leetcode 166. Fraction to Recurring Decimal

约定不等于承诺〃 2022-08-21 00:07 128阅读 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)".

不能直接除，因为计算机表示精度有限，直接除第一次除出来的结果就有偏差了，数位少看不出来，往后面算出来的数就可能不对了，所以这个解法受制于计算机，行不通。

例如1/17，正确答案为"0.(0588235294117647)"，上直接除输出却为"0.0588235294117647100620160927064716815948486328125"，就是这个原因。

上面这个问题可以每次求余数，这样精度不会有任何损失。

在一个还有溢出问题，numerator和denominator都可能超出int的最大表示范围，所以要转化为long。

程序里fraction和pp两个变量定义成int，出错了找了半天，应该是long，思维不周密啊

class Solution {
    	string myitoa(long long int num)
    	{
    		string re;
    		if (num == 0)
    			return string("0");
    		while (num != 0)
    		{
    			re.insert(re.begin(), '0' + num % 10);
    			num = num / 10;
    		}
    		return re;
    	}
    public:
    	string fractionToDecimal(int numerator, int denominator) {
    		if (numerator == 0)
    			return string("0");
    		if (denominator == 0)
    			return string("");
    		string re;
    		if (numerator < 0 && denominator>0 || numerator > 0 && denominator < 0)
    			re += '-';
    		long long int num = numerator, den = denominator;
    		num = abs(num), den = abs(den);
    		long long int integer = num / den;
    		re += myitoa(integer);
    
    		long long int fraction = num - abs(integer*den);
    		if (fraction == 0)
    			return re;
    		re += '.';
    		map<int,int>bb;
    		string fracpart;
    		int kk = 0;
    		while (fraction != 0)
    		{
    			if (bb.find(fraction) != bb.end())
    			{
    				string ff = string(fracpart.begin() + bb[fraction], fracpart.end());
    				fracpart.erase(fracpart.begin() + bb[fraction], fracpart.end());
    				fracpart += ('(' + ff + ')');
    				return re + fracpart;
    			}
    			else
    				bb.insert(pair<int, int>(fraction, kk));
    			long long int pp = 10 * fraction;
    			fracpart += myitoa(pp  /den);
    			fraction = pp  - (long long int)(pp / den)*den;
    			kk++;
    		}
    		int hh = fracpart.length()-1;
    		while (fracpart[hh] == '0')
    			hh--;
    		fracpart.erase(hh + 1, fracpart.length());
    		return re + fracpart;
    	}
    };

accepted