这个题好贱,二刷的时候就有一刷的印象,记得改来改去各种CASE。
果不其然。
除法就不说了,主要就是出现无限循环的时候,如何判定哪些是循环的。
我们有的信息就是 被除数 除数 商 余数
通过商来判断开始无限循环是不显示的,结果可能是0.1111111111111111111,商一直是1。
通过除数来判断也不现实,类似于12458之类的只能让你判断是否能整除。
通过被除数判断,你也真是牛逼了。。
最后就剩余数了。1/3每次都是10/3,给的例子4/333会发现rem会重复出现,那我们就可以他通过是否有重复的REM出现来判断是否循环。
判断重复就是SET,我一开始用的SET,后面发现还需要知道在哪开始重复的,就改成MAP了。
先算整数部分,算完改String。
如果还有余数,开是构建MAP。
每有一个rem出现,map.put(rem,index),INDEX是小数点后第几位。
能整除最好。不能展出会出现REM,此时通过map.get(rem)找到小数点后某一位,这一位之前直接添加,之后加到一个括号里再添到前面的结果,就OK了。
题里说EDGE CASE很多,也有印象,但是确实没想到这么多,比如整除就没有小数点。
再比如正负问题,得标记正负,然后分子分母都取绝对值。
这个时候才发现设置TEST CASE的人的处心积虑,素质好差,愣是设置了个-2147483648,取绝对值变正,卧槽,出错了。。
倒霉了,所有INT都要改成LONG了,重头又改了一遍。。。
最终也就这么AC了。
public class Solution
{
public String fractionToDecimal(int numerator, int denominator)
{
long up = (long)numerator;
long down = (long) denominator;
boolean pos = (up*down)>=0? true:false;
up = Math.abs(up);
down = Math.abs(down);
if(up == 0) return "0";
String res = "";
if(up/down >=1) res += Long.toString(up/down) + ".";
else res += "0.";
up %= down;
if(up == 0)
{
res = res.substring(0,res.length()-1);
if(!pos) res = "-" + res;
return res;
}
long rem = up;
Map<Long,Integer> map = new HashMap<Long,Integer>();
int index = 0;
String right = new String();
while(rem != 0)
{
if(map.containsKey(rem)) break;
map.put(rem,index++);
rem *= 10;
right += Long.toString(rem/down);
rem %= down;
}
if(rem == 0) res += right;
else
{
res += right.substring(0,map.get(rem)) + "(" + right.substring(map.get(rem)) + ")";
}
if(!pos) res = "-" + res;
return res;
}
}