leetcode 166. Fraction to Recurring Decimal 循环小数的展开

深碍√TFBOYSˉ_ 2022-06-08 07:25 160阅读 0赞

Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.

If the fractional part is repeating, enclose the repeating part in parentheses.

For example,

Given numerator = 1, denominator = 2, return “0.5”.  
Given numerator = 2, denominator = 1, return “2”.  
Given numerator = 2, denominator = 3, return “0.(6)”.

这道题很简单，但是很烦要考虑很多的exception。

需要注意的地方就是如何判断是否是循环小数：**只要出现重复的余数就表示该小数就是循环小数。**然后仔细的处理各种情况就可以了，很烦的。

代码如下：

import java.util.ArrayList;
    import java.util.HashSet;
    import java.util.List;
    import java.util.Set;
    
    
    /*
     * 这个问题的关键是如何判断是否存在存在循环小数，
     * 假如存在，应该如何判断位置
     * 
     * 这里我们直接用语速来判断是否存在循环小数，
     * 当某一个余数出现两次就表示出现了无限循环小数，
     * 定位这两个位置就可以得到循环小数的位置
     * 
     * */
    public class Solution 
    {
    
        public String fractionToDecimal(int numerator, int denominator) 
        {
            //这里转化为long是为了避免出现  1/12432356437 int越界的情况
            //因为我们要不断的补0上去所以可能出现越界
            long fenzi=numerator;
            long fenmu=denominator;
            if(fenzi==0)
                return "0";
    
            boolean flag=fenzi<0&&fenmu<0 || fenzi>0&&fenmu>0 ? true : false;
            fenzi=Math.abs(fenzi);
            fenmu=Math.abs(fenmu);
    
            //保存对应的余数和商
            List<Long> myYuShu=new ArrayList<>();
            List<Long> myShang=new ArrayList<>();
    
            //intA是整数部分的判断
            long intA=fenzi/fenmu;
            fenzi=fenzi%fenmu;
            myShang.add(intA);
            myYuShu.add(fenzi);
    
            //这里是处理整除的特殊情况
            if(fenzi==0)
                return flag? intA+"" : "-"+intA+"";
    
            //来判断是否存在循环小数
            boolean circle=false;
            while(true)
            {
                fenzi=fenzi*10;
                long a=fenzi/fenmu;
                fenzi=fenzi%fenmu;
    
                //a=0表示需要不断的添加0来补位
                if(a==0)
                {
                    myShang.add(a);
                    myYuShu.add(fenzi);
                }else if(fenzi==0)  //分子为0表示计算结束
                {
                    myShang.add(a);
                    myYuShu.add(fenzi);
                    break;
                }
                else 
                {
                    //遇到余数重复出现的情况，直接break，
                    if(myYuShu.contains(fenzi))
                    {
                        myShang.add(a);
                        myYuShu.add(fenzi);
                        circle=true;
                        break;
                    }else
                    {
                         myShang.add(a);
                         myYuShu.add(fenzi);
                    }
                }
            }
    
            String res="";
            if(circle)
            {
                int i=0;
                for(;i<myShang.size();i++)
                {
                    //处理整数部分
                    if(i==0)
                    {
                        res = res + myShang.get(i) + ".";
                        if(fenzi==myYuShu.get(i))
                            break;  
                    //遇到循环小数的开始部分
                    }else if(fenzi==myYuShu.get(i))
                    {
                        res = res + myShang.get(i);
                        break;
                    }
                    else
                        res = res + myShang.get(i);
                }
                res = res+"(";
                for(int j=i+1;j<myShang.size();j++)
                    res = res + myShang.get(j);
                res = res+")";  
            }else
            {
                res+=myShang.get(0)+".";
                for(int i=1;i<myShang.size();i++)
                    res+=myShang.get(i);
            }
            return flag? res : "-"+res;
        }
    
    
        public static void main(String[] args) 
        {
            int a=-1;
            int b=-2147483648;
            Solution solution=new Solution();
            System.out.println(solution.fractionToDecimal(a, b));
        }
    
    }

下面是C++的做法，这个是网上看到的做法，这个做法要比我的做法简洁多了，很值得学习，这道题并不难，主要就是处理各种的exception

代码如下：

#include <iostream>
    #include <algorithm>
    #include <climits>
    #include <vector>
    #include <string>
    #include <unordered_map>
    
    using namespace std;
    
    
    class Solution 
    {
    public:
        string fractionToDecimal(int numerator, int denominator) 
        {
            if (numerator==0) 
                return "0";
    
            string res="";
            if ((numerator < 0) ^ (denominator < 0))
                res += '-';
    
            long numer = numerator < 0 ? (long)numerator * (-1) : (long)numerator;
            long denom = denominator < 0 ? (long)denominator * (-1) : (long)denominator;
            long integral = numer / denom;
            res += to_string(integral);
            long rmd = numer % denom;
    
            if (rmd==0) 
                return res;
    
            res += '.';
            rmd *= 10;
            unordered_map<long, long> mp;
            while (rmd) 
            {
                long quotient = rmd / denom;
                if (mp.find(rmd) != mp.end()) 
                {
                    res.insert(mp[rmd], 1, '(');
                    res += ')';
                    break;
                }
                mp[rmd] = res.size();
                res += to_string(quotient);
                rmd = (rmd % denom) * 10;
            }
            return res;
        }
    };