江川个人博客FIELD NOTES / 个人知识库

Article / 文章

LeetCode 第273题：整数转换英文表示

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

📖 文章摘要

本文详细解析LeetCode第273题“整数转换英文表示”，这是一道字符串处理和递归设计的困难问题。文章提供了从递归分治到迭代优化的完整解法思路，包含英语数字表示规律的深度分析和边界情况处理技巧，配有详细的算法分解过程和实现要点。适合想要掌握复杂字符串处理和递归算法设计的高级算法学习者。

核心知识点： 递归分治、字符串处理、英语数字规律、边界情况处理
难度等级： 困难
推荐人群： 字符串处理进阶者、递归算法设计者

题目描述

将非负整数 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"

示例 4：

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

提示

  • 0 <= num <= 2^31 - 1

解题思路

这道题的关键在于理解英语数字表示的规律，并将复杂问题分解为简单的子问题。

核心分析

英语数字表示规律：

  1. 三位分组：英语中数字是每三位一组进行表示的
  2. 单位递增：从右到左依次是：个位、千位(Thousand)、百万位(Million)、十亿位(Billion)
  3. 特殊数字：需要特别处理小于20的数字和整十的数字
  4. 组合规则：每个三位组内部遵循相同的组合规则

解题策略：

  1. 创建基础数字词汇表（1-19, 20-90的整十数）
  2. 实现处理三位数的递归函数
  3. 从右到左每三位一组处理，添加相应单位
  4. 处理空格和边界情况

方法一：递归分治法

核心思想：

  • 将问题分解为处理三位数的子问题
  • 递归处理每个三位数组
  • 根据位置添加相应的单位（Thousand, Million, Billion）

算法步骤：

  1. 特殊处理0的情况
  2. 创建基础词汇表
  3. 递归处理不同数量级的数字
  4. 组合结果并处理空格

复杂度分析：

  • 时间复杂度：O(log n)，其中n是输入数字，因为我们需要处理的位数是log₁₀(n)级别的
  • 空间复杂度：O(1)，除了存储结果字符串外，只使用了常数级别的额外空间

方法二：迭代法

核心思想：

  • 使用迭代的方式从右到左处理每三位数
  • 维护一个结果字符串，每次在前面插入新的部分

算法步骤：

  1. 预定义所有需要的单词数组
  2. 从低位开始每三位一组处理
  3. 为每组添加相应的单位
  4. 组合最终结果

复杂度分析：

  • 时间复杂度：O(log n)
  • 空间复杂度：O(1)

图解思路

数字分解过程分析表

输入数字 分组 单位 处理结果 说明
1234567891 1 Billion “One Billion” 十亿位处理
234567891 234 Million “Two Hundred Thirty Four Million” 百万位处理
567891 567 Thousand “Five Hundred Sixty Seven Thousand” 千位处理
891 891 - “Eight Hundred Ninety One” 个位处理

三位数处理分析表

以567为例：

位置 数字 处理 结果部分 说明
百位 5 5 -> “Five” “Five Hundred” 添加Hundred
十位 6 60 -> “Sixty” “Sixty” 整十数处理
个位 7 7 -> “Seven” “Seven” 个位数处理
最终 567 组合 “Five Hundred Sixty Seven” 空格连接

代码实现

C# 实现

public class Solution {
    private readonly string[] LESS_THAN_20 = {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
    private readonly string[] TENS = {"", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
    private readonly string[] THOUSANDS = {"", "Thousand", "Million", "Billion"};
    
    public string NumberToWords(int num) {
        if (num == 0) return "Zero";
        
        int i = 0;
        string words = "";
        
        while (num > 0) {
            if (num % 1000 != 0) {
                words = Helper(num % 1000) + THOUSANDS[i] + " " + words;
            }
            num /= 1000;
            i++;
        }
        
        return words.Trim();
    }
    
    private string Helper(int num) {
        if (num == 0) return "";
        else if (num < 20) return LESS_THAN_20[num] + " ";
        else if (num < 100) return TENS[num / 10] + " " + Helper(num % 10);
        else return LESS_THAN_20[num / 100] + " Hundred " + Helper(num % 100);
    }
}

Python 实现

class Solution:
    def numberToWords(self, num: int) -> str:
        if num == 0:
            return "Zero"
        
        less_than_20 = ["", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"]
        tens = ["", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"]
        
        def helper(n):
            if n < 20:
                return less_than_20[n]
            elif n < 100:
                return tens[n // 10] + (" " + less_than_20[n % 10] if n % 10 else "")
            elif n < 1000:
                return less_than_20[n // 100] + " Hundred" + (" " + helper(n % 100) if n % 100 else "")
            elif n < 1000000:
                return helper(n // 1000) + " Thousand" + (" " + helper(n % 1000) if n % 1000 else "")
            elif n < 1000000000:
                return helper(n // 1000000) + " Million" + (" " + helper(n % 1000000) if n % 1000000 else "")
            else:
                return helper(n // 1000000000) + " Billion" + (" " + helper(n % 1000000000) if n % 1000000000 else "")
        
        return helper(num)

C++ 实现

class Solution {
public:
    string numberToWords(int num) {
        if (num == 0) return "Zero";
        
        vector<string> lessThan20 = {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
        vector<string> tens = {"", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
        vector<string> thousands = {"", "Thousand", "Million", "Billion"};
        
        string result;
        int groupIndex = 0;
        
        while (num > 0) {
            int group = num % 1000;
            if (group > 0) {
                string groupStr = helper(group, lessThan20, tens);
                
                // 添加单位
                if (groupIndex > 0) {
                    groupStr += " " + thousands[groupIndex];
                }
                
                // 插入到结果前面
                if (!result.empty()) {
                    result = groupStr + " " + result;
                } else {
                    result = groupStr;
                }
            }
            
            num /= 1000;
            groupIndex++;
        }
        
        return result;
    }
    
private:
    string helper(int num, vector<string>& lessThan20, vector<string>& tens) {
        if (num < 20) {
            return lessThan20[num];
        } else if (num < 100) {
            return tens[num / 10] + (num % 10 ? " " + lessThan20[num % 10] : "");
        } else {
            return lessThan20[num / 100] + " Hundred" + (num % 100 ? " " + helper(num % 100, lessThan20, tens) : "");
        }
    }
};

执行结果

C# 实现

  • 执行用时：84 ms
  • 内存消耗：40.2 MB

Python 实现

  • 执行用时：52 ms
  • 内存消耗：16.8 MB

C++ 实现

  • 执行用时：0 ms
  • 内存消耗：6.8 MB

性能对比

语言 执行用时 内存消耗 特点
C++ 0 ms 6.8 MB 性能最优，内存占用最小
Python 52 ms 16.8 MB 代码简洁，逻辑清晰
C# 84 ms 40.2 MB 结构化好，易于维护

代码亮点

  1. 🎯 递归分治思想完美体现，将复杂问题分解为处理三位数的简单子问题
  2. 💡 充分利用英语数字规律，通过预定义词汇表避免重复逻辑
  3. 🔍 边界情况处理完善，正确处理0、空格和各种数量级
  4. 🎨 代码结构清晰，递归函数职责单一，易于理解和扩展

常见错误分析

  1. 🚫 边界情况处理：输入为0时直接返回“Zero”，容易遗漏
  2. 🚫 空格处理：避免多余的空格，特别是在单词之间和结果末尾
  3. 🚫 大小写问题：每个单词的首字母都要大写，容易遗漏
  4. 🚫 数字范围：题目限制在2³¹-1以内，最大到Billion级别

解法对比

解法 时间复杂度 空间复杂度 优点 缺点
递归分治法 O(log n) O(log n) 代码简洁，逻辑清晰 递归调用有额外开销
迭代法 O(log n) O(1) 空间效率高，无递归开销 代码稍复杂，需要手动管理状态
查表法 O(1) O(1) 最快的查询速度 只适用于有限范围，表格庞大

相关题目

📖 系列导航

🔥 算法专题合集 - 查看完整合集

📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新第273题。

💬 互动交流

感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。

如果这篇文章对你有帮助，请：

  • 👍 点个赞，让更多人看到这篇文章
  • 📁 收藏文章，方便后续查阅复习
  • 🔔 关注作者，获取更多高质量算法题解
  • 💭 评论区留言，分享你的解题思路或提出疑问

你的支持是我持续分享的动力！

💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！