原文链接: https://leetcode-cn.com/problems/integer-to-english-words

英文原文

Convert a non-negative integer num to its English words representation.

 

Example 1:

Input: num = 123
Output: "One Hundred Twenty Three"

Example 2:

Input: num = 12345
Output: "Twelve Thousand Three Hundred Forty Five"

Example 3:

Input: num = 1234567
Output: "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"

Example 4:

Input: num = 1234567891
Output: "One Billion Two Hundred Thirty Four Million Five Hundred Sixty Seven Thousand Eight Hundred Ninety One"

 

Constraints:

• 0 <= num <= 231 - 1

中文题目

将非负整数 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 <= 231 - 1

通过代码

高赞题解

模拟

字符串大模拟，重点之一是考察大家对数字英文单词的熟练程度。🤣

首先，英文好的同学自然知道数字表示是每三位一组进行的，英文不好的可能需要通过样例来找找规律。

由于是每三位一组进行表示，首要考虑实现一个 num2Str 函数，将十进制长度小于等于 $3$ 位的数字表示出来，然后在后面配合 Billion、Million 和 Thousand 即可表示出范围不超过 $2^{32}-1$ 的任意数字。

从定义出发 num2Str 需要解决 $[0, 999]$ 范围内的所有整数，但由于该函数需要复用到更大的位数来配合 Billion、Million 和 Thousand，而 Zero Billion 并不是一个合法的描述，因此我们需要将 $0$ 抠出来特判，让 num2Str 对范围在 $[1, 999]$ 的数值进行转换。

考虑如何实现 num2Str，假设当前需要转换的数字为 $x$，我们可以对 $x$ 的大小进行分情况讨论：

1. $x >= 100$：此时首先需要表示成 ??? hundred，表示完后考虑更小的位数；
2. $x >= 20$：此时需要表示成 ??? XXX-ty 的形式，表示完后考虑更小的位数；
3. $x < 20$：直接描述成具体的单词。

实现完 num2Str 后，剩下的只需要考虑如何将入参 $num$ 拆分成每三位一组处理即可。

代码：

[]
class Solution {
    static String[] num2str_small = {
        "Zero", 
        "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", 
        "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"
    };
    static String[] num2str_medium = {
        "", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"
    };
    static String[] num2str_large = {
        "Billion", "Million", "Thousand", "",
    };
    String num2Str(int x) {
        String ans = "";
        if (x >= 100) {
            ans += num2str_small[x / 100] + " Hundred ";
            x %= 100;
        }
        if (x >= 20) {
            ans += num2str_medium[x / 10] + " ";
            x %= 10;
        }
        if (x != 0) ans += num2str_small[x] + " ";
        return ans;
    }
    public String numberToWords(int num) {
        if (num == 0) return num2str_small[0];
        StringBuilder sb = new StringBuilder();
        for (int i = (int)1e9, j = 0; i >= 1; i /= 1000, j++) {
            if (num < i) continue;
            sb.append(num2Str(num / i) + num2str_large[j] + " ");
            num %= i;
        }
        while (sb.charAt(sb.length() - 1) == ' ') sb.deleteCharAt(sb.length() - 1);
        return sb.toString();
    }
}

• 时间复杂度：令 $n$ 为 $num$ 数值大小，复杂度取决于最终构建的答案的长度，由于是每三位一组进行处理，同时每三位一组所转换的英文描述有明确的长度上界，因此最终答案长度与 $num$ 的十进制长度成线性关系，再根据 $num$ 的长度与 $num$ 数值的关系，可得最终复杂度为 $O(\log{n})$
• 空间复杂度：令 $n$ 为 $num$ 数值大小，复杂度取决于最终构建的答案的长度，由于是每三位一组进行处理，同时每三位一组所转换的英文描述有明确的长度上界，因此最终答案长度与 $num$ 的十进制长度成线性关系，再根据 $num$ 的长度与 $num$ 数值的关系，可得最终复杂度为 $O(\log{n})$

---

最后

如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ (“▔□▔)/

也欢迎你 关注我（公主号后台回复「送书」即可参与长期看题解学算法送实体书活动）或 加入「组队打卡」小群 ，提供写「证明」&「思路」的高质量题解。

所有题解已经加入 刷题指南，欢迎 star 哦 ~

统计信息

通过次数	提交次数	AC比率
29364	80029	36.7%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

相似题目

题目	难度
整数转罗马数字	中等