fraction-to-recurring-decimal

题目描述

给定两个整数，分别表示分数的分子 numerator 和分母 denominator，以字符串形式返回小数。

如果小数部分为循环小数，则将循环的部分括在括号内。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/fraction-to-recurring-decimal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

长除法，循环除法、取模直至余数为零。

特殊情况：被除数为0、最小负数除以-1会溢出、循环小数–需要用一个map来检查当前余数是否已经出现过，如果已经出现过，需要加括号。

string fractionToDecimal(int numerator, int denominator) {
	if (numerator == 0)return "0";
	string res = "";
	if ((numerator < 0) ^ (denominator < 0))res.append("-");
	long dividend = abs(numerator), divisor = abs(denominator), remainder = 0;
	res.append(to_string(dividend / divisor));
	remainder = dividend % divisor;
	if (remainder == 0)return res;
	unordered_map<long, int> map;
	res.append(".");
	while (remainder)
	{
		if (map.count(remainder))
		{
			int index = map[remainder];
			res.insert(index, "(");
			res.append(")");
			return res;
		}
		map[remainder] = res.length();
		remainder *= 10;
		res.append(to_string(remainder / divisor));
		remainder %= divisor;
	}
	return res;
}