Fraction to Recurring Decimal | LeetCode

166. Fraction to Recurring Decimal

Question Total Accepted: 24549  Total Submissions: 172168  Difficulty: Medium

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)".

Credits:

Special thanks to @Shangrila for adding this problem and creating all test cases.

好久之前做過，當時出的問題挺大的。今兒再來一遍鞏固一下，首先我們需要把結果分成兩部分，一個integer  part，一個

class Solution {
public:
	string fractionToDecimal(int numerator, int denominator) {
		unordered_map<int, int> map;

		//if there is only interpart
		long interpart = long(numerator) / denominator;
		long remainder = long(numerator) % denominator;
		if (remainder == 0) {
			return to_string(interpart);
		}

		//get denominator part
		string result = ((numerator < 0) ^ (denominator < 0))?"-"+to_string(abs(interpart)):to_string(abs(interpart));
		string deci = ".";
		long de = long(denominator);
		if (remainder < 0) remainder = -remainder;
		if (de < 0) {de = -de;};

		int idx = 1;
		while (remainder) {
			if (map.find(remainder) != map.end()) {
				int start = map[remainder];
				deci.insert(start, "(");
				deci.push_back(')');
				result += deci;
				return result;
			}
			map[remainder] = idx;
			remainder *= 10;
			deci += to_string(remainder / de);
			remainder = remainder % de;
			idx++;
		}
		result = result + deci;
		return result;
	}
};
           

decimal part. inter part直接nominator/denominator 就能出來。關鍵是小數部分。用一個hashmap來存儲，每一步的餘數。如果餘數出現重複，則出現循環。 注意幾點： 1. 正數和負數，可以用xor ^ 來判斷。 2. INT_MIN 前面加符号得到的還是他本身！！！！！！-INT_MINT == INT_MIN!! 這點找了半天，心好累 3. 沒了