0273. Integer to English Words ============================== 题目信息 -------- :题号: 0273 :难度: Hard :主题: 整数表示、英文数字、字符串格式 :原题: `LeetCode 0273 `_ :重点: 按十亿、百万、千和百位数量级表达、零值单独处理、单词间不能出现多余空格 题目重述 -------- 给定一个非负整数 ``num``,返回它对应的英文数字字符串。数值应使用标准的 ``Billion``、``Million``、``Thousand`` 和 ``Hundred`` 等数量级词,并把每个非零部分按从高位到低位排列。 ``num`` 位于 ``[0, 2^31 - 1]``。当输入为 ``0`` 时返回 ``"Zero"``。结果中的英文单词首字母采用题目示例所示的大写形式,相邻单词之间恰好使用一个空格,字符串开头和结尾都不能有空格;不添加英文口语中的 ``and``。 自建示例 -------- 中间三位组含零: .. code-block:: text 输入:num = 1005 输出:"One Thousand Five" 解释:1005 由一个千和五个一组成,百位与十位为零,因此不会产生对应单词,也不会留下多余空格。 两位整数: .. code-block:: text 输入:num = 42 输出:"Forty Two" 解释:42 由四十和二组成,两个单词之间使用一个空格。 零值: .. code-block:: text 输入:num = 0 输出:"Zero" 解释:零不按普通数量级拆分,题目规定直接返回单词 Zero。 按三位一组拆分 -------------- 英文数量级每隔三位变化一次,因此把数字从高到低拆成 Billion、Million、Thousand 和末组三位。 每个非零三位组先用 ``underThousand`` 转成 ``1..999`` 的英文,再追加它对应的数量级单词; 值为 0 的组完全跳过。统一使用“追加单词并在必要时补一个空格”的方式,可避免组之间和结果两端多余空格。 三位组内部再按百位、十位和个位处理:20 以上使用 ``Tens`` 与个位,10 到 19 使用独立的 ``Teens``, 百位非零时追加 ``One Hundred`` 等。``num=0`` 是唯一不经过分组的特殊情况,直接返回 ``Zero``。 正确性说明 ---------- 三位分组是十进制表示的无损拆分,高位组先输出且每个数量级只在对应组非零时出现。 ``underThousand`` 对任意 0 到 999 按百、十、个位覆盖互斥情形,并保持数值的位序; 把所有非零组按原顺序拼接后,恰好表达原数字,跳过零组不会改变数值也不会生成空白占位词。 C++ 实现 -------- .. code-block:: cpp class Solution { const std::vector below_20{ "", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen" }; const std::vector tens{ "", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety" }; std::string underThousand(int value) const { std::string result; if (value >= 100) { result += below_20[value / 100] + " Hundred"; value %= 100; if (value != 0) result += " "; } if (value >= 20) { result += tens[value / 10]; value %= 10; if (value != 0) result += " "; } if (value > 0) result += below_20[value]; return result; } public: std::string numberToWords(int num) { if (num == 0) return "Zero"; const std::vector scales{1000000000, 1000000, 1000, 1}; const std::vector names{ "Billion", "Million", "Thousand", "" }; std::string result; for (int i = 0; i < static_cast(scales.size()); ++i) { const int group = num / scales[i]; num %= scales[i]; if (group == 0) continue; if (!result.empty()) result += " "; result += underThousand(group); if (!names[i].empty()) result += " " + names[i]; } return result; } }; 代码分析 -------- 最多处理四个三位组和固定大小的词表,算法时间复杂度为 ``O(1)``(更准确地说与输出长度成正比), 额外空间为固定词表及结果字符串。分组时用整数除法和取余,不需要浮点数,也不会把 0 组错误写成数量级词。