难度: 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 <= 231 - 1运行时间: 26 ms
内存: 16.1 MB
singles = ["", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine"]
teens = ["Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"]
tens = ["", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"]
thousands = ["", "Thousand", "Million", "Billion"]
class Solution:
def numberToWords(self, num: int) -> str:
if num == 0:
return "Zero"
def recur(num: int) -> str:
s = ""
if num == 0:
return s
elif num < 10:
s += singles[num] + " "
elif num < 20:
s += teens[num - 10] + " "
elif num < 100:
s += tens[num // 10] + " " + recur(num % 10)
else:
s += singles[num // 100] + " Hundred " + recur(num % 100)
return s
s = ""
unit = int(1e9)
for i in range(3, -1, -1):
cur_num = num // unit
if cur_num:
num -= cur_num * unit
s += recur(cur_num) + thousands[i] + " "
unit //= 1000
return s.strip()
解题思路主要基于对数字的逐段解析，将整数划分为若干三位数的段，每个段内单独处理，并转换为英文表述。首先定义四个列表，分别表示个位数、十位数中的特殊情况（10到19）、普通的十位数后缀（20, 30, ...），以及千位数的后缀（千、百万、十亿）。主要函数使用递归处理每个三位数的段，再将这些段结合千位数后缀组合起来形成完整的英文表述。递归函数处理小于10的数返回对应的英文，处理小于20的数返回特殊的青少年数字英文，处理小于100的数将十位和个位分开处理，处理三位数时将百位、十位和个位分开处理。整个数按千的倍数逐步减少，每处理完一个三位数的段，就添加相应的千位后缀。
时间复杂度: O(n)
空间复杂度: O(1)
singles = ["", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine"]
teens = ["Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"]
tens = ["", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"]
thousands = ["", "Thousand", "Million", "Billion"]
class Solution:
def numberToWords(self, num: int) -> str:
if num == 0:
return "Zero"
def recur(num: int) -> str:
s = ""
if num == 0:
return s
elif num < 10:
s += singles[num] + " "
elif num < 20:
s += teens[num - 10] + " "
elif num < 100:
s += tens[num // 10] + " " + recur(num % 10)
else:
s += singles[num // 100] + " Hundred " + recur(num % 100)
return s
s = ""
unit = int(1e9)
for i in range(3, -1, -1):
cur_num = num // unit
if cur_num:
num -= cur_num * unit
s += recur(cur_num) + thousands[i] + " "
unit //= 1000
return s.strip()
在这个算法中，数字被分为三位数的段，并逐个处理这些段。递归函数 `recur` 负责处理每个三位数段。每次处理一个段后，数字减去当前段的值，然后继续处理剩余的数字。这是通过在主函数中逐步减少 `num` 的值实现的，每次减去 `cur_num * unit`，其中 `cur_num` 是当前段的值，`unit` 是当前段的基数（例如1000、1000000等）。这种方法确保了即使在数字边界情况下，每个数字段都被准确处理，不会遗漏。例如，对于数字1000，`cur_num` 会是1，然后 `thousands[i]` 会是'Thousand'，确保了1000被正确翻译为'One Thousand'。
递归方法在处理这种分层的数字表示时显得更自然和直观。每个三位数的处理可以看作是一个独立的问题，递归允许我们将大问题（如整个数字的英文表示）分解成小问题（每三位数字的英文表示）。递归的方式简化了代码的复杂性，使得处理单独的数字段（如百位、十位和个位）更加清楚和直接。虽然迭代也可以实现，但可能需要更多的状态管理和控制结构，这可能会使代码更加复杂和难以理解。
算法通过一个专门的列表 `teens` 来处理10到19之间的数字，这些数字在英文中有特殊的表示（如'Ten', 'Eleven', 'Twelve'等）。当 `num < 20` 时，递归函数会直接从 `teens` 数组中返回正确的表示，确保了这些特殊情况被正确处理。这种直接映射的方法简单且有效，避免了在数字组合时混淆普通的十位数和这些特殊数的读法。
对于极小的值（如0），算法非常高效，因为直接返回了'Zero'。对于极大的值，如接近2^31 - 1的值，算法仍然需要逐个处理每个三位数段，这可能导致递归调用多次。虽然这种方法在正常范围内的数字上表现良好，但在极端大数字情况下效率可能会稍微降低。优化方向可能包括减少递归调用的次数，例如通过迭代替代递归，或者通过预计算和缓存常见的数字模式来减少计算次数。