字符串形式返回小数

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

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

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

• -231 <= numerator, denominator <= 231 - 1
• denominator != 0

class Solution {
public:
    string fractionToDecimal(int numerator, int denominator) {
        if (numerator == 0) return "0"; // 特殊情况：分子为0
        string result;
        
        if ((numerator < 0) ^ (denominator < 0)) result += "-"; // 处理符号,判断分子和分母是否符号相反
        
        // 转换为长整型，处理溢出
        long num = labs(numerator);
        long den = labs(denominator);

        result += to_string(num / den); // 先添加整数部分

        long remainder = num % den; //通过取余操作 num % den 计算余数
        if (remainder == 0) return result; // 如果没有小数部分，直接返回结果
        
        result += "."; // 添加小数点
        unordered_map<long, int> map; // 用于记录余数及其对应的小数位索引
        map[remainder] = result.size(); // 记录余数的位置
        
        while (remainder != 0) {
            remainder *= 10; // 处理下一位
            result += to_string(remainder / den); // 获取当前位
            remainder %= den; // 更新余数
            
            if (map.find(remainder) != map.end()) { // 检测循环
                // 找到循环
                result.insert(map[remainder], "("); // 在循环开始的位置插入 "("
                result += ")"; // 添加 ")"
                break;
            }
            map[remainder] = result.size(); // 记录当前余数的位置
        }
        
        return result;
    }
};

unordered_map<long, int> map;是一个哈希表数据结构，它通过键值对的形式存储数据，键为 long 类型，值为 int 类型。

map[remainder] = result.size(); 将当前的余数 remainder 和当前的结果字符串 result 的长度存储到 map 中。

if (map.find(remainder) != map.end()).find() 将返回一个 迭代器，指向该余数在 map 中的位置。返回 map.end() 时，意味着 remainder 在 map 中不存在，即该余数还没有出现过。

假设我们在计算 4 / 333，余数为 4。

1. 第一步：

   • remainder = 4
   • remainder *= 10 → remainder = 40
   • 40 / 333 = 0，所以 result 添加 "0"，结果变为 "0.0"
   • remainder %= 333 → remainder = 40

2. 第二步：

   • remainder = 40
   • remainder *= 10 → remainder = 400
   • 400 / 333 = 1，所以 result 添加 "1"，结果变为 "0.01"
   • remainder %= 333 → remainder = 67

3. 第三步：

   • remainder = 67
   • remainder *= 10 → remainder = 670
   • 670 / 333 = 2，所以 result 添加 "2"，结果变为 "0.012"
   • remainder %= 333 → remainder = 4

4. 第四步：

   • 余数再次变为 4，说明出现循环，此时可以插入括号表示循环部分，结果变为 "0.(012)"。