题目描述

给定一个非负整数，请输出它的英文表示。给定的整数小于 $2^{31}-1$。

样例1

输入：123
输出："One Hundred Twenty Three"

样例2

输入：12345
输出："Twelve Thousand Three Hundred Forty Five"

样例3

输入：1234567
输出："One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"

样例4

输入：1234567891
输出："One Billion Two Hundred Thirty Four Million Five Hundred Sixty Seven Thousand Eight Hundred Ninety One"

算法

(模拟) $O(logn)$

为了便于处理，我们将所有单词和数字的映射关系存入哈希表。

然后将原问题分解，我们发现如果可以表示0~999，然后配合 thousand、million、billion即可表示出 $10^{12}$以内的所有数。即: xxx billion xxx million xxx thousand xxx，其中xxx是0~999的表示方式。

然后考虑如何表示1000以内的数，分情况讨论：

• 如果大于等于100，则需要先写出 x hundred，x是1~9的英文表示；
• 如果末两位大于20，则需要写出 xx-ty y，xx-ty是20~90的英文表示，y是1~9的英文表示；
• 如果末两位不超过20，则直接输出相应的英文单词；

时间复杂度分析：计算量与 $n$ 的十进制表示的位数成正比，所以时间复杂度是 $O(logn)$。

C++ 代码

class Solution {
public:
    int hundred = 100, thousand = 1000, million = 1000000, billion = 1000000000;
    unordered_map<int, string> numbers;

    string numberToWords(int num) {
        char number20[][30] = {"Zero", "One", "Two", "Three", "Four", "Five", 
                               "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", 
                               "Twelve", "Thirteen", "Fourteen", "Fifteen", 
                               "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
        char number2[][30] = {"Twenty", "Thirty", "Forty", "Fifty", "Sixty", 
                              "Seventy", "Eighty", "Ninety"};
        for (int i = 0; i < 20; i ++ ) numbers[i] = number20[i];
        for (int i = 20, j = 0; i < 100; i += 10, j ++ ) numbers[i] = number2[j];
        numbers[hundred] = "Hundred", numbers[thousand] = "Thousand";
        numbers[million] = "Million", numbers[billion] = "Billion";
        string res;
        for (int k = 1000000000; k >= 100; k /= 1000)
        {
            if (num >= k)
            {
                res += ' ' + get3(num / k) + ' ' + numbers[k];
                num %= k;
            }
        }
        if (num) res += ' ' + get3(num);
        if (res.empty()) res = ' ' + numbers[0];
        return res.substr(1);
    }

    string get3(int num)
    {
        string res;
        if (num >= hundred)
        {
            res += ' ' + numbers[num / hundred] + ' ' + numbers[hundred];
            num %= hundred;
        }
        if (num)
        {
            if (num < 20) res += ' ' + numbers[num];
            else if (num % 10 == 0) res += ' ' + numbers[num];
            else res += ' ' + numbers[num / 10 * 10] + ' ' + numbers[num % 10];
        }
        return res.substr(1);
    }
};