FractionToRecurringDecimal [source code]
public class FractionToRecurringDecimal {
static
/****************************************************************************/
class Solution {
public String fractionToDecimal(int numerator, int denominator) {
return divide (numerator, denominator);
}
public String divide (long numerator, long denominator) {
if (numerator == 0)
return "0";
if ((numerator > 0) ^ (denominator > 0))
return "-" + divide (Math.abs (numerator), Math.abs (denominator));
numerator = Math.abs (numerator);
denominator = Math.abs (denominator);
long cur = numerator;
StringBuilder sb = new StringBuilder ();
Map<Long, Integer> recur_start = new HashMap<> ();
while (cur > 0) {
if (recur_start.containsKey (cur)) {
int start_index = recur_start.get (cur);
sb.insert (start_index, "(").append (")");
break;
} else if (cur == 0) {
break;
} else {
recur_start.put (cur, sb.length ());
if (cur < denominator) {
sb.append ("0");
cur *= 10;
} else {
sb.append (cur / denominator);
cur = cur % denominator;
cur *= 10;
}
}
}
String res = sb.toString ();
int left_len = Long.toString (numerator / denominator).length ();
return left_len == res.length () ? res : (res.substring (0, left_len) + "." + res.substring (left_len));
}
}
/****************************************************************************/
public static void main(String[] args) {
FractionToRecurringDecimal.Solution tester = new FractionToRecurringDecimal.Solution();
String[] inputs = {
"1", "2", "0.5",
"2", "1", "2",
"2", "3", "0.(6)",
"4", "9", "0.(4)",
"4", "333", "0.(012)",
"0", "3", "0",
"-50", "8", "-6.25",
"-22", "-2", "11",
"-2147483648", "1", "-2147483648",
};
for (int i = 0; i < inputs.length / 3; i++) {
System.out.println (Printer.separator ());
int numerator = Integer.parseInt (inputs[3 * i]), denominator = Integer.parseInt (inputs[3 * i + 1]);
String ans = inputs[3 * i + 2], output = tester.fractionToDecimal (numerator, denominator);
System.out.printf ("%d / %d\n%s\n%s\n",
numerator, denominator, Printer.wrap (output, output.equals (ans) ? 92 : 91), ans
);
}
}
}
downvote有点高的一个题目, 大概写写看;
乍一看的话, 感觉难度应该是在判断是不是无限循环? 因为最后要求的输出是一个string, 所以最后的精度要求是完全的, 也就是一点都不能差, 不存在因为是浮点数所以只要误差在epsilon里面就行了的说法;
有没有可能最后得到的是一个无限不循环小数呢? 应该不会吧, 毕竟这种针对这个问题就无解了;
问题的难点是, 当你在不停的除的时候, 重复部分到底是从哪里开始你是不知道的: 无限循环小数的重复部分的开始未必就是小数点右边第一位;
另外除法本身估计不能直接利用java本身的除来做, 因为那个除好像是有一个精度限制, 意思也就是说最后实际上能够输出的小数点右边的digit数量是有限的; 这个肯定是不满足这个题目的要求的;
那么怎么做? 就跟拆分整数一样的做法自己一点一点的做? 这个应该是可行的;
完全没有思路的题目, 稍微瞄了一眼, hint很多(符合Google家的风格), 看一下;
第一个hint告诉你, 不要搞的太复杂, 最后不是纯math的解法应该也是可以AC的; hint1本身的内容讨论的就是我上面自己讲过的, 自己模拟除法的部分;
不对, 感觉hint1讲的更深, 应该是类似这个除法的过程?
有点不是很确定, 毕竟也不知道他们美国人自己的除法当时是怎么教的;
不过如果用我自己之前的拆分digit的思路, 模拟触发应该也是很简单的;
hint2好像就是开始给你实质性的解法的提示了;
刚开始我实际上是想了一会儿笨办法的, 一个办法就是自然的无限延长这个string, 比如0.512341234...这样的, 然后你的任务就是要找到(注意从具体的例子出发)1234实际上是一个重复部分; 这个东西最好是能够用O(1)的速度在每一个位置查询. 有没有办法做出一个类似2sum这样的高效历史信息流来维护这个查询信息的需求?
好像KMP可以?
KMP当时算LPS的过程非常类似这里这个解法; again, 很多刁钻的题目要求你自己定制化KMP, 大部分时候重要的你需要记忆的地方就是LPS的计算的这个代码, 而主循环(用来实现strStr的)未必是最有用的, 当然了, 你能够记得是最好的;
不对哦; LPS好像没有办法在这里用, 因为我们最后比如第二个1234, 你要查找到的是[1:]开始的第一个1234, 但是[0]=5这个你怎么办? LPS的使用, 好像一般是要始终能够从最开头来查询才行的, 包括计算的backup的过程, 也是不断向shorter prefix也就是开头的部分去缩进;
不乱想, 仔细看hint2讲的到底是什么:
这个好像是一个重要的提示, 好像是希望我们用简单的memo来完成这个查询的维护? 一旦当我们在某一个当前位置hit memo, 那么立刻就可以知道, 不用继续算了;
again, 我假设题目给的这些input, 最后对应的小数肯定都是无限循环小数; 不过真正Google面试这个的时候, 这种问题你就是应该自己去开口问: clarify;
大概有点思路, 这个时候, 除了上面说的memo(你实际上查询的是contains key), 还有一个需要维护的是, 比如4这个input, 对应的在最后的result string里面, start index是多少, 这样你知道你的左括号插入在哪里;
好像感觉这个时候基本有一个可以写出来的解法了;
干脆顺手把所有的hint都看完算了;
hint3就是我上面描述的算法的本身;
hint4就是Google特有的edge case多的东西; 那么基本就是我上面想的这个算法了;
暂时这么看起来好像还挺有意思的一个算法, 但是为什么题目最后downvote这么多? edge case很抠人? 先写写看再说;
写的时候还是用之前给的4/9和4/333这两个例子来帮助写代码;
不过这两个例子确实是比较典型的例子, 本来以为很复杂很多种情况, 这两个例子一给, 感觉general的solution其实是很好理解的;
题目给的提示是很多edge case, 那么立刻能想到的一个edge case就是, 万一最后实际上我们找的这个根本不是一个无限小数, 有没有可能?
这个对应的就是你当前的这个被除数算着算着变成了0, 所以主循环的header我感觉就可以用while不等于0这种来写;
刚开始写的时候实际上还没有把握之前描述的那两个历史信息要怎么维护; 我的想法是, 先把主要逻辑给写出来, 然后再把需要维护memo的代码给添加进去;
就跟你正常写recursion的时候的做法是一样的; 没有memo的版本先写出来, 然后最后memo的添加并不会给你带来多少额外的麻烦;
一开始我还准备专门处理一下最开始input分子比分母大的情况, 用一个conditional来处理(也可以用之前见过的recursion的思路来规整, 不过这里会麻烦一些):
StringBuilder sb = new StringBuilder ();
if (numerator >= denominator) {
sb.append (numerator / denominator);
numerator = numerator % denominator;
}
sb.append (".");
while {...}
不过后来发现这个逻辑完全跟主循环里面的逻辑是一样的, 没有必要分开专门处理;
反正最近没有面试了, 写代码也随便一点了, 暂时还没有加memo, 先跑两个test看看没有memo的代码对不对;
本来以为思路很清晰了, 不过最后实现的时候发现很多别别窍的地方相当多; 还在debug当中;
小数点问题比我想的要难解决不少, 感觉一个坑.
想了一下, 一个思路是, 干脆直接不急着一开始把小数点都放在那里, 因为其实小数点左边这个数字的计算方法和小数点右边的数字的计算方法并没有区别?
另外我现在的算法还有一个没有考虑到的地方就是, 如果小数点左边其实不止一位, 怎么办:
if (sb.length () == 1 && numerator > 0)
sb.append (".");
这个就是我现在判断小数点的逻辑, 明显是不合理的;
我想表达的意思是, 这个小数点的位置记录下来: 哪一个index对应的是第一个小数点右边的数字, 然后最后专门post-filter一下就行了;
debug过程当中再次意识到, 虽然以前证明什么的时候, 关注instance just before iteration更加的好, 但是实际上真正debug的时候, print的位置最好还是just after each iteration. 这个也是被证明了很多次的了; 不要跟自己的经验过不去;
当然最好的实际上还是把before和after的都print了是最好的; 这题其实我就是这样的, 只print某一个, 最后理解trace都有点麻烦;
然后从test5开始就慢慢理解为什么这题的downvote多了, 因为最后在input上面搞鬼的test相当多;
然后test9这个就相当恶心了, 我自己一开始代码判断是这样的:
if (numerator == 0)
return "0";
if ((numerator > 0) ^ (denominator > 0))
return "-" + fractionToDecimal (Math.abs (numerator), Math.abs (denominator));
numerator = Math.abs (numerator);
denominator = Math.abs (denominator);
...
当时在用abs的时候, 我感觉就可能会踩java abs的那个坑(负无穷的abs还是负无穷), 果然真的这里就用了这个. 有点恶心好吧;
而且真的要修改, 也没有什么特别优雅的代码来处理这个, 感觉只能很暴力的处理;
最后决定干脆就不用abs了, 反正正负情况只有四种, 直接暴力穷举, 算你狠;
不过负无穷到底怎么处理? 就算是暴力穷举正负情况, 好像也没有办法很好的处理, 因为负无穷你是无法在不溢出的情况下直接flip到正无穷的; 所以最后估计是只能借助于long?
java> long l = (long) Integer.MIN_VALUE;
long l = -2147483648;
java> Math.abs (l);
java.lang.Long res1 = 2147483648;
java> Math.abs (Integer.MIN_VALUE);
java.lang.Integer res2 = -2147483648;
最后终于是AC了...过了就行了, 不愧是Google早期的题目, 这些边界输入的检查太严厉了;
速度是7(15), 不算太差的那种;
虽然最后写完了, 但是这个代码其实写的并不轻松, 很多地方真的就是需要相当的代码熟练感觉, 才能快速的调整的. 如果是现场写这样的代码, 跪的可能性就相当大了;
总体来说我个人认为这个题目还是相当不错的一个题目的, 尤其是hint给的很有条理, 最后也能锻炼很多的思考过程;
最后这么多downvote, 我估计是各种恶心的input case的原因; 这个也是为什么后来LeetCode的新题, 基本上对于input都给了相当明确的界定;
不过真正面试的时候, 这些东西还是得自己去问, 所以只能说也是一个能力吧. 毕竟如果你不能意识到这种边界input的存在, 你也自然不会想到去问.
editorial
Approach #1 (Long Division) [Accepted]
意思就是input, 或者说分子, 决定了最后的输出, 所以一旦input开始重复了, 直接就知道我们的小数也已经开始重复了;
看他这里给的算式, 他的Map记录的好像是x10之前的那个remainder, 这个跟我有点区别, 不过估计影响不大?
nasty这个词用的就很到位了;
第二行那个, 分母为0, 其实我是想到了, 不过题目本身也没有给出明确的要求怎么处理这个异常, 所以我当时也就懒得处理了; 真正面试的时候肯定是要描述一下你准备怎么处理的: handle invalid input始终是一个很重要的课题;
第三行他的意思是, 对于没有小数部分, 也就是整除的, 他还专门一个特殊情况来handle; 我的就不是这样的, 我的算法是统一处理这个情况;
然后后面的负数处理就是最烦人的了;
public String fractionToDecimal(int numerator, int denominator) {
if (numerator == 0) {
return "0";
}
StringBuilder fraction = new StringBuilder();
// If either one is negative (not both)
if (numerator < 0 ^ denominator < 0) {
fraction.append("-");
}
// Convert to Long or else abs(-2147483648) overflows
long dividend = Math.abs(Long.valueOf(numerator));
long divisor = Math.abs(Long.valueOf(denominator));
fraction.append(String.valueOf(dividend / divisor));
long remainder = dividend % divisor;
if (remainder == 0) {
return fraction.toString();
}
fraction.append(".");
Map<Long, Integer> map = new HashMap<>();
while (remainder != 0) {
if (map.containsKey(remainder)) {
fraction.insert(map.get(remainder), "(");
fraction.append(")");
break;
}
map.put(remainder, fraction.length());
remainder *= 10;
fraction.append(String.valueOf(remainder / divisor));
remainder %= divisor;
}
return fraction.toString();
}
一开始为了记录这个Map的value, 我一开始还维护一个自增的pos, 后来发现根本没有必要, 反正记录的都是当前小数的最后位置, 所以直接用length就行了, 这个技巧在editorial的方法里面也见到了
然后负号处理, 你看他没有用recursion来出来input转换在这里; 这个我要稍微学习一下, 看起来这个recursion的input转换很多时候也是有坑的;
总体来说他这个代码最后写的比我简洁很多; 但是核心逻辑是类似的;
因为这题最后自己是做出来了的, 所以就不在看这个代码上面浪费太多时间了, 毕竟这个问题最后难点还是实现细节.
如果真正Google面试的时候看到这个题目, 先把核心逻辑快速写出来, 然后立刻几个test开始跑; 这题真的很容易一不小心就写错了, 比如我一开始连这个*=10居然都忘记写了;
https://leetcode.com/problems/fraction-to-recurring-decimal/discuss/51106/My-clean-Java-solution
The important thing is to consider all edge cases while thinking this problem through, including: negative integer, possible overflow, etc.
Use HashMap to store a remainder and its associated index while doing the division so that whenever a same remainder comes up, we know there is a repeating fractional part.
Please comment if you see something wrong or can be improved. Cheers!
public class Solution {
public String fractionToDecimal(int numerator, int denominator) {
if (numerator == 0) {
return "0";
}
StringBuilder res = new StringBuilder();
// "+" or "-"
res.append(((numerator > 0) ^ (denominator > 0)) ? "-" : "");
long num = Math.abs((long)numerator);
long den = Math.abs((long)denominator);
// integral part
res.append(num / den);
num %= den;
if (num == 0) {
return res.toString();
}
// fractional part
res.append(".");
HashMap<Long, Integer> map = new HashMap<Long, Integer>();
map.put(num, res.length());
while (num != 0) {
num *= 10;
res.append(num / den);
num %= den;
if (map.containsKey(num)) {
int index = map.get(num);
res.insert(index, "(");
res.append(")");
break;
}
else {
map.put(num, res.length());
}
}
return res.toString();
}
}
这个完全就是editorial的那个答案嘛.
几乎可以说是一模一样了, 除非最后一个while循环里面, 顺序有所更改, 不过整体基本是差不多; editorial那个写法好像稍微更整洁一些;
janos 17 February 12, 2015 8:25 AMReport
Great solution!You're reusing the variable num for the iterative calculation of the remainder. It would be better to introduce a remainder variable and use that instead, to make the code more clear:
long remainder = num % den;Instead of writing map.put twice, you could refactor the while loop to do it only once.
Also, instead of two lookups in the map with .containsKey and then .get,
you could use just one .get and do a null check:while (num != 0) { map.put(num, res.length()); num *= 10; res.append(num / den); num %= den; Integer remainderIndex = map.get(num); if (remainderIndex != null) { res.insert(remainderIndex, "("); res.append(")"); break; } }
一般性的意见, 大概看看就可以;
// upgraded parameter types
string fractionToDecimal(int64_t n, int64_t d) {
// zero numerator
if (n == 0) return "0";
string res;
// determine the sign
if (n < 0 ^ d < 0) res += '-';
// remove sign of operands
n = abs(n), d = abs(d);
// append integral part
res += to_string(n / d);
// in case no fractional part
if (n % d == 0) return res;
res += '.';
unordered_map<int, int> map;
// simulate the division process
for (int64_t r = n % d; r; r %= d) {
// meet a known remainder
// so we reach the end of the repeating part
if (map.count(r) > 0) {
res.insert(map[r], 1, '(');
res += ')';
break;
}
// the remainder is first seen
// remember the current position for it
map[r] = res.size();
r *= 10;
// append the quotient digit
res += to_string(r / d);
}
return res;
}
很厉害的一个妹子, 所以她的解法我也保存一下;
几乎是一模一样的解法都, 大概看看了; 好像cpp没有这个abs的问题, 所以他这里直接就用了?
bdeng3 5 October 12, 2017 6:24 PMReport
I encountered this question in my interview yesterday, and the interviewer asked me why I used int64_t in this question. In fact, if we changed int64_t into int, this answer won't get accepted. Any explanation?
所以实际上还是有这个溢出问题?
下套了:
pynoob 0 January 29, 2017 1:51 PMReport
Wondering if it is not possible to have a floating part as '1212312123'? In this case the repeating part will 12123 but the solution will take 12 as the repeating portion?csehaosh 34 January 29, 2017 7:35 PMReport
@pynoob No. The judgement is not based on repeating quotients, but on repeating reminders, 12 should come from different reminders,zkfairytale 511 December 16, 2014 10:03 AMReport
Thanks for your sharing. I rewrote your code into Java version.
public String fractionToDecimal(int numerator, int denominator) {
if (denominator == 0)
return "NaN";
if (numerator == 0)
return "0";
StringBuilder result = new StringBuilder();
Long n = new Long(numerator);
Long d = new Long(denominator);
// negative or positive
if (n*d < 0)
result.append("-");
n = Math.abs(n);
d = Math.abs(d);
result.append(Long.toString(n / d));
// result is integer or float
if (n % d == 0)
return result.toString();
else
result.append(".");
// deal with the float part
// key is the remainder, value is the start positon of possible repeat numbers
HashMap<Long, Integer> map = new HashMap<Long, Integer>();
Long r = n % d;
while (r > 0) {
if (map.containsKey(r)) {
result.insert(map.get(r), "(");
result.append(")");
break;
}
map.put(r, result.length());
r *= 10;
result.append(Long.toString(r / d));
r %= d;
}
return result.toString();
}
改写的又臭又长, 没仔细看了;
https://leetcode.com/problems/fraction-to-recurring-decimal/discuss/51140/Short-Java-solution
public String fractionToDecimal(int numerator, int denominator) {
StringBuilder result = new StringBuilder();
String sign = (numerator < 0 == denominator < 0 || numerator == 0) ? "" : "-";
long num = Math.abs((long) numerator);
long den = Math.abs((long) denominator);
result.append(sign);
result.append(num / den);
long remainder = num % den;
if (remainder == 0)
return result.toString();
result.append(".");
HashMap<Long, Integer> hashMap = new HashMap<Long, Integer>();
while (!hashMap.containsKey(remainder)) {
hashMap.put(remainder, result.length());
result.append(10 * remainder / den);
remainder = 10 * remainder % den;
}
int index = hashMap.get(remainder);
result.insert(index, "(");
result.append(")");
return result.toString().replace("(0)", "");
}
完全没有区别;
怎么感觉这题所有的解法都写的差不多; 难道是我自己异类了?
不对, 他while循环写的有点差别; 别人都是判断remainder > 0, 包括我自己也是判断的这个;
他这里判断的是不重复.
他这里对最后重复判断的处理是有点小聪明的, 我脑子里跑了一下1/2这个例子, 然后就知道他的把戏了, 他的while循环最后两个iteration, 第一个会把0给put到Map里面去, 然后第二个会因为0在里面, 所以直接terminate;
最后如果是1/2这样没有重复小数的情况, 直接最后会多一个(0)这样的东西; 他之所以这样处理是不希望while里面还和之前看到的大部分写法那样, 还专门多一个break出来(实际上判断的是不重复和不为0这两个terminate条件);
最后返回的时候, 如果有(0)(也就是实际上并没有重复小数部分), 直接删除就行了;
总体来说是有点小聪明的一个算法, 还行吧.
I don't understand why so many people tends to write "short" java solutions over "clear" java solution when performance stays the same.
In order to be a good teammate, one should always write clean code instead of hacky code if performance stays the same.
public String fractionToDecimal(int numerator, int denominator) {
boolean isNegative = (numerator < 0 && denominator > 0 || numerator > 0 && denominator < 0) ? true : false;
long numeratorL = Math.abs((long) numerator);
long denominatorL = Math.abs((long) denominator);
Map<Long, Integer> previousRemains = new HashMap<Long, Integer>();
StringBuilder sb = new StringBuilder();
long quotian = numeratorL / denominatorL;
sb.append(quotian);
numeratorL %= denominatorL;
if (numeratorL != 0) {
sb.append(".");
}
int quotianIndex = 0;
while (numeratorL != 0) {
numeratorL *= 10;
quotian = Math.abs(numeratorL / denominatorL);
if (!previousRemains.containsKey(numeratorL)) {
sb.append(quotian);
previousRemains.put(numeratorL, quotianIndex++);
} else {
int firstIndex = 1 + previousRemains.get(numeratorL) + sb.indexOf(".");
sb.insert(firstIndex, '(');
sb.append(")");
break;
}
numeratorL %= denominatorL;
}
if (isNegative) {
sb.insert(0, "-");
}
return sb.toString();
}
思路大体差不多, 一些小的改动, 比如他这里实际上为了Map, 维护了一个专门的pos; 然后对于负号的处理, 他最开始保存一个专门的flag(保存完了之后直接就可以把两个操作数都变成非负数了), 最后根据这个flag来处理一下最终结果, 这个实际上也是我自己想到了的技巧;
对于他反对short写法的观点, 我也是很认同, 说过很多次了;
submission: 5(30)
class Solution {
public String fractionToDecimal(int numerator, int denominator) {
// negative sign
boolean negative = (numerator < 0) ^ (denominator < 0);
long n = Math.abs((long)numerator);
long d = Math.abs((long)denominator);
long intPart = n / d;
long rest = n - intPart * d;
if (rest == 0) return negative ? String.valueOf(intPart * (-1)) : String.valueOf(intPart); // Integer result
StringBuilder res = new StringBuilder();
if (negative) res.append("-");
res.append(intPart);
res.append(".");
long slow;
long fast;
long[] temp = new long[2];
slow = Decimal(rest*10, d)[1];
fast = Decimal(Decimal(rest*10, d)[1], d)[1];
while (slow != fast) {
slow = Decimal(slow, d)[1];
fast = Decimal(Decimal(fast, d)[1], d)[1];
}
slow = rest * 10;
while (slow != fast && slow != 0) {
temp = Decimal(slow, d);
slow = temp[1];
res.append(temp[0]); // non-cycle part
fast = Decimal(fast, d)[1];
}
if (slow == 0) return res.toString(); // return when result is finite decimal
temp = Decimal(slow, d);
fast = temp[1];
res.append("(");
res.append(temp[0]);
while (slow != fast) {
temp = Decimal(fast, d);
fast = temp[1];
res.append(temp[0]); // cycle part
}
res.append(")");
return res.toString();
}
public long[] Decimal(long rest, long denominator) {
// return the quotient and remainder (multiplied by 10)
long r1;
long r2;
if (rest < denominator) {
r1 = 0;
r2 = rest * 10;
}
else {
r1 = rest / denominator;
r2 = (rest - denominator * r1) * 10;
}
return new long[]{r1, r2};
}
}
一顿操作猛如虎, 也没有快多少;
没有仔细看代码了, 看起来又是在搞一些造轮子的东西;
Problem Description
Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.
If the fractional part is repeating, enclose the repeating part in parentheses.
Example 1:
Input: numerator = 1, denominator = 2
Output: "0.5"
Example 2:
Input: numerator = 2, denominator = 1
Output: "2"
Example 3:
Input: numerator = 2, denominator = 3
Output: "0.(6)"
Difficulty:Medium
Total Accepted:66.1K
Total Submissions:362.4K
Contributor:Shangrila
Companies
googleixl
Related Topics
hash tablemath
- Hint 1: No scary math, just apply elementary math knowledge. Still remember how to perform a long division?
- Hint 2: Try a long division on 4/9, the repeating part is obvious. Now try 4/333. Do you see a pattern?
- Hint 3: Notice that once the remainder starts repeating, so does the divided result.
- Hint 4: Be wary of edge cases! List out as many test cases as you can think of and test your code thoroughly.