LeetCode刷题实战423：从英文中重建数字

爱被打了一巴掌 2022-08-28 00:49 138阅读 0赞

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选 ！

今天和大家聊的问题叫做 **从英文中重建数字**，我们先来看题面：

https://leetcode-cn.com/problems/reconstruct-original-digits-from-english/

> Given a string s containing an out-of-order English representation of digits 0-9, return the digits in ascending order.

给定一个非空字符串，其中包含字母顺序打乱的英文单词表示的数字0-9。按升序输出原始的数字。

注意:

输入只包含小写英文字母。

输入保证合法并可以转换为原始的数字，这意味着像 "abc" 或 "zerone" 的输入是不允许的。

输入字符串的长度小于 50,000。

## **示例** ##

示例 1:
    输入: "owoztneoer"
    输出: "012" (zeroonetwo)
    
    示例 2:
    输入: "fviefuro"
    输出: "45" (fourfive)

## **解题** ##

思路 ：

观察每个数字的英文，找出数量决定性的字母，首先判断对应的数字个数。

进而继续推理其他数字：比如我们可以从u决定four的数量，从而可以根据f来推理决定five的数量，进而可以根据v来决定seven，其他数字推理逻辑类似。

注意：nine中又两个n，最后进行9的推理是，要整除2。

class Solution:
        def DeterNums(self, index, Alphabet, numsE):
            #check
            if( not all([ True if Alphabet[w] >0 else False for w in numsE[1] ])):
                return;
            E = numsE[1][-1]
            if numsE[0] == 9:
                index[numsE[0]] = Alphabet[E]//2
                Alphabet['n'] = index[numsE[0]] 
            else:
                index[numsE[0]] = Alphabet[E]
    
            for v in numsE[1]:
                Alphabet[v] -= index[numsE[0]]
    
    
        def originalDigits(self, s: str) -> str:
            Alphabet = collections.Counter(s)
            index, re = [0] * 10, ''
            numsE = [[2, 'tow'], [0, 'eroz'], [6, 'six'], [4, 'foru'],
                     [7, 'evens'], [1, 'neo'], [5, 'ivef'], [9, 'ien'],
                     [8, 'eghti'], [3, 'treeh']]
    
            for nE in numsE:
                self.DeterNums(index, Alphabet, nE)
            re = ''
            for i in range(10):
                re += str(i)*index[i]
            return re

好了，今天的文章就到这里，如果觉得有所收获，请顺手点个**在看**或者转发吧，你们的支持是我最大的动力 。

**上期推文：**

[LeetCode1-420题汇总，希望对你有点帮助！][LeetCode1-420]

[LeetCode刷题实战421：数组中两个数的最大异或值][LeetCode_421]

![3b997961e6826f59f9034dc6cb2dac82.png][]

[LeetCode1-420]: https://blog.csdn.net/itcodexy/article/details/109832160
[LeetCode_421]: https://blog.csdn.net/itcodexy/article/details/111772001
[3b997961e6826f59f9034dc6cb2dac82.png]: /images/20220828/629c2be331ff475b8a84d56865cbd0b8.png