《程序员面试金典（第6版）》面试题 16.08. 整数的英语表示

题目描述

给定一个整数，打印该整数的英文描述。

示例 1:

• 输入: 123
• 输出: “One Hundred Twenty Three”

示例 2:

• 输入: 12345
• 输出: “Twelve Thousand Three Hundred Forty Five”

示例 3:

• 输入: 1234567
• 输出: “One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven”

示例 4:

• 输入: 1234567891
• 输出: “One Billion Two Hundred Thirty Four Million Five Hundred Sixty Seven Thousand Eight Hundred Ninety One”

提示：

• 0 <= num <= 2^31 - 1

解题思路与代码

• 不知道大家怎么看这道题，但是我觉得，这道题算是一道好题。不过这道题对英语不好的朋友可能就不那么友好了。

• 在中文里，我们习惯四位数分为一组，比如1,0000就是一万。1,0000,0000就是一亿。

• 而英文呢，它们习惯是三位一组，它们没有万的概念。也没有亿的概念。转而是1,000这就是这就是一千（Thousand），而10000则是Ten Thousand（我们说是1万，而它们就是10千），1,000,000则就是Million（也就是百万）它们有百万的概念。再往后，它们没有亿的概念，但是有10亿的概念，也就是1,000,000,000 Billion

• 英文里面，0到19里面每个数字对应的英文都不一样。分别是：Zero（零），One（一），Two（二），Three（三），Four（四），Five（五），Six（六），Seven（七），Eight（八），Nine（九），Ten（十），Eleven（十一），Twelve（十二），Thirteen（十三），Fourteen（十四），Fifteen（十五），Sixteen（十六），Seventeen（十七），Eighteen（十八），Nineteen（十九）

• 紧接着，英语里面20，30,40…100的英文单词也都不一样，分别是：Twenty（二十），Thirty（三十），Forty（四十），Fifty（五十），Sixty（六十），Seventy（七十），Eighty（八十），Ninety（九十），Hundred（百）

• 最后就是几个大单位表示了：Thousand（千），Million（百万），Billion（十亿）

• 小于20的表示方法就是对应的单个英文数字，以20，30，…100这样的乘10整数就对应英语里面的20,30^100，那像 23 表示也就是 20 + 3 ，比如就是 Twenty Three ，123 就是 One Hundred Twenty Three 小于1000的大家可以自己类别。

• 我们之间讲到英语是3位一组的，所以每三位，就会加一个单位，这个单位是加在前3位之后，后三位之前的。比如 1234 就是 One Thousand Two Hundred Thirty Four ，1234567 就是 One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven，1234567890 就是 One Billion Two Hundred Thirty Million Five Hundred Sixty Seven Thousand Eight Hundred Ninety。

• 聪明的大家，一定懂了，我像表达的意思了吧。

这道题，也算是给大家补充中英区别的小知识了。紧接着，其实就是转换问题。我认为转换问题不是难事。我们只需要将数字与英文直接建立起联系就好了。

那如何建立起联系呢？我这边有两种，一种就是哈希映射，另一种呢？其实就是vector数组。

而这道题的解决方法也有两种，一种是迭代，一种是递归。两种都可以。

那么我接下来，我就一点一点的来展现给大家。

方法一：哈希映射 + switch结构（迭代方案）

这种方法是我第一种想出来的方法，我认为这种方法实在是十分的简易好懂，并且逻辑关系清晰。不过缺点就是有点无脑，复杂度较高。

接下来，我来给大家讲讲我这道题的解题思路：我首先，是将除了大单位外每一个可能出现的英语单词，分为3组，分别用哈希映射的方式，放入3个unordered_map<int,string>中。
然后命名4个int，billion，million，thousand，remainder分别对应着3个大单位，与小于最小的大单位可能出现的3位数。比如123000，thousand = 123。

之后只需要再创建一个string 去存储最后的结果，在用if判断，去依次判断billion，million，thousand的值是否大于0，如果大于0，就调用一个函数去生成结果，最后依次加上对应的结果就好。

函数里面写的就是，如何处理进来的3位数的逻辑。如果是0-9我们怎么样，10-19我们怎么样，等等。

具体的实现，请看代码：

class Solution {
public:string numberToWords(int num) {if (num == 0) return "Zero";string res = "";int billion = num / 1000000000;int million = (num % 1000000000) / 1000000;int thousand = (num % 1000000) / 1000;int remainder = num % 1000;if (billion > 0) res += getHundreds(billion) + " Billion";if (million > 0) {if (!res.empty()) res += " ";res += getHundreds(million) + " Million";}if (thousand > 0) {if (!res.empty()) res += " ";res += getHundreds(thousand) + " Thousand";}if (remainder > 0) {if (!res.empty()) res += " ";res += getHundreds(remainder);}return res;}string getHundreds(int num){string strNum = to_string(num);int size = strNum.size();unordered_map<int,string> map{{0,"Zero"},{1,"One"},{2,"Two"},{3,"Three"},{4,"Four"},{5,"Five"},{6,"Six"},{7,"Seven"},{8,"Eight"},{9,"Nine"}};unordered_map<int,string> map1{{10,"Ten"},{11,"Eleven"},{12,"Twelve"},{13,"Thirteen"},{14,"Fourteen"},{15,"Fifteen"},{16,"Sixteen"},{17,"Seventeen"},{18,"Eighteen"},{19,"Nineteen"}};unordered_map<int,string> map2{{20,"Twenty"},{30,"Thirty"},{40,"Forty"},{50,"Fifty"},{60,"Sixty"},{70,"Seventy"},{80,"Eighty"},{90,"Ninety"},};switch(size){case 1:return map[num];case 2:{if(num < 20){return map1[num];}else if(num >=20 && num % 10 == 0){return map2[num];}else{int ones = num % 10;string strOnes = map[ones];int tensDigit = num - ones;string strTD = map2[tensDigit];strTD += " ";strTD += strOnes;return strTD;}}case 3:{string result = "";int hundreds_digit = num / 100;result += map[hundreds_digit];result += " Hundred";num %= 100;if(num < 20 && num > 9){result += " ";result += map1[num];return result;}else if(num <= 9){if(num == 0) return result;result += " ";result += map[num];return result;}else{int onesDigit = num % 10;int tensDigit = num - onesDigit;result += " ";result += map2[tensDigit];if(onesDigit == 0) return result;result += " ";result += map[onesDigit];return result;}}}return "";}
};

复杂度分析

时间复杂度：

• 时间复杂度是由两个主要部分组成的：numberToWords() 函数和 getHundreds() 函数。numberToWords() 函数的时间复杂度主要取决于 getHundreds() 函数调用的次数，最多为 4 次（分别是十亿、百万、千和余数）。getHundreds() 函数中的运算和查找操作的时间复杂度为 O(1)。因此，整个程序的时间复杂度可以表示为 O(1)。

空间复杂度：

• 空间复杂度主要取决于两个因素：局部变量（包括整数和字符串）和哈希表。局部变量的空间复杂度为 O(1)。哈希表的空间复杂度取决于它们的大小，但是由于它们的大小是固定的，所以哈希表的空间复杂度也为 O(1)。综上，整个程序的空间复杂度可以表示为 O(1)。

方法二：方法一的优化升级，用vector代替unordered_map,用if_else代替switch（迭代方案）

这个做法，稍微比上个做法高明了些，具体在于，我们用4个vector去存储，每一个对应可能出现的英语代码，去替代上一回的哈希映射。

用for循环每次去除1000，去代替上一种解决方案里面的4个int变量。

写的那个函数，我们也不用switch语句了，直接改成if判断语句。具体的做法就是这样，代码的逻辑并没有变，还是依旧是迭代遍历。

class Solution {
public:vector<string> singles = {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine"};vector<string> teens = {"Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};vector<string> tens = {"", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};vector<string> thousands = {"", "Thousand", "Million", "Billion"};string numberToWords(int num) {if(num == 0) return "Zero";string result = "";for(int i = 3,unit = 1000000000; i >= 0; --i,unit /= 1000){int curr = num / unit;if(curr != 0){num -= curr * unit;result += toEnglish(curr);result += thousands[i];result += " ";}}while(result.back() == ' ') result.pop_back();return result;}string toEnglish(int num){string res = "";int hundred = num / 100;num %= 100;if(hundred > 0){res +=  singles[hundred];res += " Hundred ";} int ten = num / 10;if(ten >= 2){num %= 10;res += tens[ten];res += " ";}if(num > 0 && num <= 9 ){res += singles[num];res += " ";}else if(num >= 10){res += teens[num - 10];res += " ";}return res;}
};

复杂度分析

时间复杂度：

• 时间复杂度是由两个主要部分组成的：numberToWords() 函数和 toEnglish() 函数。numberToWords() 函数中的循环固定运行 4 次（分别是十亿、百万、千和余数）。在每次循环中，会调用一次 toEnglish() 函数。toEnglish() 函数中的运算和查找操作的时间复杂度为 O(1)。因此，整个程序的时间复杂度可以表示为 O(1)。

空间复杂度：

• 空间复杂度主要取决于两个因素：局部变量（包括整数和字符串）和向量。局部变量的空间复杂度为 O(1)。向量的空间复杂度取决于它们的大小，但是由于它们的大小是固定的，所以向量的空间复杂度也为 O(1)。综上，整个程序的空间复杂度可以表示为 O(1)。

方法三：方案二的变式，副函数用递归去处理

方法三的主函数的逻辑不变，变的其实就是副函数如何处理3位数转换成英文的逻辑。

我觉得这种方式，是三种方法里面最简单易懂的副函数处理方法。极具代码美感。

具体的代码如下：

class Solution {
public:vector<string> singles = {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine"};vector<string> teens = {"Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};vector<string> tens = {"", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};vector<string> thousands = {"", "Thousand", "Million", "Billion"};string numberToWords(int num) {if(num == 0) return "Zero";string result;for(int i = 3,unit = 1000000000; i >=0; --i, unit /= 1000){int curNum = num / unit;if(curNum != 0){num %= unit;toEnglish(result,curNum);result += thousands[i];result += " ";}}while(result.back() == ' ') result.pop_back();return result;}void toEnglish(string& str,int curNum){if(curNum == 0) return;if(curNum < 10){str += singles[curNum];str += " ";}else if(curNum < 20){str += teens[curNum - 10];str += " ";}else if(curNum < 100){int ten = curNum / 10;str += tens[ten];str += " ";toEnglish(str,curNum % 10);}else {int hundred = curNum / 100;str += singles[hundred];str += " Hundred ";toEnglish(str,curNum % 100);}}
};

复杂度分析

时间复杂度：

• 时间复杂度主要取决于 numberToWords() 函数和 toEnglish() 函数。numberToWords() 函数中的循环固定运行 4 次（分别是十亿、百万、千和余数）。在每次循环中，会调用一次 toEnglish() 函数。toEnglish() 函数的时间复杂度主要取决于递归调用的深度，最大深度为 3。因此，整个程序的时间复杂度可以表示为 O(1)。

空间复杂度：

• 空间复杂度主要取决于两个因素：局部变量（包括整数和字符串）和向量。局部变量的空间复杂度为 O(1)。向量的空间复杂度取决于它们的大小，但是由于它们的大小是固定的，所以向量的空间复杂度也为 O(1)。此外，toEnglish() 函数采用了引用参数，因此不会引入额外的空间开销。综上，整个程序的空间复杂度可以表示为 O(1)。

总结

这三种方法各有优缺点。方法一使用哈希表实现，查找速度快，但代码略显冗长。方法二和三使用向量实现，代码简洁，其中方法三还采用了递归方式，进一步简化了代码，使代码极具美感。

总的来说，这对于练习编程逻辑和数字处理是一个很好的实践。

最后的最后，如果你觉得我的这篇文章写的不错的话，请给我一个赞与收藏，关注我，我会继续给大家带来更多更优质的干货内容。