题目

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

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

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

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

示例 1：

输入：numerator = 1, denominator = 2 输出："0.5"

示例 2：

输入：numerator = 2, denominator = 1 输出："2"

示例 3：

输入：numerator = 4, denominator = 333 输出："0.(012)"

提示：

-2^31 <= numerator, denominator <= 2^31 - 1
denominator != 0

解题思路

整体框架

处理特殊情况和符号：先处理掉一些简单和边缘的情况。
计算整数部分：将被除数和除数相除得到整数部分。
计算小数部分：模拟长除法，并检测循环。

详细步骤

1. 预处理：处理符号和边界情况

零分子：如果 numerator 为 0，结果直接就是 "0"。
符号：最终结果的符号由 numerator 和 denominator 的符号决定。可以先判断最终结果是否为负数（当两者异号时），然后将 numerator 和 denominator 都转为绝对值进行后续计算。这样可以简化问题，只需处理正数除法，最后根据之前记录的符号决定是否添加负号 "-"。

2. 计算整数部分

这部分很简单，直接做整除运算：integer_part = abs(numerator) // abs(denominator)。
计算出用于小数部分计算的初始余数：remainder = abs(numerator) % abs(denominator)。
将整数部分转换成字符串，作为结果字符串的开头。
如果余数 remainder 为 0，说明可以整除，没有小数部分。直接返回整数部分的字符串即可。

3. 计算小数部分

如果初始余数不为 0，说明有小数部分。

在结果字符串后面拼接上小数点 .。
如何模拟长除法？
- 我们每次将当前的 余数乘以 10，然后用这个新数去除以分母 denominator。
- 得到的商就是小数部分的下一位数字。
- 得到的 新余数 用于下一次计算。
- 重复这个过程，直到余数为 0。
如何检测循环？
- 核心思想：当同一个余数第二次出现时，就意味着计算过程进入了循环。因为从这个余数开始，后续计算出的商和小数位将会和第一次出现该余数时完全一样。
- 实现方法：我们需要一个数据结构来记录出现过的余数以及它出现时在小数部分的位置（索引）。哈希表（HashMap 或 Python 中的字典） 是完美的选择。
  - 键 (Key)：出现过的余数 remainder。
  - 值 (Value)：该余数对应的小数位在结果字符串中的索引 index。
算法流程：
1. 初始化一个空的哈希表 remainder_map。
2. 进入一个循环，循环条件是 remainder != 0。
3. 在循环内部，首先检查当前的 remainder 是否已经存在于哈希表的键中：
  - 如果存在：说明找到了循环节。循环的起始位置就是哈希表中记录的该 remainder 对应的索引。我们在这个索引位置插入一个左括号 (，并在字符串末尾追加一个右括号 )，然后结束循环并返回结果。
  - 如果不存在：说明这是一个新的余数。我们将当前的 remainder 和它对应的小数位在结果字符串中的索引存入哈希表：remainder_map[remainder] = current_index。然后继续进行长除法模拟： a. remainder = remainder * 10 b. digit = remainder // denominator (计算出小数位) c. remainder = remainder % denominator (更新余数) d. 将 digit 拼接到结果字符串的末尾。
4. 如果循环正常结束（即 remainder 变成了 0），说明这是一个有限小数，此时结果字符串已经构建完毕，直接返回即可。

具体代码

class Solution {
public:
    string fractionToDecimal(int numerator, int denominator) {
        // 1. 处理分子为 0 的特殊情况
        if (numerator == 0) {
            return "0";
        }

        string res;

        // 2. 处理符号
        // 使用异或(^)判断符号是否不同，不同则为负数
        if ((numerator > 0) ^ (denominator > 0)) {
            res += "-";
        }

        // 3. 将分子分母转为 long long 并取绝对值，防止溢出
        long long num = abs((long long)numerator);
        long long den = abs((long long)denominator);

        // 4. 计算整数部分
        res += to_string(num / den);
        long long remainder = num % den;

        // 5. 如果余数为0，说明可以整除，直接返回结果
        if (remainder == 0) {
            return res;
        }

        // 6. 处理小数部分
        res += ".";
        
        // 使用哈希表记录出现过的余数及其在结果字符串中的位置
        unordered_map<long long, int> remainder_map;

        while (remainder != 0) {
            // 检查当前余数是否已出现过
            if (remainder_map.count(remainder)) {
                // 如果余数重复出现，说明找到了循环节
                // 在循环开始的位置插入左括号，在字符串末尾追加右括号
                int pos = remainder_map[remainder];
                res.insert(pos, "(");
                res += ")";
                break; // 结束循环
            }

            // 记录当前余数和它对应的位置（即当前结果字符串的长度）
            remainder_map[remainder] = res.length();

            // 模拟长除法：余数乘以10，然后继续除
            remainder *= 10;
            
            // 将计算出的商（小数的一位）追加到结果中
            res += to_string(remainder / den);
            
            // 更新余数
            remainder %= den;
        }

        return res;
    }
};

166. 分数到小数

beautifulremi

题目