[LeetCode] 166、分数到小数

题目描述

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

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

示例：

输入: numerator = 2, denominator = 3
输出: "0.(6)"
           

解题思路

这道题其实就是模拟我们平时在纸上竖式计算的过程，其中一些问题要注意下：符号部分、整数部分/小数部分、溢出的问题等。

HashMap

来处理重复值的技巧，经常用到了。

测试样例	解释
0 1 \frac{0}{1} 10​	被除数为 0。
1 0 \frac{1}{0} 01​	除数为 0，应当抛出异常，这里为了简单起见不考虑。
20 4 \frac{20}{4} 420​	答案是整数，不包括小数部分。
1 2 \frac{1}{2} 21​	答案是 0.5，是有限小数。
− 1 4 \frac{-1}{4} 4−1​或 1 − 4 \frac{1}{-4} −41​	除数被除数有一个为负数，结果为负数。
− 1 − 4 \frac{-1}{-4} −4−1​	除数和被除数都是负数，结果为正数。
− 2147483648 − 1 \frac{-2147483648}{-1} −1−2147483648​	转成整数时注意可能溢出。

需要用一个哈希表记录余数出现在小数部分的位置（关键），当你发现已经出现的余数，就可以将重复出现的小数部分用括号括起来。

再出发过程中余数可能为 0，意味着不会出现循环小数，立刻停止程序。（小数部分如果“余数”重复出现就表示该小数是循环小数了）

就像两数相除问题一样（应该先做），主义考虑负分数以及极端情况，比如说 − 2147483648 − 1 \frac{-2147483648}{-1} −1−2147483648​。

参考代码

typedef long long LL;

class Solution {
public:
    //小数部分如果“余数”重复出现两次就表示该小数是循环小数了
    string fractionToDecimal(int numerator, int denominator) {
        if(denominator==0) return "";  // 边界条件，分母为0
        if(numerator==0) return "0";  // 边界条件，分子为0
        string result;
        
        //转换为longlong防止溢出
        long long num = (LL)numerator;  // static_cast<long long>(numerator)
        long long denom = (LL)denominator;
        
        //处理正负号，一正一负取负号
        if((num>0)^(denom>0))
            result.push_back('-');  // 用 += 也行
        
        //分子分母全部转换为正数（labs 处理长整形的绝对值）
        num=labs(num); denom=labs(denom);
        
        //处理整数部分
        result.append(to_string(num/denom));
        
        //处理小数部分
        num %= denom;                    //获得余数
        if(num==0)                      //余数为0，表示整除了，直接返回结果
            return result;             
        result.push_back('.');              //余数不为0，添加小数点
        
        int index = result.size()-1;          //获得小数点的下标（重要），用length()也行
        unordered_map<int, int> record;      //map用来记录出现重复数的下标，然后将'('插入到重复数前面就好了
        while(num && record.count(num) == 0){   //小数部分：余数不为0且余数还没有出现重复数字（如果因为余数为0退出循环，则代表是有限小数）
            record[num] = ++index;
            num *= 10;                        //余数扩大10倍，然后求商，和草稿本上运算方法是一样的
            result += to_string(num/denom);
            num %= denom;  // 新的余数
        }
        
        if(record.count(num) == 1){           //出现循环余数，我们直接在重复数字前面添加'(',字符串末尾添加')'
            result.insert(record[num], "(");
            result.push_back(')');
        }
        
        return result;
    }
    
};
           

自己提交的代码（看上面的注释版本就好）

typedef long long LL;

class Solution {
public:
    string fractionToDecimal(int numerator, int denominator) {
        if(denominator == 0)
            return "";
        if(numerator == 0)
            return "0";
        
        string res = "";
        if((numerator > 0) ^ (denominator > 0))
            res += "-";
        
        LL numerator_ll = fabs((LL)numerator);
        LL denominator_ll = fabs((LL)denominator);
        
        res += to_string(numerator_ll / denominator_ll);
        if(numerator_ll % denominator_ll == 0)
            return res;
        
        res += ".";
        numerator_ll = numerator_ll % denominator_ll;
        int index = res.length() - 1;
        unordered_map<int, int> umap;
        
        while(numerator_ll && umap.count(numerator_ll) == 0){
            umap[numerator_ll] = ++index;
        
            numerator_ll = numerator_ll * 10;
            res += to_string(numerator_ll / denominator_ll);
            
            numerator_ll = numerator_ll % denominator_ll;
        }
        
        if(umap.count(numerator_ll) > 0){
            res.insert(umap[numerator_ll], "(");
            res += ")";
        }
        
        return res;
    }
};