My C++ solution - better use of std::unordered_map


  • 1
    C

    We can rewrite the phrase

    if (map.find(key) == map.end()) {
        map[key] = value;
    } else {
        // duplicated
    }
    

    by the API insert or emplace (since C++11)

    map.emplace(key, value);
    

    Here is my full code

    #include <cstdlib>
    
    #include <string>
    #include <unordered_map>
    
    class Solution {
    public:
        std::string fractionToDecimal(int numerator, int denominator) {
            if (denominator == 0) {
                // to avoid divide by zero
                return "";
            } else if (numerator == 0) {
                // to avoid output "-0"
                return "0";
            }
    
            // cast numerator and denominator to long long to avoid overflow
            // and then make them positive
            long long n = numerator, d = denominator;
            std::string num;
            if (n < 0) {
                n = abs(n);
                d *= -1;
            }
            if (d < 0) {
                // only one of numerator and denominator is negative
                d = abs(d);
                num.push_back('-');
            }
    
            // integer part
            num += std::to_string(n / d);
            n %= d;
            if (n == 0) {
                return std::move(num);
            }
    
            // fractional part
            num.push_back('.');
            std::unordered_map<long long, size_t> hash_table;
            while (n != 0) {
                // associate remainder with the position of its appearance
                auto res = hash_table.emplace(n, num.size());
                if (!res.second) {
                    num.insert(res.first->second, "(");
                    num.push_back(')');
                    break;
                }
                n *= 10;
                num += std::to_string(n / d);
                n %= d;
            }
            return std::move(num);
        }
    };

Log in to reply
 

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