[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;
  	}
  };