My java solution


  • 3

    basic idea:

    1. for the input integer: positive and negative number matters? => yes, so check the sign first

    2. can get integer part directly by a/b, then deal with decimal part

    3. get remainder by a%b. the problem is: how to check the decimal part is repeated (or not)?

    4. for each loop, we can get the digit by remainder10/b and update new remainder=remainder10%b, if we get the same remainder again, previous result is repeated

    5. so, use a set to store the remainder(s) that already appeared and use queue to store int sequence that need to append to res

    6. check remainder for each loop, if 0, poll all elem in queue, if set contains the remainder (q...)

    7. but... the question comes again: example, if result is 0.123454545 or 1/7 = 0.123454545, need a parameter to store which digit the res starts to repeat.. extra info is needed when we store the remainder to "locate" its position

    8. back to step 5, define the map instead of set to store <remainder, position> position=i (each loop i++)

    9. at last, check the remainder to know whether it's belong to "recurring" result or not

        public static String fractionToDecimal(int numerator, int denominator) {
    		String res = "";
    		long a = Math.abs((long) numerator);
    		long b = Math.abs((long) denominator);
    		if ((denominator < 0 && numerator > 0) || (denominator > 0 && numerator < 0)) {
    			res += "-";
    		}
    		long intPart= a / b;
    		res += intPart;
    		if (a % b == 0) {
    			return res;
    		}
    		res += ".";
    		long remainder = a % b;
    		HashMap<Long, Integer> map = new HashMap<Long, Integer>();
    		int i = 1;
    		map.put(remainder, 1);
    		Queue<Long> queue = new LinkedList<Long>();
    		int begin = -1;
    		while (remainder != 0) {
    			i++;
    			long tmp = remainder * 10 / b;
    			remainder = remainder * 10 % b;
    			if (map.containsKey(remainder)) {
    				begin = map.get(remainder);
    				queue.offer(tmp);
    				break;
    			} else {
    				map.put(remainder, i);
    				queue.offer(tmp);
    			}
    		}
    		if (remainder == 0) {
    			while (!queue.isEmpty()) {
    				res += queue.poll();
    			}
    		} else {
    			int j = 1;
    			while (!queue.isEmpty()) {
    				long cur = queue.poll();
    				if (j != begin) {
    					res += cur;
    				} else {
    					res = res + "(" + cur;
    				}
    				j++;
    			}
    			res += ")";
    		}
    		return res;
    	}
    

    a little optimization can be done: define stringbuilder as the result


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.