[LeetCode]Integer to English Words

题目描述:

Convert a non-negative integer to its english words representation. Given input is guaranteed to be less than 2 ^ 31 - 1.

For example,

123 -> "One Hundred Twenty Three"
12345 -> "Twelve Thousand Three Hundred Forty Five"
1234567 -> "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"

Hint:

Did you see a pattern in dividing the number into chunk of words? For example, 123 and 123000.

Group the number by thousands (3 digits). You can write a helper function that takes a number less than 1000 and convert just that chunk to words.

There are many edge cases. What are some good test cases? Does your code work with input such as 0? Or 1000010? (middle chunk is zero and should not be printed out)

题目大意:

将非负整数转化为其英文单词表示。给定输入确保小于 2 ^ 31 - 1

测试用例见题目描述。

提示:

是否发现了将数字拆分成一组单词的模式?例如,123和123000。

将数字以千为单位分组(3位数)。可以写一个帮助函数,输入一个小于1000的数,然后将其转化为单词。

有许多边际样例。好的测试样例是什么?你的代码可以正确处理诸如0或者1000010的输入吗?(单词中间的0不应该输出)

解题思路:

使用除法和取模运算将数字以千为单位拆分成数组,再分别做单词转化

注意边界条件的处理,不需要考虑添加单词And

Python代码:

class Solution(object):
    def numberToWords(self, num):
        """
        :type num: int
        :rtype: str
        """
        lv1 = "Zero One Two Three Four Five Six Seven Eight Nine Ten \
               Eleven Twelve Thirteen Fourteen Fifteen Sixteen Seventeen Eighteen Nineteen".split()
        lv2 = "Twenty Thirty Forty Fifty Sixty Seventy Eighty Ninety".split()
        lv3 = "Hundred"
        lv4 = "Thousand Million Billion".split()
        words, digits = [], 0
        while num:
            token, num = num % 1000, num / 1000
            word = ''
            if token > 99:
                word += lv1[token / 100] + ' ' + lv3 + ' '
                token %= 100
            if token > 19:
                word += lv2[token / 10 - 2] + ' '
                token %= 10
            if token > 0:
                word += lv1[token] + ' '
            word = word.strip()
            if word:
                word += ' ' + lv4[digits - 1] if digits else ''
                words += word,
            digits += 1
        return ' '.join(words[::-1]) or 'Zero'

递归版本,参考LeetCode Discuss:https://leetcode.com/discuss/55477/recursive-python

Python代码:

class Solution(object):
    def numberToWords(self, num):
        """
        :type num: int
        :rtype: str
        """
        to19 = 'One Two Three Four Five Six Seven Eight Nine Ten Eleven Twelve ' \
               'Thirteen Fourteen Fifteen Sixteen Seventeen Eighteen Nineteen'.split()
        tens = 'Twenty Thirty Forty Fifty Sixty Seventy Eighty Ninety'.split()
        def words(n):
            if n < 20:
                return to19[n-1:n]
            if n < 100:
                return [tens[n/10-2]] + words(n%10)
            if n < 1000:
                return [to19[n/100-1]] + ['Hundred'] + words(n%100)
            for p, w in enumerate(('Thousand', 'Million', 'Billion'), 1):
                if n < 1000**(p+1):
                    return words(n/1000**p) + [w] + words(n%1000**p)
        return ' '.join(words(num)) or 'Zero'

 

本文链接:http://bookshadow.com/weblog/2015/08/31/leetcode-integer-english-words/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。

如果您喜欢这篇博文,欢迎您捐赠书影博客: ,查看支付宝二维码

Pingbacks已关闭。

暂无评论

张贴您的评论