[LeetCode]Fraction to Recurring Decimal

能表示成分数的都是有理数，都不会是无限不循环小数，所以一定可以表示整数，小数或者无限循环小数。前两种都好判断，余数为0的时候就代表除尽了。无限循环小数的话，是要用map记录之前出现过的余数和index，再出现的时候，我们就知道又要从这里开始循环了。线性时间和空间，代码如下：

	class Solution {
	public:
	string fractionToDecimal(int numerator, int denominator) {
	bool isNeg = numerator < 0 && denominator > 0 || numerator > 0 && denominator < 0;
	long n = numerator, d = denominator;
	n = abs(n);
	d = abs(d);
	long quotient = n / d, reminder = n % d, i = 0;
	if(!reminder)return isNeg? "-" + to_string(quotient): to_string(quotient);
	unordered_map<int, int> visited;
	string decimal = "";
	while(reminder)
	{
	if(visited.find(reminder) != visited.end())break;
	visited[reminder] = i++;
	reminder *= 10;
	int digit = reminder / d;
	reminder %= d;
	decimal += to_string(digit);
	}
	if(reminder)
	{
	int idx = visited[reminder];
	decimal = decimal.substr(0, idx) + "(" + decimal.substr(idx) + ")";
	}
	string res = to_string(quotient) + "." + decimal;
	return isNeg? "-" + res: res;
	}
	};

view raw Fraction to Recurring Decimal.cpp hosted with ❤ by GitHub