166. Fraction to Recurring Decimal

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.

Example 1:

Input: numerator = 1, denominator = 2
Output: "0.5"

Example 2:

Input: numerator = 2, denominator = 1
Output: "2"

Example 3:

Input: numerator = 2, denominator = 3
Output: "0.(6)"

---

本题要把两数相除的结果转换为小数字符串，对于无限循环小数，把循环部分用括号括起来。 参考欣欣的做法。 首先判断一下符号位，如果异号则添加负号，然后把两数都转换为正数，注意因为int的负数个数比正数个数多一个-2147483648，abs(-2147483648)=-2147483648还是负数，因为int最大的正数是2147483647，导致转换为正数时溢出成-2147483648。所以需要先把分子分母转换为long long再取绝对值。

整数部分就是分子除以分母。如果没有余数，就整除了，直接返回结果；否则添加小数点，开始处理小数部分。小数部分判断是否有无限循环小数周期的方法是，用一个map保留每次除法的余数，以及对应的商在结果字符串中的位置，如果以后某次的余数在这个map中，就表明小数部分要开始循环了，通过map找到循环的起始位置，添加左括号，并在结果字符串末尾添加有括号就结束了。比如4/9，用长除法，第一次上0，添加小数点，余数为4。余数乘10再除以9，即40/9=4，余数还是4，因为之前有出现过4的余数，所以开始循环了。 有些除法能除尽，除尽的标志就是余数为0，所以也需要在循环的时候判断余数是否为0。 需要注意的一点是，不能对商建立hash表，比如某个小数是3.(5883)，循环周期是5883，如果对商建立hash，则出现第二个8时，会误以为开始循环周期了，导致结果3.5(8)，而正确的循环周期应该是5883。正确的做法是对余数建立hash表。 完整代码如下：

class Solution {
public:
    string fractionToDecimal(int numerator, int denominator)
    {
        if (numerator == 0)
            return "0";
        string ans = "";
        if ((numerator < 0) ^ (denominator < 0))
            ans = "-";
        long long num = llabs((long long)numerator), denom = llabs((long long)denominator);
        ans += to_string(num / denom);
        if (num % denom == 0)
            return ans;
        ans += ".";
        unordered_map<int, int> hash;
        long long reminder = num % denom;
        while (hash.find(reminder) == hash.end()) {
            hash[reminder] = ans.size();
            reminder *= 10;
            ans += to_string(reminder / denom);
            reminder %= denom;
            if (reminder == 0)
                return ans;
        }
        ans.insert(hash[reminder], "(");
        ans += ")";
        return ans;
    }
};

本代码提交AC，用时3MS。

二刷。相同思路：

class Solution {
public:
	string fractionToDecimal(int num, int denom) {

		long long numerator = num, denominator = denom;

		if (numerator == 0)return "0";
		if (denominator == 1)return to_string(numerator);
		if (denominator == -1)return to_string(-numerator);

		bool pos = true;
		if (numerator < 0) {
			numerator = -numerator;
			pos = !pos;
		}
		if (denominator < 0) {
			denominator = -denominator;
			pos = !pos;
		}

		unordered_map<int, int> hash;
		hash[numerator] = 0;
		vector<int> ans;
		
		int rep_start = -1;
		while (true) {
			int div = numerator / denominator;
			ans.push_back(div);
			numerator -= div * denominator;
			if (numerator == 0)break;
			numerator *= 10;
			if (hash.find(numerator) != hash.end()) {
				rep_start = hash[numerator];
				break;
			}
			else {
				hash[numerator] = ans.size();
			}
		}

		string frac = pos ? "" : "-";
		if (ans.size() == 1) {
			return frac + to_string(ans[0]);
		}
		frac += (to_string(ans[0]) + ".");
		for (int i = 1; i < ans.size(); ++i) {
			if (i == rep_start)frac += "(";
			frac += to_string(ans[i]);
		}
		if (rep_start >= 0)frac += ")";
		return frac;
	}
};

本代码提交AC，用时4MS。