bucket solution in C++, short-circuit if duplicate exist or lengh > 720


  • 0
    Q

    bucket solution in C++, short-circuitif duplicate exist or lengh > 720

    1. pigeon hole short-circuit, if length > 1440 return 0;
    2. use flag array, if duplicate, return 0;
    3. pigeon hole short-circuit, if length > 1440 / 2 return 1;
    4. check minimal difference, similar to Verbose Java Solution, Bucket
      4.1 short-circuit if res reach 1
    int findMinDifference(vector<string>& timePoints) {
        if (timePoints.size() > 1440) return 0; 
        std::vector<int> times(1440, 0);
        auto getTime = [](string t) { return 60 * ((t[0] - '0') * 10 + (t[1] - '0')) + ((t[3] - '0') * 10 + (t[4] - '0')); };
        for (int i = 0, sz = std::min(timePoints.size(), times.size()); i < sz; ++i) {
            if (times[getTime(timePoints[i])]++) return 0;
        }
        if (timePoints.size() > 1440 / 2) return 1; 
        int res = 1440, prev = -1440, first = -1440;
        // for (int i = 0, sz = times.size(); i < sz; ++i) {
        for (int i = 0, sz = times.size(); i < sz && res > 1; ++i) {
            if (times[i]) {
                if (first < 0) first = i;
                res = std::min(res, i - prev);
                prev = i;
            }
        }
        res = std::min(res, 1440 - (prev - first));  // handle `last - first` case
        return res;
    }

Log in to reply
 

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