首页 > 代码库 > [C++]LeetCode: 82 Fraction to Recurring Decimal

[C++]LeetCode: 82 Fraction to Recurring Decimal

题目:

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)".

题意:给定一个分子和一个分母,以字符串的形式返回该小数。如果小数无限循环的话,用括号扩住循环体。

思路:手写计算除法方法

    0.16  
6 ) 1.00
    0 
    1 0       <-- Remainder=1, mark 1 as seen at position=0.
    - 6 
      40      <-- Remainder=4, mark 4 as seen at position=1.
    - 36 
       4      <-- Remainder=4 was seen before at position=1, so the fractional part which is 16 starts repeating at position=1 => 1(6).

关键点就是如何确定循环体?

我们用一个hashmap记录每一个余数,以及该余数出现的位置,当出现重复的余数时,说明除法开始进入循环,两个重复余数之间的部分就是循环体。

示例:1/13=0.076923076923076923...,当小数部分第二次出现0时,就意味着开始了循环,那么需要把076923用括号括起来,结果为0.(076923)。

Attention:

1. HashMap的构造

HashMap<key, value>分别对应<当前余数,对应的结果下标(位置)>。这样可以根据key即余数来判断是否进入循环;并且这样之后才能在循环体的第一个数前插入‘(’;这种利用map的方法十分巧妙。既标记了余数,又标记了位置。

2. 考虑正负数,和溢出

考虑结果的正负数,我们先判断符号,然后都转为正数运算。

考虑溢出,如果输入为INT.MIN_VALUE, 取绝对值后会溢出,所以我们需要调整计算的分子分母和余数的类型为long 或 long long.

<span style="font-size:14px;"> //(2)得到绝对值
        //int n = abs(numerator);
        //int d = abs(denominator);
        long long int n = numerator, d = denominator;  
        n=abs(n);
        d=abs(d);  
        
        //(3) 计算整数部分
        ret += to_string(n/d);
        long long int r= n % d;    //余数r  </span>

溢出结果 将变成负数的除法

30 / 35 test cases passed.
Status: 

Wrong Answer

 
Submitted: 32 minutes ago
Input:-1, -2147483648
Output:"0.000000000-4-6-5-6-6-1-2-8-7-30-7-7-3-9-2-5-7-8-1-2-5"
Expected:"0.0000000004656612873077392578125"

3. 先处理特殊情况,分子或分母为0

<span style="font-size:14px;"> //计算特殊情况,分子/分母为0
        if(numerator == 0) return "0";
        if(denominator == 0) return "";</span>
4. 注意我们计算除法的步骤:

(1)先判断符号  (2)计算整数部分,是否有余数,有,加小数点‘.‘,继续计算;无,返回结果 (3)余数补零,和分母作除法,计入结果(r *= 10, ret += to_string(r / d))(4) 如果还有余数,将余数作为下一次计算的分子(r %= d)直到出现循环或者没有余数,结束计算。

5. string的insert函数

string& insert (size_t pos, size_t n, char c);
复杂度:O(1) 空间复杂度O(1) 都是常数。可以表示为分数,说明一定是有理数。

AC Code:

<span style="font-size:14px;">class Solution {
public:
    string fractionToDecimal(int numerator, int denominator) {
        //计算特殊情况,分子/分母为0
        if(numerator == 0) return "0";
        if(denominator == 0) return "";
        
        string ret;
        
        //(1)判断符号位
        if(numerator < 0 ^ denominator < 0) ret += '-';
        
        //(2)得到绝对值
        //int n = abs(numerator);
        //int d = abs(denominator);
        long long int n = numerator, d = denominator;  
        n=abs(n);
        d=abs(d);  
        
        //(3) 计算整数部分
        ret += to_string(n/d);
        long long int r= n % d;    //余数r  
        if(r == 0) return ret;
        
        ret += '.';
        
        //(4) 计算小数部分  
        unordered_map<int, int> pmap;  //记录位置信息 余数的位置
        while(r)
        {
            //如果这个余数出现过,说明分数除法开始循环 停止计算,在第一次出现的位置插入‘(’,在最后插入‘)’
            if(pmap.count(r) == 1)
            {
                ret.insert(pmap[r], 1,'(');
                ret += ')';
                return ret;
            }
            
            //记录此时的余数和位置
            pmap[r] = ret.size();
            
            //如果没有出现循环,按照手写计算除法的方法计算除法: 补零,做除法;然后取余数,作为下一次计算分子
            r *= 10;
            ret += to_string(r / d);
            r %= d;
        }
        
        return ret;
    }
    
};</span>





[C++]LeetCode: 82 Fraction to Recurring Decimal