273. 整数转换英文表示

Hard

题目描述

将非负整数 num 转换为其对应的英文表示。

示例 1：

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

示例 2：

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

示例 3：

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

约束条件：

0 <= num <= 2³¹ - 1

提示：

你是否看到了将数字分成单词块的模式？例如，123 和 123000。
按千位（3 位数字）对数字进行分组。你可以编写一个辅助函数，接受一个小于 1000 的数字并将该块转换为单词。
有很多边界情况。一些好的测试用例是什么？你的代码是否适用于输入如 0？或者 1000010？（中间的块为零，不应该被打印出来）

解题思路

这道题的核心思路是将大数按照千位进行分组处理。

解题思路：

特殊情况处理：首先处理 num = 0 的情况，直接返回 “Zero”。
分组策略：将数字按照千位分组，从右到左依次处理：
- 个位、十位、百位（0-999）
- 千位组（1,000-999,999）
- 百万位组（1,000,000-999,999,999）
- 十亿位组（1,000,000,000-2,147,483,647）
辅助函数设计：
- convertHundreds(num)：处理0-999范围内的数字转换
- convertTens(num)：处理0-99范围内的数字转换
处理逻辑：
- 对于每个三位数组，先转换为英文，然后添加对应的单位（Thousand、Million、Billion）
- 注意跳过值为0的组，避免输出多余的单位词
- 使用字符串拼接，注意空格的处理
边界情况：
- 数字为0时的特殊处理
- 中间某个千位组为0的情况（如1000010）
- 避免多余的空格

这种分组递归的方法既清晰又易于实现，时间复杂度为O(1)，因为数字位数有上限。

代码实现

class Solution {
public:
    string numberToWords(int num) {
        if (num == 0) return "Zero";
        
        vector<string> thousands = {"", "Thousand", "Million", "Billion"};
        string result = "";
        int group = 0;
        
        while (num > 0) {
            if (num % 1000 != 0) {
                string groupStr = convertHundreds(num % 1000);
                if (group > 0) {
                    groupStr += " " + thousands[group];
                }
                result = groupStr + (result.empty() ? "" : " " + result);
            }
            num /= 1000;
            group++;
        }
        
        return result;
    }
    
private:
    string convertHundreds(int num) {
        vector<string> ones = {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine"};
        vector<string> teens = {"Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
        vector<string> tens = {"", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
        
        string result = "";
        
        if (num >= 100) {
            result += ones[num / 100] + " Hundred";
            num %= 100;
        }
        
        if (num >= 20) {
            if (!result.empty()) result += " ";
            result += tens[num / 10];
            if (num % 10 != 0) {
                result += " " + ones[num % 10];
            }
        } else if (num >= 10) {
            if (!result.empty()) result += " ";
            result += teens[num - 10];
        } else if (num > 0) {
            if (!result.empty()) result += " ";
            result += ones[num];
        }
        
        return result;
    }
};

class Solution:
    def numberToWords(self, num: int) -> str:
        if num == 0:
            return "Zero"
        
        thousands = ["", "Thousand", "Million", "Billion"]
        result = ""
        group = 0
        
        while num > 0:
            if num % 1000 != 0:
                group_str = self.convertHundreds(num % 1000)
                if group > 0:
                    group_str += " " + thousands[group]
                result = group_str + (" " + result if result else "")
            num //= 1000
            group += 1
        
        return result
    
    def convertHundreds(self, num):
        ones = ["", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine"]
        teens = ["Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"]
        tens = ["", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"]
        
        result = ""
        
        if num >= 100:
            result += ones[num // 100] + " Hundred"
            num %= 100
        
        if num >= 20:
            if result:
                result += " "
            result += tens[num // 10]
            if num % 10 != 0:
                result += " " + ones[num % 10]
        elif num >= 10:
            if result:
                result += " "
            result += teens[num - 10]
        elif num > 0:
            if result:
                result += " "
            result += ones[num]
        
        return result

public class Solution {
    public string NumberToWords(int num) {
        if (num == 0) return "Zero";
        
        string[] thousands = {"", "Thousand", "Million", "Billion"};
        string result = "";
        int group = 0;
        
        while (num > 0) {
            if (num % 1000 != 0) {
                string groupStr = ConvertHundreds(num % 1000);
                if (group > 0) {
                    groupStr += " " + thousands[group];
                }
                result = groupStr + (string.IsNullOrEmpty(result) ? "" : " " + result);
            }
            num /= 1000;
            group++;
        }
        
        return result;
    }
    
    private string ConvertHundreds(int num) {
        string[] ones = {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine"};
        string[] teens = {"Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
        string[] tens = {"", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
        
        string result = "";
        
        if (num >= 100) {
            result += ones[num / 100] + " Hundred";
            num %= 100;
        }
        
        if (num >= 20) {
            if (!string.IsNullOrEmpty(result)) result += " ";
            result += tens[num / 10];
            if (num % 10 != 0) {
                result += " " + ones[num % 10];
            }
        } else if (num >= 10) {
            if (!string.IsNullOrEmpty(result)) result += " ";
            result += teens[num - 10];
        } else if (num > 0) {
            if (!string.IsNullOrEmpty(result)) result += " ";
            result += ones[num];
        }
        
        return result;
    }
}

var numberToWords = function(num) {
    if (num === 0) return "Zero";
    
    const ones = ["", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", 
                  "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", 
                  "Seventeen", "Eighteen", "Nineteen"];
    
    const tens = ["", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"];
    
    function helper(n) {
        if (n === 0) return "";
        else if (n < 20) return ones[n] + " ";
        else if (n < 100) return tens[Math.floor(n / 10)] + " " + helper(n % 10);
        else return ones[Math.floor(n / 100)] + " Hundred " + helper(n % 100);
    }
    
    let result = "";
    let billion = Math.floor(num / 1000000000);
    let million = Math.floor((num % 1000000000) / 1000000);
    let thousand = Math.floor((num % 1000000) / 1000);
    let remainder = num % 1000;
    
    if (billion !== 0) result += helper(billion) + "Billion ";
    if (million !== 0) result += helper(million) + "Million ";
    if (thousand !== 0) result += helper(thousand) + "Thousand ";
    if (remainder !== 0) result += helper(remainder);
    
    return result.trim();
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	分析
时间复杂度	O(1) - 因为输入数字的位数是有限的（最多10位），处理时间为常数
空间复杂度	O(1) - 除了存储常量字符串数组外，只使用了常数级别的额外空间

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目