Go?Java算法之怎么從英文中重建數(shù)字

今天小編給大家分享一下Go Java算法之怎么從英文中重建數(shù)字的相關(guān)知識(shí)點(diǎn)，內(nèi)容詳細(xì)，邏輯清晰，相信大部分人都還太了解這方面的知識(shí)，所以分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后有所收獲，下面我們一起來了解一下吧。

從英文中重建數(shù)字

給你一個(gè)字符串 s ，其中包含字母順序打亂的用英文單詞表示的若干數(shù)字（0-9）。按 升序 返回原始的數(shù)字。

示例 1：

輸入：s = "owoztneoer" 輸出："012" 示例 2：

輸入：s = "fviefuro" 輸出："45"  

提示：

1 <= s.length <= 105

s[i] 為 ["e","g","f","i","h","o","n","s","r","u","t","w","v","x","z"] 這些字符之一

s 保證是一個(gè)符合題目要求的字符串

Java實(shí)現(xiàn)

先對 s 進(jìn)行詞頻統(tǒng)計(jì)，然后根據(jù)「英文單詞中的字符唯一性」確定構(gòu)建的順序，最后再對答案進(jìn)行排序即可。

• zero 中的 z 在其余所有單詞中都沒出現(xiàn)過，可以先統(tǒng)計(jì) zero 的出現(xiàn)次數(shù)，并構(gòu)建 00；然后觀察剩余數(shù)字，其中 eight 中的 g 具有唯一性，構(gòu)建 88；

• 再發(fā)現(xiàn) six 中的 x 具有唯一性，構(gòu)建 66；

• 發(fā)現(xiàn) three 中的 h 具有唯一性（利用在此之前 eight 已經(jīng)被刪除干凈，詞頻中僅存在 three 對應(yīng)的 h)，構(gòu)建 33 ...

最終可以確定一個(gè)可行的構(gòu)建序列為 0, 8, 6, 3, 2, 7, 5, 9, 4, 1。

class Solution {
    static String[] ss = new String[]{"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"};
    static int[] priority = new int[]{0, 8, 6, 3, 2, 7, 5, 9, 4, 1};
    public String originalDigits(String s) {
        int n = s.length();
        int[] cnts = new int[26];
        for (int i = 0; i < n; i++) cnts[s.charAt(i) - 'a']++;
        StringBuilder sb = new StringBuilder();
        for (int i : priority) {
            int k = Integer.MAX_VALUE;
            for (char c : ss[i].toCharArray()) k = Math.min(k, cnts[c - 'a']);
            for (char c : ss[i].toCharArray()) cnts[c - 'a'] -= k;
            while (k-- > 0) sb.append(i);
        }
        char[] cs = sb.toString().toCharArray();
        Arrays.sort(cs);
        return String.valueOf(cs);
    }
}

時(shí)間復(fù)雜度：O(mlogm)

空間復(fù)雜度：O(L+m)

Go實(shí)現(xiàn)

輸入中各個(gè)字母的個(gè)數(shù)，可以知道一些數(shù)字的個(gè)數(shù)了，比如只有零用了z，只有六用了x等等，

在將一些可以求得的個(gè)數(shù)求了后，將它們占用的其他字母的個(gè)數(shù)排除掉，經(jīng)過排除后，剩下的有用到別人用過的字母的數(shù)字的個(gè)數(shù)也可以得到了。 比如在四的個(gè)數(shù)通過u得到后，五的個(gè)數(shù)就可以通過剩下的f的個(gè)數(shù)得到了。

func originalDigits(s string) string {
    cnts, a := make([]int, 26), byte('a')
    for i := range s {
        cnts[s[i] - a]++
    }
    zeros, twos, fours, sixs, eights := cnts[byte('z') - a], cnts[byte('w') - a], cnts[byte('u') - a], cnts[byte('x') - a], cnts[byte('g') - a]
    fives, sevens, ones, threes := cnts[byte('f') - a] - fours, cnts[byte('s') - a] - sixs, cnts[byte('o') - a] - zeros - twos - fours, cnts[byte('h') - a] - eights
    nines := cnts[byte('i') - a] - fives - sixs - eights
    return strings.Repeat("0", zeros) + strings.Repeat("1", ones) + strings.Repeat("2", twos) + strings.Repeat("3", threes) + strings.Repeat("4", fours) + strings.Repeat("5", fives) + strings.Repeat("6", sixs) + strings.Repeat("7", sevens) + strings.Repeat("8", eights) + strings.Repeat("9", nines)
}

時(shí)間復(fù)雜度：O(mlogm)

空間復(fù)雜度：O(L+m)

以上就是“Go Java算法之怎么從英文中重建數(shù)字”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家閱讀完這篇文章都有很大的收獲，小編每天都會(huì)為大家更新不同的知識(shí)，如果還想學(xué)習(xí)更多的知識(shí)，請關(guān)注億速云行業(yè)資訊頻道。