LeetCode 166. 分数到小数--模拟

166. 分数到小数

给定两个整数，分别表示分数的分子 numerator 和分母 denominator，以字符串形式返回小数。

如果小数部分为循环小数，则将循环的部分括在括号内。

示例 1:

输入: numerator = 1, denominator = 2
输出: “0.5”

示例 2:

输入: numerator = 2, denominator = 1
输出: “2”

示例 3:

输入: numerator = 2, denominator = 3
输出: “0.(6)”

题解
主要难在小数循环部分的处理，怎么找到开始循环的位置，因为题目要求输出循环的结果，所以暑假应该保证了分数都是有理数，余数在反复做除运算的时候，因为出现了相同的被除数，以1和33为例：
整数部分为0，余数为1，除数为33
此时s=“0.”
step1 余数为110=10，除数为33，得到新的小数位置上的整数部分为0，余数为10，
此时s=“0.0”
step2 余数为1010=100，除数为33，得到新的小数位置上的整数部分为3，余数为1，
此时s=“0.03”
step3 余数为1*10=10，出现了重复的在step1中的10，因此会无限重复上述的操作，因此判断位置1开始就是无限循环。
所以我们需要标记每个位置上出现的余数，利用map进行标记判断即可，要注意负数处理。
AC代码

class Solution {
public:
typedef long long ll;
map<ll,int>pos;
string fractionToDecimal(ll x, ll y) 
{
	string s="";
	if(x*y<0)
	s+="-";
	x=abs(x);
	y=abs(y);
	ll t=x/y;
	x=x%y;
	//处理整数部分
	if(t==0)
	s+="0";
	else
	{
		vector<int>q;
		while(t>0)
		{
			q.push_back(t%10);
			t/=10;
		}
		for(int i=q.size()-1;i>=0;i--)
		s+=(q[i]+'0');
	}
	if(x==0)return s;
	s+=".";
	pos.clear();
	string tt="";
	int dp=0;
	int sign=-1;
	//处理小数部分
	while(true)
	{
		x*=10;
		if(pos[x]>0)
		{
			sign=pos[x];
			break;
		}
		dp++;
		pos[x]=dp;
		tt+=((x/y)+'0');
		x%=y;
		if(x==0)break;
	}
	//把循环部分括起来
	if(sign>0)
	{
		for(int i=0;i<sign-1;i++)
		s+=tt[i];
		s+="(";
		for(int i=sign-1;i<dp;i++)
		s+=tt[i];
		s+=")";
	}
	else s+=tt;
	return s;
}
};