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:

    1. Input: numerator = 1, denominator = 2
    2. Output: "0.5"

    Example 2:

    1. Input: numerator = 2, denominator = 1
    2. Output: "2"

    Example 3:

    1. Input: numerator = 2, denominator = 3
    2. Output: "0.(6)"

    题意

    计算一个分数表示的有理数的小数形式，若为无限循环小数，则将循环部分用括号标记。

    思路

    直接按照小学除法步骤进行模拟，判断出现循环的依据是计算过程中有余数出现了两次，利用Hash进行标记。

    代码实现

    1. class Solution {
    2.     public String fractionToDecimal(int numerator, int denominator) {
    3.         Map<Long, Integer> map = new HashMap<>();    // key为余数值，value为对应的小数位
    4.         StringBuilder sb = new StringBuilder();
    6.         // 先将分子分母全部转化为正数，并记录符号信息
    7.         // 因为最小负int取绝对值后会溢出，所以全用long来计算
    8.         boolean negative = numerator < 0 && denominator > 0 || numerator > 0 && denominator < 0;
    9.         long dividend = Math.abs((long) numerator), divisor = Math.abs((long) denominator);
    10.         long remainder = dividend % divisor, quotient = dividend / divisor;
    12.         sb.append(quotient);            // 将整数部分存入
    13.         // 仍有余数，说明存在小数部分
    14.         if (remainder != 0) {
    15.             sb.append(".");
    16.             // 余数最终为0，说明是有限小数，不为0则需要找到无限循环小数的循环部分
    17.             while (remainder != 0) {
    18.                 if (!map.containsKey(remainder)) {
    19.                     map.put(remainder, sb.length());
    20.                     quotient = remainder * 10 / divisor;
    21.                     remainder = remainder * 10 % divisor;
    22.                     sb.append(quotient);
    23.                 } else {
    24.                     sb.insert(map.get(remainder), "(");
    25.                     sb.append(')');
    26.                     break;
    27.                 }
    28.             }
    29.         }
    31.         return (negative ? "-" : "") + sb.toString();
    32.     }
    33. }