整数转换英文表示

难度:

标签:

题目描述

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

代码结果

运行时间: 26 ms, 内存: 16.1 MB

/*
 * 将非负整数 num 转换为其对应的英文表示。
 * 使用Java Stream
 */
import java.util.*;
import java.util.stream.Collectors;
 
public class NumberToWordsStream {
    private static final String[] LESS_THAN_20 = {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
    private static final String[] TENS = {"", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
    private static final String[] THOUSANDS = {"", "Thousand", "Million", "Billion"};
 
    public String numberToWords(int num) {
        if (num == 0) return "Zero";
        List<String> parts = new ArrayList<>();
        int i = 0;
        while (num > 0) {
            if (num % 1000 != 0) {
                parts.add(0, helper(num % 1000) + THOUSANDS[i]);
            }
            num /= 1000;
            i++;
        }
        return parts.stream().filter(str -> !str.isEmpty()).collect(Collectors.joining(" ")).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);
    }
}

解释

方法:

解题思路主要基于对数字的逐段解析，将整数划分为若干三位数的段，每个段内单独处理，并转换为英文表述。首先定义四个列表，分别表示个位数、十位数中的特殊情况（10到19）、普通的十位数后缀（20, 30, ...），以及千位数的后缀（千、百万、十亿）。主要函数使用递归处理每个三位数的段，再将这些段结合千位数后缀组合起来形成完整的英文表述。递归函数处理小于10的数返回对应的英文，处理小于20的数返回特殊的青少年数字英文，处理小于100的数将十位和个位分开处理，处理三位数时将百位、十位和个位分开处理。整个数按千的倍数逐步减少，每处理完一个三位数的段，就添加相应的千位后缀。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆

在将数字分为三位数段的方法中，递归函数是如何确保不会遗漏处理某些数字的，特别是在数字边界（如1000，1000000）的情况下？

▷

在这个算法中，数字被分为三位数的段，并逐个处理这些段。递归函数 `recur` 负责处理每个三位数段。每次处理一个段后，数字减去当前段的值，然后继续处理剩余的数字。这是通过在主函数中逐步减少 `num` 的值实现的，每次减去 `cur_num * unit`，其中 `cur_num` 是当前段的值，`unit` 是当前段的基数（例如1000、1000000等）。这种方法确保了即使在数字边界情况下，每个数字段都被准确处理，不会遗漏。例如，对于数字1000，`cur_num` 会是1，然后 `thousands[i]` 会是'Thousand'，确保了1000被正确翻译为'One Thousand'。

🦆

为什么选择递归作为处理每个三位数的主要方法，而不是迭代或其他可能的解决方案？

▷

递归方法在处理这种分层的数字表示时显得更自然和直观。每个三位数的处理可以看作是一个独立的问题，递归允许我们将大问题（如整个数字的英文表示）分解成小问题（每三位数字的英文表示）。递归的方式简化了代码的复杂性，使得处理单独的数字段（如百位、十位和个位）更加清楚和直接。虽然迭代也可以实现，但可能需要更多的状态管理和控制结构，这可能会使代码更加复杂和难以理解。

🦆

在处理特殊的十位数（10到19）时，这种方法如何保证其正确性，尤其是在数的组合需要区分特殊读法和普通读法的情况下？

▷

算法通过一个专门的列表 `teens` 来处理10到19之间的数字，这些数字在英文中有特殊的表示（如'Ten', 'Eleven', 'Twelve'等）。当 `num < 20` 时，递归函数会直接从 `teens` 数组中返回正确的表示，确保了这些特殊情况被正确处理。这种直接映射的方法简单且有效，避免了在数字组合时混淆普通的十位数和这些特殊数的读法。

🦆

对于极大或极小的输入值（如0或接近2^31 - 1的值），这个算法的效率如何？是否有可能对其进行优化？

▷

对于极小的值（如0），算法非常高效，因为直接返回了'Zero'。对于极大的值，如接近2^31 - 1的值，算法仍然需要逐个处理每个三位数段，这可能导致递归调用多次。虽然这种方法在正常范围内的数字上表现良好，但在极端大数字情况下效率可能会稍微降低。优化方向可能包括减少递归调用的次数，例如通过迭代替代递归，或者通过预计算和缓存常见的数字模式来减少计算次数。

相关问题

整数转罗马数字

罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。

字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

例如，罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。

给你一个整数，将其转为罗马数字。

示例 1:

输入: num = 3
输出: "III"

示例 2:

输入: num = 4
输出: "IV"

示例 3:

输入: num = 9
输出: "IX"

示例 4:

输入: num = 58
输出: "LVIII"
解释: L = 50, V = 5, III = 3.

示例 5:

输入: num = 1994
输出: "MCMXCIV"
解释: M = 1000, CM = 900, XC = 90, IV = 4.

提示：

1 <= num <= 3999

最接近的二叉搜索树值 II H 指数