题目

将非负整数 num 转换为其对应的英文表示。
提示：0 <= num <= 2^31 - 1

示例：

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

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

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

解答 & 代码

模拟，三位一组进行转换

class Solution {
public:
    string numberToWords(int num) {
        unordered_map<int, string> map {{1, "One"}, {2, "Two"}, {3, "Three"}, {4, "Four"}, 
                                        {5, "Five"}, {6, "Six"}, {7, "Seven"}, {8, "Eight"}, {9, "Nine"}, 
                                        {10, "Ten"}, {11, "Eleven"}, {12, "Twelve"}, {13, "Thirteen"}, {14, "Fourteen"}, 
                                        {15, "Fifteen"}, {16, "Sixteen"}, {17, "Seventeen"}, {18, "Eighteen"}, {19, "Nineteen"},
                                        {20, "Twenty"}, {30, "Thirty"}, {40, "Forty"}, {50, "Fifty"}, {60, "Sixty"},
                                        {70, "Seventy"}, {80, "Eighty"}, {90, "Ninety"}};
        vector<string> part = {"", "Thousand", "Million", "Billion"};
        // 存储整数的每一位数值（逆序）
        vector<int> number;
        while(num > 0)
        {
            number.push_back(num % 10);
            num /= 10;
        } 
        int len = number.size();
        string result;        // 结果字符串
        int idx = len - 1;
        while(idx >= 0)        // 每次 3 个数字一组进行迭代
        {
            int partIdx = idx / 3;    // 代表当前三位是 0、千、百万、十亿 级别
            bool zero = true;        // 代表当前三位是否都为 0
            // 处理当前三位的百位
            if(idx % 3 == 2)
            {
                if(number[idx] != 0)
                {
                    result += map[number[idx]];
                    result += " Hundred ";
                    zero = false;
                }
                --idx;
            }
            bool ten = false;        // 代表十位是否为 1
            // 处理当前三位的十位
            if(idx % 3 == 1)
            {
                if(number[idx] == 1)
                {
                    ten = true;
                    zero = false;
                }
                else if(number[idx] > 1)
                {
                    result += map[number[idx] * 10];
                    result += " ";
                    zero = false;
                }
                --idx;
            }
            // 处理当前三位的个位
            if(idx % 3 == 0)
            {
                int cur = number[idx];
                if(ten == true)            // 若十位为 1，则和个位一起处理
                    cur += 10;
                if(cur != 0)
                {
                    result += map[cur];
                    result += " ";
                    zero = false;
                }
                --idx;
            }
            // 若当前三位数字不都为 0，则加上 0/千/百万/十亿 后缀
            if(zero == false)
            {
                result += part[partIdx];
                result += " ";
            }
        }
        // 去掉结果的后缀空格
        for(int i = result.size() - 1; i >= 0 && result[i] == ' '; --i)
            result.pop_back();
        // 如果结果数组为空，则为 Zero
        if(result.size() == 0)
            result = "Zero";
        return result;
    }
};

复杂度分析：

时间复杂度 O(1)：3 位一组，最多 4 组，因为 num <= 2^31 - 1
空间复杂度 O(1)：结果字符串不计入。哈希表存储的是常数级别的

执行结果：

执行结果：通过
执行用时：4 ms, 在所有 C++ 提交中击败了 69.29% 的用户
内存消耗：7.8 MB, 在所有 C++ 提交中击败了 11.28% 的用户

hot 100

[困难] 273. 整数转换英文表示

题目

解答 & 代码