首页 > 代码库 > LeetCode:Fraction to Recurring Decimal

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

思路分析:先算正数部分,再用for循环算小数部分。在计算的过程中,将所有出现过的小数位放在map中,并在map中记录先他们在结果中的位置。如果当前计算得到的值在map中已经出现了,则表示出现了循环,根据之前记录下的位置在结果中插入括号,即可得最终结果。


代码:

string solution::fractionToDecimal(int64_t numerator,int64_t denominator)
{
	string result = "";
	if(numerator == 0)
		return "0";
	if(numerator < 0 ^ denominator < 0)
		result += "-";
	if(numerator < 0)
		numerator = numerator * -1;
	if(denominator < 0)
		denominator = denominator * -1;
	result += to_string(numerator/denominator);
	if(numerator % denominator == 0)
		return result;
	result += ".";
	unordered_map<int,int> um;
	for(int64_t r = numerator % denominator;r != 0;r = r % denominator)
	{
		if(um.count(r) > 0)
		{
			result.insert(um[r],1,'(');
			result += ")";
			break;
		}
		um[r] = result.size();
		r = r*10;
		result +=to_string(r/denominator);
	}
	return result;
}



LeetCode:Fraction to Recurring Decimal