166. Fractions to decimals

Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”

Given two integers that represent the numerator and denominator of a fraction, respectively, return a decimal as a string.

If the decimal part is a repeating decimal, enclose the repeating part in parentheses.

If more than one answer exists, just return any one.

Ensure that the answer string is less than 104 in length for any given input.

Example 1:

Input: numerator = 1, denominator = 2 output: “0.5”

Example 2:

Input: numerator = 2, denominator = 1 output: “2”

Example 3:

Denominator = 2, denominator = 3 output: “0.(6)”

Example 4:

Denominator = 4, denominator = 333 output: “0.(012)”

Example 5:

Input: numerator = 1, denominator = 5 output: “0.2”

Their thinking

To simulate long division, use map to record where the remainder occurs. Once the same remainder occurs, it indicates that the loop is followed by parentheses.

Minimum negative numbers overflow when they turn positive, so use long to catch them

code

class Solution {
    public String fractionToDecimal(int num, int de) {

        if(num==0) return "0";
        StringBuilder sb=new StringBuilder();
        if(num<0^de<0)
            sb.append(The '-');
        long numL=Math.abs(Long.valueOf(num));
        long deL=Math.abs(Long.valueOf(de));
        sb.append(numL/deL);
        long re=numL%deL;
        if(re==0)
            return sb.toString();
        sb.append('. ');
        HashMap<Long,Integer> map=new HashMap<>();
        while(re! =0)
        {
            if(map.containsKey(re))
            {
                sb.insert(map.get(re), "(");
                sb.append(') ');
                return sb.toString();
            }
            map.put(re,sb.length());
            re*=10;
            sb.append(String.valueOf(re/deL));
            re=re%de;
        }
        returnsb.toString(); }}Copy the code

Time complexity: O(len), where len is the length of the answer string, in this case len<=10000. For each character in the answer string, the computation time is O(1).
Space complexity: O(len), where len is the length of the answer string, in this case len<=10000. The space complexity depends primarily on the answer string and the hash table, where each key-value pair has a different subscript, so the number of key-value pairs cannot exceed len.

166. Fractions to decimals