leetcode-166-分数到小数(用余数判断有没有出现小数的循环体)
题目描述:
如果小数部分为循环小数,则将循环的部分括在括号内。
示例 1:
输入: numerator = 1, denominator = 2
输出: "0.5"
示例 2:
输入: numerator = 2, denominator = 1
输出: "2"
示例 3:
输入: numerator = 2, denominator = 3
输出: "0.(6)"
要完成的函数:
string fractionToDecimal(int numerator, int denominator)
说明:
1、这道题给定两个整数,要求将这两个整数相除的结果存储在string中,最后返回string。
如果是无限循环小数,则要求把循环的部分用括号括起来。
2、两个整数相除,结果只有两种可能,一种是有限循环小数,一种是无限循环小数,不可能出现无限不循环小数。
这道题笔者陷入了几个误区,在这里一一列举一下,可能也会有同学跟笔者犯一样的错误。
①看到2/3=0.6666666……,2/7=0.2857142857142857……,3/7=0.4285714285714286……,就以为所有的循环部分都在小数点后最开始出现。
其实不然,比如1/6=0.166666666666666……,循环部分从第二位开始,我们存储在string中也应该是0.1(6)。
②结合了①的错误,产生了新的想法,判断当前这一位有没有出现过,如果有出现过了,那么之前出现的位置开始,到当前位置的前一位,就是循环体。
如果没有出现过,那么继续记录下去,直到出现了重复的或者直接跑完了所有小数部分(有限循环小数)。
但这样还是错误的,因为其实出现重复的位不代表这个时候就开始循环了,比如1315/10000=0.1315,第二个1出现的时候,仍然不是循环。
如果按照上面所说的方法,这时候出现了重复的位,最终结果是0.(13)。
所以究竟循环体出现的标志是什么?我们研究一下1/6。
最开始补零,变成10/6,写成0.1,这时候余数是4。
余数4再去除以6,变成40/6,写成0.16,这时候余数是4,。
余数4再去除以6……
这个时候我们都知道接下来必定是循环体结构了,因为出现了相同的被除数。
所以我们不能把两个整数变成double类型,直接相除,而是应该不断地整数相除,记录余数,余数再去除以除数。
在这个过程中记录余数,如果出现了重复的余数,那么必定是循环体结构了。
③边界条件,比如-2147483648/-1,-1/-2147483648,7/-12等等。
在下面的代码中再详解。
如下为代码:(附详解)
string fractionToDecimal(int numerator, int denominator)
{
if(numerator==INT_MIN&&denominator==-1)//边界条件,没法直接除,因为除完结果溢出
return "2147483648";
if(numerator==-1&&denominator==INT_MIN)//边界条件,都是int类型,没法除
return "0.0000000004656612873077392578125";
int shang=numerator/denominator,yushu=numerator%denominator;//记录商和余数
string res;//最终要返回的string
if(double(numerator)/double(denominator)<0)//如果两个数一正一负
{
if(shang==0)//如果商为0
res='-'+to_string(abs(shang));//可能有的同学疑惑为什么要这样处理,比如7/-12,除完shang为0,但是我们要的是-0
else
res=to_string(shang);//如果不为0,那么直接处理
}
else//如果都是正数或者都是负数
res=to_string(shang);//直接处理
if(yushu==0)//如果余数为0,那么到此为止,返回res就可以了
return res;
res+='.';//如果还有余数,那么要加个小数点
unordered_map<int,int>record;//记录出现过的余数和余数除以除数得到的商的位置
while(yushu!=0)
{
yushu=abs(yushu);//余数有可能是负的,全都转为正数
denominator=abs(denominator);//除数也转为正数
yushu*=10;//余数乘10,作为新的被除数
if(record.count(yushu))//如果之前出现过了这个余数,那么可以取出循环体了
{
int start=record[yushu],end=res.size()-1;//start和end表示循环体的开端和末尾
res=res.substr(0,start)+'('+res.substr(start,end-start+1)+')';//加一下括号
return res;//直接返回
}
record[yushu]=res.size();//如果没出现过,那么记录在record中,value是这个余数除以除数得到的商应该放的位置
shang=yushu/denominator;//更新商
yushu=yushu%denominator;//更新余数
res+=to_string(shang);//加入最新的商
}
return res;//如果一直没有出现重复的余数,那么最终跳出循环后直接返回res
}
上述代码实测0ms,beats 100.00% of cpp submissions。
最新文章
- Android之AndroidManifest.xml文件解析
- 以 Angular 的姿势打开 Font-Awesome
- avalon加载一闪而过现象
- MT【258】椭圆第三定义
- .NET Core中使用IHostedService结合队列执行定时任务
- Atitit 纯java项目的提升进度大法---通用json dsl接口
- 扩展layui中的自带字体图标
- linux golang
- Python+Selenium学习--定位iframe中的对象
- static ,final 、abstract的作用,以及它们的联系和区别
- leetcode-递增的三元子序列
- web前端导出csv文件
- 20165320 预备作业3 :Linux安装及命令入门
- ToastUtil
- 【BZOJ2763/洛谷p4563】【分层图最短路】飞行路线
- 微博excel数据清洗(Java版)
- ORM数据库查询操作之基于双下划线的跨表查询
- MySQL给字段唯一索引的三种方法
- EF选择Mysql数据源
- GIS可视化——热点图
热门文章
- sqlldr 笔记
- [原创] 分享一下Sencha 三种环境(开发环境、测试环境、生产环境)的优雅配置方案
- SpringBoot集成篇(二) 异步调用Async
- kbmMWEncodeEscapes 中汉字编码的问题及解决办法
- 2018.07.08 hdu5316 Magician(线段树)
- 2018.07.06 POJ1556 The Doors(最短路)
- Linux下编译与调试
- Docker mysql启动自动按顺序导入sql
- gj10 python socket编程
- 3D UI场景中,把XY平面的尺寸映射为屏幕像素的数学模型推导