自动化设计网站建设,福永附近网站建设公司,如何做框架网站,一个网站要多少钱题目描述 给定一个整数#xff0c;打印该整数的英文描述。 示例 1:
输入: 123输出: “One Hundred Twenty Three”
示例 2:
输入: 12345输出: “Twelve Thousand Three Hundred Forty Five”
示例 3:
输入: 1234567输出: “One Million Two Hundred Thirty Four Thousand…题目描述 给定一个整数打印该整数的英文描述。 示例 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十九 紧接着英语里面2030,40…100的英文单词也都不一样分别是Twenty二十Thirty三十Forty四十Fifty五十Sixty六十Seventy七十Eighty八十Ninety九十Hundred百 最后就是几个大单位表示了Thousand千Million百万Billion十亿 小于20的表示方法就是对应的单个英文数字以2030…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 Seven1234567890 就是 One Billion Two Hundred Thirty Million Five Hundred Sixty Seven Thousand Eight Hundred Ninety。 聪明的大家一定懂了我像表达的意思了吧。
这道题也算是给大家补充中英区别的小知识了。紧接着其实就是转换问题。我认为转换问题不是难事。我们只需要将数字与英文直接建立起联系就好了。
那如何建立起联系呢我这边有两种一种就是哈希映射另一种呢其实就是vector数组。
而这道题的解决方法也有两种一种是迭代一种是递归。两种都可以。
那么我接下来我就一点一点的来展现给大家。
方法一哈希映射 switch结构迭代方案 这种方法是我第一种想出来的方法我认为这种方法实在是十分的简易好懂并且逻辑关系清晰。不过缺点就是有点无脑复杂度较高。 接下来我来给大家讲讲我这道题的解题思路我首先是将除了大单位外每一个可能出现的英语单词分为3组分别用哈希映射的方式放入3个unordered_mapint,string中。 然后命名4个intbillionmillionthousandremainder分别对应着3个大单位与小于最小的大单位可能出现的3位数。比如123000thousand 123。
之后只需要再创建一个string 去存储最后的结果在用if判断去依次判断billionmillionthousand的值是否大于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_mapint,string map{{0,Zero},{1,One},{2,Two},{3,Three},{4,Four},{5,Five},{6,Six},{7,Seven},{8,Eight},{9,Nine}};unordered_mapint,string map1{{10,Ten},{11,Eleven},{12,Twelve},{13,Thirteen},{14,Fourteen},{15,Fifteen},{16,Sixteen},{17,Seventeen},{18,Eighteen},{19,Nineteen}};unordered_mapint,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:vectorstring singles {, One, Two, Three, Four, Five, Six, Seven, Eight, Nine};vectorstring teens {Ten, Eleven, Twelve, Thirteen, Fourteen, Fifteen, Sixteen, Seventeen, Eighteen, Nineteen};vectorstring tens {, Ten, Twenty, Thirty, Forty, Fifty, Sixty, Seventy, Eighty, Ninety};vectorstring 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:vectorstring singles {, One, Two, Three, Four, Five, Six, Seven, Eight, Nine};vectorstring teens {Ten, Eleven, Twelve, Thirteen, Fourteen, Fifteen, Sixteen, Seventeen, Eighteen, Nineteen};vectorstring tens {, Ten, Twenty, Thirty, Forty, Fifty, Sixty, Seventy, Eighty, Ninety};vectorstring 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)。
总结
这三种方法各有优缺点。方法一使用哈希表实现查找速度快但代码略显冗长。方法二和三使用向量实现代码简洁其中方法三还采用了递归方式进一步简化了代码使代码极具美感。
总的来说这对于练习编程逻辑和数字处理是一个很好的实践。
最后的最后如果你觉得我的这篇文章写的不错的话请给我一个赞与收藏关注我我会继续给大家带来更多更优质的干货内容。
