LeetCode 整數轉英文單詞：分段處理三位一組

題目描述

將非負整數（< 2³¹）轉換為英文單詞表示。例如：

123 -> "One Hundred Twenty Three"
12345 -> "Twelve Thousand Three Hundred Forty Five"
1234567 -> "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"

解題思路

1. 將數字按千位分組（每 3 位一組）：Billion、Million、Thousand、空（個位組）。
2. 編寫輔助函數 convertHundreds(num) 處理 0~999 的數字：
   - 百位：num/100 + "Hundred"
   - 十位與個位：<20 直接查表；≥20 查十位表 + 個位表。
3. 從高組到低組遍歷，若該組不為 0，調用輔助函數並加上對應單位（Billion/Million/Thousand）。
4. 特殊情況：輸入 0 直接返回 "Zero"；中間組為 0 時跳過不輸出單位。

參考代碼 (C++)

class Solution {
public:
    string numberToWords(int num) {
        if (num == 0) return "Zero";
        const vector units = {"", " Thousand", " Million", " Billion"};
        string res;
        for (int i = 0; num > 0; ++i) {
            if (num % 1000 != 0) {
                res = convertHundreds(num % 1000) + units[i] + res;
            }
            num /= 1000;
        }
        return res.substr(1); // 去除首部空格
    }
private:
    string convertHundreds(int num) {
        static const vector below20 = {"", " One", " Two", " Three", " Four", " Five",
            " Six", " Seven", " Eight", " Nine", " Ten", " Eleven", " Twelve", " Thirteen",
            " Fourteen", " Fifteen", " Sixteen", " Seventeen", " Eighteen", " Nineteen"};
        static const vector tens = {"", "", " Twenty", " Thirty", " Forty", " Fifty",
            " Sixty", " Seventy", " Eighty", " Ninety"};
        string s;
        if (num >= 100) {
            s += below20[num/100] + " Hundred";
            num %= 100;
        }
        if (num >= 20) {
            s += tens[num/10];
            num %= 10;
        }
        if (num > 0) s += below20[num];
        return s;
    }
};

複雜度分析

• 時間複雜度：O(1) —— 數字固定最多 10 位，循環常數次。
• 空間複雜度：O(1) —— 僅使用常數大小的查表數組。