Google+ Followers

Monday, August 7, 2017

[Leetcode] Fraction to Recurring Decimal, Solution

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

[Thoughts]
分成三步走,第一步,处理整数,确定小数点之前的数字;第二步,加小数点;第三步,不断的做除法,直到发现重复的余数,之前的数字即为循环数字。

[Code]
1:    string fractionToDecimal(int num2, int den2) {  
2:      if(num2 == 0) return "0";  
3:      string result;  
4:      if((num2>0) ^ (den2>0)) {  
5:        result +='-';  
6:      }  
7:      long num = abs((long)num2);  
8:      long den = abs((long)den2);  
9:            
10:      // process before point  
11:      long div = num/den;  
12:      result += to_string(div);  
13:        
14:      //add point  
15:      if(num % den != 0) {  
16:        result +='.';  
17:      } else {  
18:        return result;  
19:      }  
20:    
21:      //process after point  
22:     
23:      map<int, int> rem_index;  
24:      long remind= num%den;  
25:      while(remind!=0) {  
26:        long res = remind*10/den;  
27:          
28:        if(rem_index.find(remind) == rem_index.end()) {  
29:          result += to_string(res);  
30:          rem_index[remind] = result.size()-1;  
31:        } else {  
32:          result.insert(rem_index[remind], 1, '(');  
33:          result+=")";  
34:          break;  
35:        }  
36:        remind = remind * 10;  
37:        remind = remind% den;  
38:          
39:      }  
40:      return result;  
41:    }  






Post a Comment