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

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

從英文中重建數字

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

示例 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 保證是一個符合題目要求的字符串

Java實現

先對 s 進行詞頻統計，然后根據「英文單詞中的字符唯一性」確定構建的順序，最后再對答案進行排序即可。

• zero 中的 z 在其余所有單詞中都沒出現過，可以先統計 zero 的出現次數，并構建 00；然后觀察剩余數字，其中 eight 中的 g 具有唯一性，構建 88；

• 再發現 six 中的 x 具有唯一性，構建 66；

• 發現 three 中的 h 具有唯一性（利用在此之前 eight 已經被刪除干凈，詞頻中僅存在 three 對應的 h)，構建 33 ...

最終可以確定一個可行的構建序列為 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);
    }
}

時間復雜度：O(mlogm)

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

Go實現

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

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

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)
}

時間復雜度：O(mlogm)

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

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