leetcode：166. 分数到小数

题目

给定两个整数，分别表示分数的分子 numerator 和分母 denominator，以 字符串形式返回小数 。
如果小数部分为循环小数，则将循环的部分括在括号内。
如果存在多个答案，只需返回 任意一个 。
对于所有给定的输入，保证 答案字符串的长度小于 10^4 。

示例：

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

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

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

解答 & 代码

模拟
注意处理负数、整数部分等

class Solution {
public:
    string fractionToDecimal(int numerator, int denominator) {
        // 哈希表，存储 <余数，出现该余数对应的下标>
        unordered_map<int, int> map;
        // 得到最终结果的符号位
        char sign = '+';
        if((numerator > 0 && denominator < 0) || (numerator < 0 && denominator > 0))
            sign = '-';
        // 将分子、分母都用 long 表示，再变为正数（否则负数变正数可能会溢出）
        long numeratorL = numerator;
        numeratorL = numeratorL > 0 ? numeratorL : -numeratorL;
        long denominatorL = denominator;
        denominatorL = denominatorL > 0 ? denominatorL : -denominatorL;
        string result = "";        // 结果
        if(sign == '-')            // 如果结果是负数，则先加上负号
            result += '-';
        // 先得到结果的整数部分
        result += to_string(numeratorL / denominatorL);
        // 如果结果就是整数，则直接返回结果
        if(numeratorL % denominatorL == 0)
            return result;
        // 给结果的整数部分后面加上小数点
        result.push_back('.');
        // 将整数部分除法的余数先存入哈希表，下标存的是小数点的位置
        // 因为如果后续这个余数重复，循环小数的左括号加在小数点后面
        map[numeratorL % denominatorL] = result.size() - 1;
        numeratorL = numeratorL % denominatorL * 10;
        int idx = result.size();
        int start = -1;        // 第一个重复余数的下标，start + 1 是循环小数左括号的位置
        int end = -1;        // 第一个重复元素第二次出现的下标，end + 2 是循环小数右括号的位置（因为先插入了左括号）
        while(true)
        {
            // 计算当前位的结果
            result += numeratorL / denominatorL + '0';
            // 如果余数为 0，则结束循环
            if(numeratorL % denominatorL == 0)
                break;
            // 如果当前余数之前出现过，则记录两次出现的位置，并结束循环
            if(map.find(numeratorL % denominatorL) != map.end())
            {
                start = map[numeratorL % denominatorL];
                end = idx;
                break;
            }
            else    // 否则，将当前的余数及下标存入哈希表
                map[numeratorL % denominatorL] = idx;
            // 余数乘 10 作为下一轮除法运算的分子
            numeratorL = numeratorL % denominatorL * 10;
            ++idx;
        }
        // 如果结果是循环小数，插入左括号和右括号
        if(start != -1)
        {
            result.insert(start + 1, "(");
            result.insert(end + 2, ")");
        }
        return result;
    }
};

复杂度分析：

时间复杂度 O()：
空间复杂度 O()：

执行结果：

执行结果：通过
执行用时：0 ms, 在所有 C++ 提交中击败了 100.00% 的用户
内存消耗：6 MB, 在所有 C++ 提交中击败了 98.80% 的用户

hot 100

[中等] 166. 分数到小数

题目

解答 & 代码