题目

LeetCode.273.整数转换英文表示（困难）

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

题解

定义问题，发现规律

根据示例，可以发现：

每3位数的读法是一样的。
每3位数末尾的量词读法不一样。

那么问题一下子就明确了，只需要：

按每三个数一组，拆分原数字。
每一组调用统一的三位数读法处理方法。
每一组的末尾用不同的量词。

接下来的问题就是：

如何三位一组拆分原数字？
怎么知道要拆分几组？
每一组怎么把数字对应上英文？

如何三位一组拆分原数字？

利用不保留余数的除法。

比如 123456789。

如何得到789？
- 123456789 % 1000 = 789
如何得到456？
- 123456789 / 1000 = 123456
- 123456 % 1000 = 456
如何得到123？
- 123456789 / 1000 / 1000 = 123

这样的拆分这是可以递归进行的。

怎么知道要拆分几组？

比如

1、12、123就不需要拆分了。
1234、12345、123456可以拆分为两组。
1234567、12345678、123456789可以拆分为三组。
1234567890可以拆分为四组。

再多的位数不考虑了。

因为num <= 2^31 - 1 ，其中2^31 = 2147483648，是10位数。

每一组怎么把数字对应上英文？

每一组是小于1000的，得看英文中是怎么描述小于1000的数字的。

可以小于100的一些数有单独的单词：

0到9
10到19
20、30、40、50、60、70、80、90

这里可以用哈希表存储数字对应的单词。

大于20小于100，没有单独单词的数字怎么读？

个位置零后的两位数单词 + 个位数对应的单词

100到1000的数怎么读？

百位数单独读法 + Hundred + 两位数或个位数读法

所有情况都罗列出来了，可以直接照着写。

边界情况

不能拆分，说明是0，要读Zero。

复杂度

时间复杂度O(n)：n为数字位数，需要检测每一位的数字的读法。
空间复杂度O(1)：仅用常数个变量。

class Solution {
    private val map = mapOf(
            0 to "Zero",
            1 to "One",
            2 to "Two",
            3 to "Three",
            4 to "Four",
            5 to "Five",
            6 to "Six",
            7 to "Seven",
            8 to "Eight",
            9 to "Nine",
            10 to "Ten",
            11 to "Eleven",
            12 to "Twelve",
            13 to "Thirteen",
            14 to "Fourteen",
            15 to "Fifteen",
            16 to "Sixteen",
            17 to "Seventeen",
            18 to "Eighteen",
            19 to "Nineteen",
            20 to "Twenty",
            30 to "Thirty",
            40 to "Forty",
            50 to "Fifty",
            60 to "Sixty",
            70 to "Seventy",
            80 to "Eighty",
            90 to "Ninety"
    )

    private val units = arrayOf("Thousand", "Million", "Billion")

    fun numberToWords(num: Int): String {
        val strings = helper(num)
        return if (strings.isNotEmpty()) return strings.joinToString(" ")
        else "Zero"
    }

    private fun helper(num: Int): List<String> {
        if (num == 0) return emptyList()
        if (num < 20) return listOf(map.getValue(num))
        if (num < 100) {
            return listOf(map.getValue(num / 10 * 10)) + helper(num % 10)
        }
        if (num < 1000) {
            return listOf(map.getValue(num / 100), "Hundred") + helper(num % 100)
        }
        for (i in 1..3) {
            if (num < 1000L.pow(i + 1)) {
                val high = num / 1000L.pow(i).toInt()
                val remain = num % 1000L.pow(i).toInt()
                return helper(high) + listOf(units[i - 1]) + helper(remain)
            }
        }
        return emptyList()
    }

    private fun Long.pow(n: Int): Long {
        var result = 1L
        repeat(n) { result *= this }
        return result
    }
}