《程序员面试金典(第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 就是 OneMillion
Two Hundred Thirty FourThousand
Five Hundred Sixty Seven,1234567890 就是 OneBillion
Two Hundred ThirtyMillion
Five Hundred Sixty SevenThousand
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)。
总结
这三种方法各有优缺点。方法一使用哈希表实现,查找速度快,但代码略显冗长。方法二和三使用向量实现,代码简洁,其中方法三还采用了递归方式,进一步简化了代码,使代码极具美感。
总的来说,这对于练习编程逻辑和数字处理是一个很好的实践。
最后的最后,如果你觉得我的这篇文章写的不错的话,请给我一个赞与收藏,关注我,我会继续给大家带来更多更优质的干货内容
。
相关文章:

《程序员面试金典(第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…...
ChatGPT技术原理 第四章:Transformer模型
目录 4.1 什么是Transformer 4.2 Transformer结构详解 4.3 Self-Attention机制 4.4 Multi-Head Attention机制 4.1 什么是Transformer...

基于redis和threadlocal实现登录状态校验和拦截
1.流程图 单机节点下的登录状态校验 分布式节点下的登录状态校验 2.代码实现 实现步骤分为如下几步 实现WebMvcConfigurer接口,添加拦截器定义拦截器,需要配置两个interceptor,第一个用于刷新token,写threadlocalÿ…...

14-6-进程间通信-信号量
前面学习了pipe,fifo,共享内存,信号。 本章将讲述信号量。 一、什么是信号量/信号量集? 1.什么是信号量 信号量是一个计数器。信号量用于实现进程间的同步和互斥。而可以取多个正整数的信号量被称为通用信号量。 对信号量的使用场景的解读 房间&#…...
《中国教育报》投稿邮箱编辑部征稿
《中国教育报》国家教育部主管,中国教育报刊社主办的以教育新闻为主的全国性日报。是迄今为止中国最具权威和最有影响力的教育新闻媒体。中国教育报刊社是中华人民共和国教育部直属的新闻出版机构。2018年获得第三届全国“百强报纸”。2019年入选“新媒体影响力指数…...

Photoshop如何使用绘画和图像修饰之实例演示?
文章目录 0.引言1.给图像添加渐变色效果2.快速创建一副素描画3.清除图像中多余的景物4.快速融合两张图像5.调整图像光影6.人像面部瑕疵修除7.美化眼睛 0.引言 因科研等多场景需要进行绘图处理,笔者对PS进行了学习,本文通过《Photoshop2021入门教程》及其…...

【C++】布隆过滤器
文章目录 布隆过滤器提出布隆过滤器概念布隆过滤器应用场景设计思路:布隆过滤器的插入布隆过滤器的查找布隆过滤器删除BloomFilter.h布隆过滤器优点布隆过滤器缺陷 布隆过滤器提出 我们在使用新闻客户端看新闻时,它会给我们不停地推荐新的内容,它每次推荐时要去重,去掉那些已经…...

功能齐全的 ESP32 智能手表,具有多个表盘、心率传感器硬件设计
相关设计资料下载ESP32 智能手表带心率、指南针设计资料(包含Arduino源码+原理图+Gerber+3D文件).zip 介绍 我们调查了智能手表项目的不同方面,并学会了集成和测试每个单独的部分。在本文中,我们将使用所学知识,结合使用硬件和软件组件,从头开始创建我们自己的智能手表。在…...

微服务不是本地部署的最佳选择,不妨试试模块化单体
微服务仅适用于成熟产品 关于从头开始使用微服务,马丁・福勒(Martin Fowler)总结道: 1. 几乎所有成功的微服务都是从一个过于庞大而不得不拆分的单体应用开始的。 2. 几乎所有从头开始以微服务构建的系统,最后都会因…...

解读Toolformer
【引子】读论文Toolformer: Language Models Can Teach Themselves to Use Tools,https://arxiv.org/pdf/2302.04761.pdf,再阅读了几篇关于Toolformer的网络热文,于是“无知者无畏”,开始自不量力地试图解读Toolformer。 大语言模…...

FCOS3D Fully Convolutional One-Stage Monocular 3D Object Detection 论文学习
论文地址:Fully Convolutional One-Stage Monocular 3D Object Detection Github地址:Fully Convolutional One-Stage Monocular 3D Object Detection 1. 解决了什么问题? 单目 3D 目标检测由于成本很低,对于自动驾驶任务非常重…...
Xpath学习笔记
Xpath原理:先将HTML文档转为XML文档,再用xpath查找HTML节点或元素 什么是xml? 1、xml指可扩展标记语言 2、xml是一种标记原因,类似于html 3、xml的设计宗旨是传输数据,而非显示数据 4、xml标签需要我们自己自定义 5、x…...

网络编程之 Socket 套接字(使用数据报套接字和流套接字分别实现一个小程序(附源码))
文章目录 1. 什么是网络编程2. 网络编程中的基本概念1)发送端和接收端2)请求和响应3)客户端和服务端4)常见的客户端服务端模型 3. Socket 套接字1)Socket 的分类2)Java 数据报套接字通信模型3)J…...
What Are Docker Image Layers?
Docker images consist of multiple layers that collectively provide the content you see in your containers. But what actually is a layer, and how does it differ from a complete image? In this article you’ll learn how to distinguish these two concepts and…...

范数详解-torch.linalg.norm计算实例
文章目录 二范数F范数核范数无穷范数L1范数L2范数 前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站。 范数是一种数学概念,可以将向量或矩阵映射到非负实数上,通常被…...
postgresdb备份脚本
以下是一个简单的postgresdb备份脚本示例: 复制 #!/bin/bash # 设置备份目录和文件名 BACKUP_DIR/path/to/backup BACKUP_FILEdb_backup_$(date %F_%H-%M-%S).sql # 设置数据库连接参数 DB_HOSTlocalhost DB_PORT5432 DB_NAMEmydatabase DB_USERmyusername DB_PA…...
MATLAB程序员投简历的技巧解析,如何写出有亮点的简历
如果你想在简历中展示你的项目经验,一定要有亮点。一个导出的 Excel 文件过大导致浏览器卡顿的例子就是一个很好的亮点。你可以在简历中写明这个例子。如果面试官问起,可以用浏览器的原理来解释。浏览器内核可以简单地分为以下 5 个线程:GUI …...

颜色空间转换RGB-YCbCr
颜色空间 颜色空间(Color Space)是描述颜色的一种方式,它是一个由数学模型表示的三维空间,通常用于将数字表示的颜色转换成可见的颜色。颜色空间的不同取决于所选的坐标轴和原点,以及用于表示颜色的色彩模型。在计算机…...
年薪40万程序员辞职炒股,把一年工资亏光了,得了抑郁症,太惨了
年薪40万的程序员辞职全职炒股 把一年的工资亏光了 得了抑郁症 刚才在网上看了一篇文章 是一位北京的一位在互联网 大厂上班的程序员 在去年就是股市行情比较好的时候 他买了30多万股票 结果连续三个月都赚钱 然后呢 他是就把每天就996这种工作就辞掉了 然后在家全是炒股 感觉炒…...

10分钟如何轻松掌握JMeter使用方法?
目录 引言 安装jmeter HTTP信息头管理器 JMeter断言 HTTP请求默认值来代替所有的域名与端口 JSON提取器来替换变量 结语 引言 想要了解网站或应用程序的性能极限,JMeter是一个不可或缺的工具。但是,对于初学者来说,该如何上手使用JMe…...
Vim 调用外部命令学习笔记
Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...
ubuntu搭建nfs服务centos挂载访问
在Ubuntu上设置NFS服务器 在Ubuntu上,你可以使用apt包管理器来安装NFS服务器。打开终端并运行: sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享,例如/shared: sudo mkdir /shared sud…...

阿里云ACP云计算备考笔记 (5)——弹性伸缩
目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...

从零实现STL哈希容器:unordered_map/unordered_set封装详解
本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说,直接开始吧! 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...

自然语言处理——Transformer
自然语言处理——Transformer 自注意力机制多头注意力机制Transformer 虽然循环神经网络可以对具有序列特性的数据非常有效,它能挖掘数据中的时序信息以及语义信息,但是它有一个很大的缺陷——很难并行化。 我们可以考虑用CNN来替代RNN,但是…...
06 Deep learning神经网络编程基础 激活函数 --吴恩达
深度学习激活函数详解 一、核心作用 引入非线性:使神经网络可学习复杂模式控制输出范围:如Sigmoid将输出限制在(0,1)梯度传递:影响反向传播的稳定性二、常见类型及数学表达 Sigmoid σ ( x ) = 1 1 +...

Mysql中select查询语句的执行过程
目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析(Parser) 2.4、执行sql 1. 预处理(Preprocessor) 2. 查询优化器(Optimizer) 3. 执行器…...

使用Spring AI和MCP协议构建图片搜索服务
目录 使用Spring AI和MCP协议构建图片搜索服务 引言 技术栈概览 项目架构设计 架构图 服务端开发 1. 创建Spring Boot项目 2. 实现图片搜索工具 3. 配置传输模式 Stdio模式(本地调用) SSE模式(远程调用) 4. 注册工具提…...
python爬虫——气象数据爬取
一、导入库与全局配置 python 运行 import json import datetime import time import requests from sqlalchemy import create_engine import csv import pandas as pd作用: 引入数据解析、网络请求、时间处理、数据库操作等所需库。requests:发送 …...
Java求职者面试指南:Spring、Spring Boot、Spring MVC与MyBatis技术解析
Java求职者面试指南:Spring、Spring Boot、Spring MVC与MyBatis技术解析 一、第一轮基础概念问题 1. Spring框架的核心容器是什么?它的作用是什么? Spring框架的核心容器是IoC(控制反转)容器。它的主要作用是管理对…...