LeetCode273-整数转换英文表示

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/integer-to-english-words/

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

题目详述

将非负整数转换为其对应的英文表示。可以保证给定输入小于 2^31 - 1 。

示例 1:

1
2
输入: 123
输出: "One Hundred Twenty Three"

示例 2:

1
2
输入: 12345
输出: "Twelve Thousand Three Hundred Forty Five"

示例 3:

1
2
输入: 1234567
输出: "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"

示例 4:

1
2
输入: 1234567891
输出: "One Billion Two Hundred Thirty Four Million Five Hundred Sixty Seven Thousand Eight Hundred Ninety One"

题目详解

  • 为了方便处理，用一个哈希表存储数字与单词的映射关系。
  • 对问题进行分解，3 位作为一组，配合 thousand、million、billion 即可表示 10^12 以内的所有数，即 xxx billion xxx million xxx thousand xxx。
  • 然后考虑如何表示 1000 以内的数，可以分为以下 方式：
    • 如果大于等于 100，需要先写 x hundred。
    • 如果末两位不超过 20，直接输出对应的单词。
    • 如果末两位是 10 的倍数，直接输出对应的单词。
    • 如果末两位大于 20，输出对应的十位与个位。
  • 时间复杂度分析：计算量与 n 的十进制表示的位数成正比，所以时间复杂度是 O(logn)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
public class LeetCode_00273 {

    private static Map<Integer, String> map;

    static {
        map = new HashMap<>();
        map.put(1, "One");
        map.put(2, "Two");
        map.put(3, "Three");
        map.put(4, "Four");
        map.put(5, "Five");
        map.put(6, "Six");
        map.put(7, "Seven");
        map.put(8, "Eight");
        map.put(9, "Nine");
        map.put(10, "Ten");
        map.put(11, "Eleven");
        map.put(12, "Twelve");
        map.put(13, "Thirteen");
        map.put(14, "Fourteen");
        map.put(15, "Fifteen");
        map.put(16, "Sixteen");
        map.put(17, "Seventeen");
        map.put(18, "Eighteen");
        map.put(19, "Nineteen");
        map.put(20, "Twenty");
        map.put(30, "Thirty");
        map.put(40, "Forty");
        map.put(50, "Fifty");
        map.put(60, "Sixty");
        map.put(70, "Seventy");
        map.put(80, "Eighty");
        map.put(90, "Ninety");
        map.put(100, "Hundred");
        map.put(1000, "Thousand");
        map.put(1000000, "Million");
        map.put(1000000000, "Billion");
    }

    public String numberToWords(int num) {
        if (num == 0) {
            return "Zero";
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 1000000000; i >= 1000; i /= 1000) {
            if (num >= i) {
                sb.append(get3Digits(num / i)).append(' ').append(map.get(i));
                num %= i;
            }
        }
        if (num > 0) {
            sb.append(get3Digits(num));
        }
        return sb.substring(1);
    }

    private String get3Digits(int num) {
        StringBuilder sb = new StringBuilder();
        if (num >= 100) {
            sb.append(' ').append(map.get(num / 100)).append(' ').append(map.get(100));
            num %= 100;
        }
        if (num > 0) {
            if (num < 20 || num % 10 == 0) {
                sb.append(' ').append(map.get(num));
            } else {
                sb.append(' ').append(map.get(num / 10 * 10)).append(' ').append(map.get(num % 10));
            }
        }
        return sb.toString();
    }
}