【LeetCode】Fraction to Recurring Decimal【Solution】

【テーマ】
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)".
【題意】
分子と分母を指定し、文字列として小数を返します.小数無限ループの場合は、カッコでループ体を拡張します.
【公式ソリューション】

    0.16  
6 ) 1.00
    0 
    1 0       <-- Remainder=1, mark 1 as seen at position=0.
    - 6 
      40      <-- Remainder=4, mark 4 as seen at position=1.
    - 36 
       4      <-- Remainder=4 was seen before at position=1, so the fractional part which is 16 starts repeating at position=1 => 1(6).

The key insight here is to notice that once the remainder starts repeating, so does the divided result.
You will need a hash table that maps from the remainder to its position of the fractional part. Once you found a repeating remainder, you may enclose the reoccurring fractional part with parentheses by consulting the position from the table.
The remainder could be zero while doing the division. That means there is no repeating fractional part and you should stop right away.
Just like the question Divide Two Integers, be wary of edge case such as negative fractions and nasty extreme case such as  -2147483648 / -1 .
【中国語解析】
難点:どのように循環体を識別しますか?
解決方法:1つのHashMapで各剰余を記録し、重複する剰余が現れると循環に入り、2つの重複する剰余の間の部分が循環体になる.
例:1/13=0.07692307169230769923...、小数部が2回目に0が現れると、ループが開始することを意味し、076923を括弧で囲む必要があり、結果は0である.(076923).
テクニック:1)絶えず除去する過程で、残数に10を乗じて次の除去を行い、ずっと整数で除去することを保証する.2)HashMapのkeyとvalueはそれぞれ<現在の残高、対応する結果の下付き>であり、076923を取得するとvalue値に基づいて探すことができる.
注意点1:正負数を考慮し、まず記号を判断し、それから正数に変換する.
注意点2:入力がIntegerの場合、オーバーフローを考慮する.MIN_VALUE、絶対値を取るとオーバーフローします.
コードにコメントが追加されました.コードを見てください.

public class Solution {
    public String fractionToDecimal(int numerator, int denominator) {
        if (numerator == 0) return "0";
        if (denominator == 0) return "";
        
        String ans = "";
        
        //       
        if ((numerator < 0) ^ (denominator < 0)) {
            ans += "-";
        }
        
        //            ，     ，int  long
        long num = numerator, den = denominator;
        num = Math.abs(num);
        den = Math.abs(den);
        
        //       
        long res = num / den;
        ans += String.valueOf(res);
        
        //      ，    
        long rem = (num % den) * 10;
        if (rem == 0) return ans;
        
        //       
        HashMap<Long, Integer> map = new HashMap<Long, Integer>();
        ans += ".";
        while (rem != 0) {
            //            ，        
            if (map.containsKey(rem)) {
                int beg = map.get(rem); //        
                String part1 = ans.substring(0, beg);
                String part2 = ans.substring(beg, ans.length());
                ans = part1 + "(" + part2 + ")";
                return ans;
            }
            
            //     
            map.put(rem, ans.length());
            res = rem / den;
            ans += String.valueOf(res);
            rem = (rem % den) * 10;
        }
        
        return ans;
    }
}

Javaプログラミングエラー:必ずintをlongに変換してから絶対値を取ります.long num=Mathと書くと.abs(numerator)では問題があります.このコードはnumerator=Integerにあるからです.MIN_VALUEの場合long num=Mathに相当する.abs(−2174483648)は、numが−2174483648である.
参照元1:http://www.cnblogs.com/ganganloveu/p/4170601.html
参照元2:https://oj.leetcode.com/discuss/18780/my-java-solution-with-explanation-second-version