【Leetcode刷题记录】166. 分数到小数

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

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

如果存在多个答案，只需返回 任意一个 。

对于所有给定的输入，保证 答案字符串的长度小于 104 。

首先要明确两个数相除的结果肯定是整数，有限小数，或无限循环小数。那么可以通过模拟手动除法，也就是竖式除法的过程来求解这道题。手动除法的过程就是不断对余数补0，再重新计算余数和除数的新余数，由于我们一直是对余数进行补0操作，那么如果出现了相同的余数，就说明产生了循环小数。

解题步骤如下：

1. 处理符号：
   • 首先确定结果的符号。如果分子和分母的符号不同，结果为负数；否则为正数。
   • 将分子和分母都转换为绝对值，方便后续计算。
2. 计算整数部分：
   • 使用整数除法计算整数部分，即 numerator // denominator。
   • 将结果存入字符串res中。
3. 计算小数部分：
   • 使用取余运算 numerator % denominator 得到余数。
   • 如果余数为0，说明结果是整数或有限小数，直接返回结果。
   • 如果余数不为0，开始模拟除法过程：
     • 初始化一个哈希表 remainder_map，用于记录余数出现的位置。
     • 循环处理余数，直到余数为0或发现循环：
       • 将余数乘以10，得到新的被除数。
       • 计算新的商，即 new_numerator // denominator，并将其添加到 res 中。
       • 计算新的余数，即 new_numerator % denominator。
       • 如果余数已经存在于 remainder_map 中，说明出现了循环，获取余数第一次出现的位置，利用字符串截取和拼接操作返回题目要求的格式。
       • 否则，将余数和当前位置存入 remainder_map 中。

代码

string fractionToDecimal(int numerator, int denominator) {
    string res;
    long a = numerator, b = denominator;
    if (a % b == 0) {
        res += to_string(a / b);
        return res;
    }
    if (a * b < 0) {
        res.push_back('-');
    }
    a = abs(a), b = abs(b);
    res += to_string(a / b) + ".";
    a %= b;
    unordered_map<long, int> mp;
    while (a != 0) {
        mp[a] = res.length();
        a *= 10;
        res += to_string(a / b);
        a %= b;
        if (mp.find(a) != mp.end()) {
            int u = mp[a];
            return res.substr(0, u) + "(" + res.substr(u) + ")";
        }
    }
    return res;
}