题目地址:https://leetcode.com/problems/reconstruct-original-digits-from-english/description/

题目描述:

Given a non-empty string containing an out-of-order English representation of digits 0-9, output the digits in ascending order.

Note:

1、 InputcontainsonlylowercaseEnglishletters.;
2、 Inputisguaranteedtobevalidandcanbetransformedtoitsoriginaldigits.Thatmeansinvalidinputssuchas"abc"or"zerone"arenotpermitted.;
3、 Inputlengthislessthan50,000.;

Example 1: Input: "owoztneoer"

Output: "012"

Example 2: Input: "fviefuro"

Output: "45"

题目大意

根据一个打乱了的英文表示的字符串以升序重构出阿拉伯数字。

解题方法

刚开始就做错了,都怪我太年轻,以为从0~9把所有能够成的都提前构成,最后就是结果了。这样不对,因为可能会有剩余的字符了。这个题说了,不会有剩余字符。

这个题不是很好,并没有考编程的思想,而是考的找规律。。面试应该不会问的。

错误代码:

class Solution(object):
    def originalDigits(self, s):
        """
        :type s: str
        :rtype: str
        """
        number = ['zero', 'one', 'two', 'three', 'four', 'five', 'six', 'seven', 'eight', 'nine']
        count = collections.Counter(s)
        res = ''
        for i, num in enumerate(number):
            while True:
                word_count = 0
                for c in num:
                    if count[c] > 0:
                        word_count += 1
                if word_count == len(num):
                    res += str(i)
                    count.subtract(collections.Counter(num))
                else:
                    break
        return res

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

正确做法如下:

选自:http://bookshadow.com/weblog/2016/10/16/leetcode-reconstruct-original-digits-from-english/

统计字符串s中各字符的个数,需要注意的是,在枚举英文字母时,需要按照特定的顺序方可得到正确答案。

例如按照顺序:6028745913,这个顺序可以类比拓扑排序的过程。

观察英文单词,six, zero, two, eight, seven, four中分别包含唯一字母x, z, w, g, v, u;因此6, 0, 2, 8, 7, 4需要排在其余数字之前。

排除这6个数字之后,剩下的4个数字中,按照字母唯一的原则顺次挑选。

由于剩下的单词中,只有five包含f,因此选为下一个单词;

以此类推,可以得到上面所述的顺序。

在上文代码的基础上,我进行了一点点的技巧性的改变,就是Counter()自带的有subtract()方法,直接从字典中减去了新字典。。

class Solution(object):
    def originalDigits(self, s):
        """
        :type s: str
        :rtype: str
        """
        cnts = collections.Counter(s)
        nums = ['six', 'zero', 'two', 'eight', 'seven', 'four', 'five', 'nine', 'one', 'three']
        numc = [collections.Counter(num) for num in nums]
        digits = [6, 0, 2, 8, 7, 4, 5, 9, 1, 3]
        ans = [0] * 10
        for idx, num in enumerate(nums):
            cntn = numc[idx]
            t = min(cnts[c] /  cntn[c] for c in cntn)
            ans[digits[idx]] = t
            for i in range(t):
                cnts.subtract(cntn)
        return ''.join(str(i) * n for i, n in enumerate(ans))

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

DDKK.COM 弟弟快看-教程,程序员编程资料站,版权归原作者所有

本文经作者:负雪明烛 授权发布,任何组织或个人未经作者授权不得转发