LeetCode 面试题 16.08. 整数的英语表示

2026-03-28 HGNULB 约 6 分钟

文章信息 3 个分类 3 个标签

分类

题目描述

✅ 面试题 16.08. 整数的英语表示

题意分析

题目目标：把一个非负 32 位整数转换为规范的英文读法，例如 123 转为 One Hundred Twenty Three。
分组规则：英文整数每三位使用一个数量级，依次是 Billion、Million、Thousand 和个位组；每个三位组内部再处理 Hundred、十位和个位。
格式约束：0 单独读作 Zero；中间值为零的三位组必须跳过；单词之间只有一个空格，末尾不能留空格，也不添加 and。
朴素瓶颈：逐位翻译无法处理 10 到 19 的特殊词形，也很难正确插入数量级。按三位分组可以把问题收敛为重复转换 $1$ 到 $999$。

解法：三位一组递归转换

核心思路

主函数从高到低枚举 Billion、Million、Thousand 和个位组。对每个非零三位组调用 convert，再追加对应的数量级名称。
convert(num) 只处理 $0$ 到 $999$：小于 $20$ 直接查表；小于 $100$ 拆成整十和个位；否则先读百位，再递归处理余下两位。
递归函数对 0 返回空串，这使 100 不会多出尾词，也使主函数能够自然跳过 000 组。

解题步骤

num == 0 时直接返回 Zero。

按 {10^9, 10^6, 10^3, 1} 从高位取出当前三位组 value = num / VALUES[i]。

value != 0 时，将它转为三位以内的英文，并追加对应的 UNITS[i]；随后用取模去掉已处理部分。

三位转换中依次处理 < 20、< 100、< 1000 三种情况，最后用单个空格连接所有片段。

例如 1,234,567 被拆成 1 | 234 | 567，依次得到 One Million、Two Hundred Thirty Four Thousand、Five Hundred Sixty Seven，拼接后就是最终答案。

代码实现

// 从 Billion 到个位组三位一组处理，每组只需转换 0..999。
class Solution {
    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 int[] VALUES = {1000000000, 1000000, 1000, 1};
    private static final String[] UNITS = {"Billion", "Million", "Thousand", ""};

    public String numberToWords(int num) {
        if (num == 0) {
            return "Zero";
        }

        StringBuilder answer = new StringBuilder();
        for (int i = 0; i < VALUES.length; i++) {
            int value = num / VALUES[i];
            if (value == 0) {
                continue;
            }

            appendPart(answer, convert(value));
            appendPart(answer, UNITS[i]);
            num %= VALUES[i];
        }

        return answer.toString().trim();
    }

    private String convert(int num) {
        if (num == 0) {
            return "";
        }
        if (num < 20) {
            return LESS_THAN_20[num];
        }
        if (num < 100) {
            return (TENS[num / 10] + " " + convert(num % 10)).trim();
        }
        return (LESS_THAN_20[num / 100] + " Hundred " + convert(num % 100)).trim();
    }

    private void appendPart(StringBuilder builder, String part) {
        if (part.isEmpty()) {
            return;
        }
        if (builder.length() > 0) {
            builder.append(' ');
        }
        builder.append(part);
    }
}

import "strings"

// 从 Billion 到个位组三位一组处理，每组只需转换 0..999。
func numberToWords(num int) string {
    if num == 0 {
        return "Zero"
    }

    values := []int{1000000000, 1000000, 1000, 1}
    units := []string{"Billion", "Million", "Thousand", ""}
    parts := []string{}

    for i, value := range values {
        cur := num / value
        if cur == 0 {
            continue
        }
        parts = append(parts, convertNumber(cur))
        if units[i] != "" {
            parts = append(parts, units[i])
        }
        num %= value
    }

    return strings.Join(parts, " ")
}

func convertNumber(num int) string {
    lessThan20 := []string{"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"}
    tens := []string{"", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"}

    if num == 0 {
        return ""
    }
    if num < 20 {
        return lessThan20[num]
    }
    if num < 100 {
        parts := []string{tens[num/10]}
        if num%10 != 0 {
            parts = append(parts, convertNumber(num%10))
        }
        return strings.Join(parts, " ")
    }

    parts := []string{lessThan20[num/100], "Hundred"}
    if num%100 != 0 {
        parts = append(parts, convertNumber(num%100))
    }
    return strings.Join(parts, " ")
}

复杂度分析

时间复杂度：对 32 位整数最多处理四个三位组，可视为 $O(1)$；若推广到 $d$ 位整数，则为 $O(d)$，也与输出长度同阶。

空间复杂度：32 位范围内递归深度和分组数都是常数，即 $O(1)$；若计入返回字符串，输出空间为 $O(d)$。

关键点总结

三位分组是结构核心：外层负责数量级，内层只负责 $0$ 到 $999$ 的读法。

0 有两种语义：整个数字为零时输出 Zero，分组内部为零时输出空串并跳过该组。

$10$ 到 $19$ 必须单独查表，不能套用整十位规则。

面试时应主动说明空格策略。先收集非空片段再连接，比在每个分支手动补空格更不容易出错。

易错点总结

为零分组输出 Zero：1,000,001 应为 One Million One，不是 One Million Zero Thousand One。

把 13 拆成 Ten Three：10 到 19 的词形不规则，必须从专门数组读取 Thirteen。

忘记处理整体为零：通用分组逻辑会得到空串，所以 num == 0 必须单独返回 Zero。

边拼接边无条件加空格：容易出现连续空格或尾空格；应只追加非空片段并统一连接。

相似题目

题目	难度	考察点
273. 整数转换英文表示	困难	三位分组
补充题 14. 阿拉伯数字转中文数字	中等	中文数位规则
字节面试题-阿拉伯数字转中文	中等	分组与格式化