0ms C++ solution with unordered_map


  • 1
    F
    string fractionToDecimal(int numerator, int denominator) 
    {
    	if (numerator == 0) { return "0"; }
    
    	unordered_map<int, int> map;
    	vector<int> prevNumverator;
    	string result = "";
    	bool isNeg = (numerator > 0 && denominator < 0) || (numerator < 0 && denominator > 0);
    	
    	long long curNumerator = numerator;
    	if (curNumerator < 0) { curNumerator *= -1; }
    	long long curDenominator = denominator;
    	if (curDenominator < 0) { curDenominator *= -1; }
    
    	bool hasDot = false;
    	while (1)
    	{						
    		if (map.find(curNumerator) == map.end())
    		{				
    			prevNumverator.push_back(curNumerator);
    			long long curVal = (long long)curNumerator / (long long)curDenominator;
    			map[curNumerator] = result.size();
    			if (curVal == 0)
    			{
    				result += "0";
    			}
    			else
    			{
    				result += to_string(curVal);
    			}
    			curNumerator = curNumerator % curDenominator * 10;
    			if (curNumerator == 0) { break; }
    			if (!hasDot)
    			{
    				result += ".";
    				hasDot = true;
    			}
    		}
    		else
    		{
    			int index = map[curNumerator];
    			result.insert(result.begin() + index, '(');
    			result.push_back(')');
    			break;
    		}	
    	}
    	return isNeg ? "-" + result : result;
    }

  • 0
    F

    Cleaned up a few places and added some comments

    string fractionToDecimal(int numerator, int denominator) 
    {
    	if (numerator == 0) { return "0"; }
    
    	unordered_map<int, int> map;
    	vector<int> prevNumverator;
    	string result = "";
    	bool isNeg = (numerator > 0 && denominator < 0) || (numerator < 0 && denominator > 0);
    	
    	// Overflow prevention
    	long long curNumerator = numerator;
    	if (curNumerator < 0) { curNumerator *= -1; }
    	long long curDenominator = denominator;
    	if (curDenominator < 0) { curDenominator *= -1; }
    
    	bool hasDot = false;
    	while (1)
    	{						
    		if (map.find(curNumerator) == map.end())
    		{				
    			prevNumverator.push_back(curNumerator);
    			long long curVal = (long long)curNumerator / (long long)curDenominator;
    			// Remember the index. This will be the location to insert '(' if necessary
    			map[curNumerator] = result.size();
    			result += to_string(curVal);				
    			curNumerator = curNumerator % curDenominator * 10;
    			if (curNumerator == 0) { break; }
    			if (!hasDot)
    			{
    				result += ".";
    				hasDot = true;
    			}
    		}
    		else
    		{
    			int index = map[curNumerator];
    			result.insert(result.begin() + index, '(');
    			result.push_back(')');
    			break;
    		}	
    	}
    	return isNeg ? "-" + result : result;
    }

  • 0

    I share you with the samll idea, but I think my solution is more easy:

    class Solution {
    public:
        std::string fractionToDecimal(long long numerator, long long denominator) {
            if (!numerator)
                return "0";
            std::string str = numerator < 0 ^ denominator < 0 ? "-" : "";
            numerator = std::abs(numerator);
            denominator = std::abs(denominator);
            long long quotient = numerator / denominator, remainder = numerator % denominator;
            std::stringstream ss;
            ss << quotient;
            str += ss.str();
            if (!remainder)
                return str;
            str += '.';
            std::unordered_map<int, int> flag;
            int pos = str.size();
            while (remainder && flag.find(remainder) == flag.end()) {
                flag[remainder] = pos++;
                numerator = remainder * 10;
                quotient = numerator / denominator;
                remainder = numerator % denominator;
                str += '0' + quotient;
            }
            if (remainder) {
                str += ')';
                str.insert(str.begin() + flag[remainder], '(');
            }
            return str;
        }
    };

Log in to reply
 

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