题目描述:

 
给定两个整数,分别表示分数的分子 numerator 和分母 denominator,以字符串形式返回小数。

如果小数部分为循环小数,则将循环的部分括在括号内。

示例 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。

最新文章

  1. Android之AndroidManifest.xml文件解析
  2. 以 Angular 的姿势打开 Font-Awesome
  3. avalon加载一闪而过现象
  4. MT【258】椭圆第三定义
  5. .NET Core中使用IHostedService结合队列执行定时任务
  6. Atitit 纯java项目的提升进度大法---通用json dsl接口
  7. 扩展layui中的自带字体图标
  8. linux golang
  9. Python+Selenium学习--定位iframe中的对象
  10. static ,final 、abstract的作用,以及它们的联系和区别
  11. leetcode-递增的三元子序列
  12. web前端导出csv文件
  13. 20165320 预备作业3 :Linux安装及命令入门
  14. ToastUtil
  15. 【BZOJ2763/洛谷p4563】【分层图最短路】飞行路线
  16. 微博excel数据清洗(Java版)
  17. ORM数据库查询操作之基于双下划线的跨表查询
  18. MySQL给字段唯一索引的三种方法
  19. EF选择Mysql数据源
  20. GIS可视化——热点图

热门文章

  1. sqlldr 笔记
  2. [原创] 分享一下Sencha 三种环境(开发环境、测试环境、生产环境)的优雅配置方案
  3. SpringBoot集成篇(二) 异步调用Async
  4. kbmMWEncodeEscapes 中汉字编码的问题及解决办法
  5. 2018.07.08 hdu5316 Magician(线段树)
  6. 2018.07.06 POJ1556 The Doors(最短路)
  7. Linux下编译与调试
  8. Docker mysql启动自动按顺序导入sql
  9. gj10 python socket编程
  10. 3D UI场景中,把XY平面的尺寸映射为屏幕像素的数学模型推导