Saturday, January 3, 2015

166. Fraction to Recurring Decimal -M !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

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.
Example 1:
Input: numerator = 1, denominator = 2
Output: "0.5"
Example 2:
Input: numerator = 2, denominator = 1
Output: "2"
Example 3:
Input: numerator = 2, denominator = 3
Output: "0.(6)"
A:
思路很简单,就是挨个 乘呗。每次都乘以10

class Solution {
public:
    string fractionToDecimal(int numerator, int denominator) {        
        long a = numerator;
        long b = denominator;
        if( b == 0)
            throw std::invalid_argument( "demoninator cannot be zero");
        string sign = "";
        if(  (a < 0 and b >0 ) || (a > 0 and b < 0))
            sign = "-";
        a = abs(a);
        b = abs(b);
        string res = sign + to_string(a /b);
        
        long rem = a % b;
        if(rem ==0)
            return res;
        else
            return res+"." + helper(rem, b);
    }
private:
    string helper(long a, long b)
    {    
        unordered_map<long, int> M; // value to index
        vector<char> res;
        int index = 0;
        while(a != 0 && M.find(a) == M.end())
        {
            M[a]=index++;
            char v = '0'+(a*10 / b);
            res.push_back(v);
            a = a*10 % b;
        }
        if(a!=0) // we found loop
        {
            res.insert(res.begin() + M[a], '(');
            res.push_back(')');
        }
        string ss(res.begin(), res.end());
        return ss;
    }
};

Mistakes:
1: 不能简单的,假设a / b的整数结果就可以处理符号问题。
  如果是   -7 / 12 整数位是0 ,没有负号。  因此要单独处理

2: 考虑到负数的范围更大,因此考虑都转换成负数 
Line 7: Char 22: runtime error: signed integer overflow: -1 * -2147483648 cannot be represented in type 'int' (solution.cpp)

long b = abs(denominator);   这样也是不对的。 因为会默认先转成int 类型的正数。
Line 10: Char 21: runtime error: negation of -2147483648 cannot be represented in type 'int'; cast to an unsigned type to negate this value to itself (solution.cpp)

3: 别傻了, 老老实实转换成 double类型, 别非想着用int, 否则 *10之后,可能会溢出的



No comments:

Post a Comment