[Rainbow] a math mimic operation implementation problem


  • 1

    This problem requires us to mimic the operation of divide.

    The trouble is that we need to find the recuring parts. If no recurring parts, the problem will be easy. We just

    need to solve the problem step by step to mimic the operation

    We devide and get the remained part and multiply it by 10 and continue the similiar operation ....

    Here is a ac implementation refered to @jianchao.li.fighter

    class Solution {
    public:
        string fractionToDecimal(int numerator, int denominator) {
            if(!numerator)  return "0";
            string result;
            if(numerator<0 ^ denominator<0)  result+="-";
            long m = abs((long)numerator);
            long n = abs((long)denominator);
            long s = m/n;
            result+=to_string(s);
            long r = m%n;
            if(!r)  return result;
            result += ".";
            r *= 10;
            unordered_map<long, long> dict;
            
            while(r){
                if(dict.find(r)!=dict.end()){
                    result.insert(dict[r], 1, '(');
                    result += ')';
                    break;
                }
                dict[r]=result.size();
                long ss = r/n;
                result += to_string(ss);
                r = (r%n)*10;
            }
            
            return result;
        }
    };

  • 1

    To insert the "()" to the correct position , we need to use the unordered_map to record the position ....


  • 1

    Implementation by myself.

    class Solution {
    public:
        string fractionToDecimal(int numerator, int denominator) {
            string result;
            
            if(numerator==0)  return "0";
            
            if(numerator>0 ^ denominator>0)  result += "-";
            
            long m=abs((long)numerator);
            long n=abs((long)denominator);
            long s=m/n;
            long r=m%n;
            
            result += to_string(s);
            if(r==0)  return result;
            result += '.';
            r*=10;
            
            unordered_map<int, int> dict;
            while(r){
                if(dict.find(r)!=dict.end()){
                    result.insert(dict[r], 1, '(');
                    result += ')';
                    break;
                }
                /** dict record the previous length **/
                dict[r]=result.size();
                long ss=r/n;
                result += to_string(ss);
                r = (r%n)*10;
            }
            
            return result;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.