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

相关博文：

定制桌面成功案例

海量文档查同或聚类问题 -- Locality Sensitive Hash 算法 （转）

汉字转拼音c/c++源码，支持gb2312和utf8

数据库顶级会议——SIGMOD介绍