[LeetCode] Fraction to Recurring Decimal

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

  题目意思：

  将分数转化成循环小数。大体思想是：用两个map分别记录商及其位置和余数及其位置，若出现了重复的余数，则表示此余数对应位置的商位开始循环。这道题非常多的陷阱。弄了我好久，代码如下所示

   

  class Solution {
  public:
  	string fractionToDecimal(int numerator, int denominator) {
  		string result = "";
  		long long numberatorL = (long long)numerator;
  		long long denominatorL = (long long)denominator;
  		if (numberatorL * denominatorL < 0){		//注意负数的情况
  			result += "-";
  			numberatorL = -numberatorL;
  		}
  		long long quotient = numberatorL / denominatorL;	//商
  		result += intToStr(quotient);
  		long long remainder = numberatorL % denominatorL;	//余数
  		if (remainder != 0){
  			result += '.';
  			int position = -1;
  			int repeatStartPosition = -1;		//循环起始位
  			map positionToQuotient;	//位置到商，从某个位置开始为循环小数
  			map remainderToPosition;	//余数到位置
  			remainderToPosition.insert(map::value_type(remainder, position));
  			position++;
  			while (remainder != 0){
  				remainder *= 10;
  				quotient = remainder / denominatorL;
  				remainder = remainder % denominatorL;
  				positionToQuotient.insert(map::value_type(position, quotient));
  				map::iterator it = remainderToPosition.find(remainder);
  				if (it != remainderToPosition.end()){	//若余数已经存在过
  					repeatStartPosition = it->second + 1;
  					break;
  				}
  				remainderToPosition.insert(map::value_type(remainder, position));
  				position++;
  			}
  			for (map::iterator it = positionToQuotient.begin(); it != positionToQuotient.end(); it++){
  				if (it->first == repeatStartPosition){
  					result += "(";
  				}
  				result += intToStr(it->second);
  			}
  			if (repeatStartPosition >= 0){
  				result += ")";
  			}
  		}
  		return result;
  	}
  
  private:
  	string intToStr(long long number){
  		string result = "";
  		do{
  			result = (char)(number % 10 + '0') + result;
  			number /= 10;
  		} while (number != 0);
  		return result;
  	}
  };