Alibi

My Life is Getting Better

Leetcode[166] Fraction to Recurring Decimal

14 Nov 2015

###Task1 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)”.

###Python

class Solution(object):
    def fractionToDecimal(self, numerator, denominator):
        """
        :type numerator: int
        :type denominator: int
        :rtype: str
        """
        res = ''
        if numerator == 0:
            return '0'
        if denominator == 0:
            return ''
        if (numerator < 0) ^ (denominator < 0):
            res += '-'
        num = abs(numerator)
        den = abs(denominator)
        res += str(num / den)
        rem = (num % den) * 10
        if rem == 0:
            return res
        dic = {}
        res += '.'
        while rem > 0:
            if rem in dic:
                pos = dic[rem]
                left = res[:pos - 1]
                right = res[pos - 1:]
                res = left + '(' + right + ')'
                return res
            res += str(rem / den)
            dic[rem] = len(res)
            rem = (rem % den) * 10
        return res

###Java

import java.util.*;

public class Solution {
    public String fractionToDecimal(int numerator, int denominator) {
        String result = "";
        if (denominator == 0) {
        	return result;
        }
        if (numerator == 0) {
        	return "0";
        }
        if (numerator < 0 ^ denominator < 0) {
        	result += "-";
        }

        long num = numerator;
        long den = denominator;
        num = Math.abs(num);
        den = Math.abs(den);

        long temp = num / den;
        result += String.valueOf(temp);
        long remainder = (num % den) * 10;
        if (remainder == 0) {
        	return result;
        }

        HashMap<Long, Integer> map = new HashMap<Long, Integer>();
        result += ".";
        while (remainder > 0) {
        	if (map.containsKey(remainder)) {
        		int pos = map.get(remainder);
        		String left = result.substring(0, pos - 1);
        		String right = result.substring(pos - 1, result.length());
        		result = left + "(" + right + ")";
        		return result;
        	}
        	temp = remainder / den;
        	result += String.valueOf(temp);
        	map.put(remainder, result.length());
        	remainder = (remainder % den) * 10;
        }

        return result;
    }

    public static void main(String[] args) {
    	Solution sol = new Solution();
    	System.out.println(sol.fractionToDecimal(0, -5));
    }
}

###Points

Related Posts