3ms c++ code with explanation


  • 0
    K



    class Solution {
    public:
    //the key point is to do division just like a pupil
    string fractionToDecimal(int numerator, int denominator) {
    if (numerator == 0)
    return "0";

        //use long to avoid overflow, convert all to positive
        bool b1 = numerator < 0,b2 = denominator < 0;
        long num = numerator, den = denominator;
        if (b1) num = -num;
        if (b2) den = -den;
        long quotient = num/den, remainder = num % den;
        string res;
    
        //the part before the decimal point
    	if (quotient == 0)
    	    res.append("0");
        while (quotient>0){
    	    res.push_back('0' + (quotient % 10));
    	    quotient /= 10;
        }
    	if (b1 ^ b2)
    	    res.push_back('-');
        reverse(res.begin(), res.end());
    
        //no remainder, just return
        if (remainder == 0)
    	    return res;
    	
        res.push_back('.');
    
        //the decimal part
        //the key point is that when we find the reminder has appeared before or the reminder  is zero ,we stopped
        vector<char> decimal;
        unordered_map<long long, int> rec;
    	int count = 0;
        int repeat = -1;//repeat is the the start of a recurring
        while (1){
    	    remainder *= 10;
    	    //when we find the reminder has appeared before	,we know that the recurring happened	
    	    if (rec.find(remainder) != rec.end()){
    		    repeat = rec[remainder];
    		    break;
    	    }
    	    //or we just put it into the map
    	    else
    		    rec[remainder] = count;
    	    count++;
    	    decimal.push_back('0' + remainder / den);
    	    long i = remainder % den;
    	    if (i == 0)//is the reminder is zero ,it means no recurring, we just break
    		    break;
    	    remainder = i;
        }
    
        //push the decimal part into the string
        if (repeat == 0)
    	    res.push_back('(');
        for (int i = 0; i < decimal.size(); i++){
    	    res.push_back(decimal[i]);
    	    if (i + 1 == repeat)
    		    res.push_back('(');
        }
        if (repeat >= 0)
    	    res.push_back(')');
        return res;
    }
    

    };


Log in to reply
 

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