题目描述
这是 LeetCode 上的 273. 整数转换英文表示 ，难度为 困难。
Tag : 「模拟」
将非负整数 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} - 10<=num<=231−1
模拟
字符串大模拟，重点之一是考察大家对数字英文单词的熟练程度。🤣
首先，英文好的同学自然知道数字表示是每三位一组进行的，英文不好的可能需要通过样例来找找规律。
由于是每三位一组进行表示，首要考虑实现一个 num2Str 函数，将十进制长度小于等于 33 位的数字表示出来，然后在后面配合 Billion、Million 和 Thousand 即可表示出范围不超过 2^{32}-1232−1 的任意数字。
从定义出发 num2Str 需要解决 [0, 999][0,999] 范围内的所有整数，但由于该函数需要复用到更大的位数来配合 Billion、Million 和 Thousand，而 Zero Billion 并不是一个合法的描述，因此我们需要将 00 抠出来特判，让 num2Str 对范围在 [1, 999][1,999] 的数值进行转换。
考虑如何实现 num2Str，假设当前需要转换的数字为 xx，我们可以对 xx 的大小进行分情况讨论：
- x >= 100x>=100：此时首先需要表示成
??? hundred，表示完后考虑更小的位数； - x >= 20x>=20：此时需要表示成
??? XXX-ty的形式，表示完后考虑更小的位数； - x < 20x<20：直接描述成具体的单词。
实现完 num2Str 后，剩下的只需要考虑如何将入参 numnum 拆分成每三位一组处理即可。
代码：
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(); } } 复制代码
- 时间复杂度：令 nn 为 numnum 数值大小，复杂度取决于最终构建的答案的长度，由于是每三位一组进行处理，同时每三位一组所转换的英文描述有明确的长度上界，因此最终答案长度与 numnum 的十进制长度成线性关系，再根据 numnum 的长度与 numnum 数值的关系，可得最终复杂度为 O(\log{n})O(logn)
- 空间复杂度：令 nn 为 numnum 数值大小，复杂度取决于最终构建的答案的长度，由于是每三位一组进行处理，同时每三位一组所转换的英文描述有明确的长度上界，因此最终答案长度与 numnum 的十进制长度成线性关系，再根据 numnum 的长度与 numnum 数值的关系，可得最终复杂度为 O(\log{n})O(logn)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.273 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
