题目：
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.
For example,
- Given numerator = 1, denominator = 2, return "0.5".
- Given numerator = 2, denominator = 1, return "2".
- Given numerator = 2, denominator = 3, return "0.(6)".
链接： http://leetcode.com/problems/fraction-to-recurring-decimal/
题解：
这道题基本就是Divide Two Integers + 处理循环小数。一刷的时候果断放弃了，因为不想处理恶心的边界条件，不在一开始把int转为long的话后面会很难写。现在又看了一遍大家的答案，发现绝大多数是先把int转为long，我也就放心了。实在不行咱可以用Python写这个。
Java:
Time Complexity - O(n)， Space Complexity - O(n)
public class Solution {
public String fractionToDecimal(int numerator, int denominator) {
if (numerator == 0) return "0";
if (denominator == 0) throw new ArithmeticException();
boolean sameSign = (numerator > 0) ^ (denominator < 0);
long dividend = Math.abs((long)numerator);
long divisor = Math.abs((long)denominator);
String intPart = String.valueOf(dividend / divisor);
intPart = sameSign ? intPart : "-" + intPart;
long remainder = dividend % divisor;
if (remainder == 0) return intPart;
Map<Long, Integer> map = new HashMap<>();
StringBuilder decimalPart = new StringBuilder();
while (remainder != 0) {
map.put(remainder, decimalPart.length());
remainder *= 10;
decimalPart.append(remainder / divisor);
remainder = remainder % divisor;
if (map.containsKey(remainder)) {
decimalPart.insert(map.get(remainder), "(");
decimalPart.append(')');
break;
}
}
return intPart + "." + decimalPart.toString();
}
}
二刷:
一样的方法，一样的code，写起来还是很吃力，多多练习吧。
Java:
public class Solution {
public String fractionToDecimal(int numerator, int denominator) {
if (numerator == 0) return "0";
if (denominator == 0) throw new ArithmeticException("Divide by zero");
boolean sameSign = (numerator > 0) ^ (denominator < 0);
long dividend = Math.abs((long)numerator);
long divisor = Math.abs((long)denominator);
StringBuilder sb = new StringBuilder();
if (!sameSign) sb.append("-");
sb.append(dividend / divisor);
dividend %= divisor;
if (dividend == 0) return sb.toString();
sb.append(".");
Map<Long, Integer> map = new HashMap<>();
while (dividend != 0) {
map.put(dividend, sb.length());
dividend *= 10;
sb.append(dividend / divisor);
dividend %= divisor;
if (map.containsKey(dividend)) {
sb.insert(map.get(dividend), "(");
sb.append(")");
return sb.toString();
}
}
return sb.toString();
}
}
Test Cases:
- (1, 3)
- (1, 5)
- (1, 6)
- (1, 90)
- (1, 99)
- (22, 7)
- (-50, 8)
- (0, -5)
- (-1, -2147483648)
- (-2147483648, 1)
Reference：
https://leetcode.com/discuss/18731/accepted-cpp-solution-with-explainations
https://leetcode.com/discuss/18769/there-good-deal-with-extreme-edge-case-without-converting-long
https://leetcode.com/discuss/18989/online-judge-pass-java-version
https://leetcode.com/discuss/20515/my-java-solution
https://leetcode.com/discuss/22652/do-not-use-python-as-cpp-heres-a-short-version-python-code
https://leetcode.com/discuss/23079/my-clean-java-solution
https://leetcode.com/discuss/31521/short-java-solution
https://leetcode.com/discuss/42159/0ms-c-solution-with-detailed-explanations
https://leetcode.com/discuss/50512/accepted-clean-java-solution
http://gqqnbig.me/?p=160
http://blog.csdn.net/hanshileiai/article/details/8861376
http://segmentfault.com/q/1010000003958185
https://leetcode.com/discuss/8886/my-simple-solution
http://blog.csdn.net/ljiabin/article/details/42025037