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

Hint:

No scary math, just apply elementary math knowledge. Still remember how to perform a long division?

这题就是按定义做。

如果不能整除，就不断进行余数补零除以除数。

维护一个映射表map<long long, int> m, 用来记录每个余数对应返回值ret中的位置。

（1）当出现重复的余数r时，说明找到了循环体，根据m[r]找到ret中位置，加上相应的'('和')'将循环体括起来即可返回。

（2）当余数r为0时，返回ret。

注意点：可能出现INT_MIN/-1的越界情况，因此第一步现将int转为long long int

class Solution {

public:

    string fractionToDecimal(int numerator, int denominator) {

        if(denominator==)

            return "";

        if(numerator==)

            return "";

        string res;

        long long num=numerator;

        long long den=denominator;

        if((num<)^(den<))

        {

            res+="-";

            num=abs(num);

            den=abs(den);

        }

        long long temp=num/den;

        res+=to_string(temp);

        if (num%den==)

            return res;

        res+=".";

        temp=num%den;

        map<long long,int> m;

        while(temp!=)

        {

            if(m.find(temp)!=m.end())

            {

                res.insert(m[temp], , '(');   //insert (iterator p, size_t n, char c);

                res += ')';

                return res;

            }

            m[temp] = res.size();

            temp*=;

            res+=to_string(temp/den);

            temp%=den;

        }

        return res;

    }

};

巴特西

Fraction to Recurring Decimal——数值处理&&哈希表

最新文章

热门文章