I think the evaluating code has some problems!


  • 0
    T

    When the input is gas = [5,1,2,3,4] and cost = [4,4,1,5,1], the output of the evaluating code is 2. Obviously, 2 is not correct. Can anybody tell me if I am right?

    Below is my own code, which is accepted.

    class Solution {
    public:
        int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
            int sz = gas.size();
            vector<int>oilleft(2*sz);
            for (int idx = 0; idx < sz; ++idx)
            {
                oilleft[idx] = gas[idx] - cost[idx];
                oilleft[idx + sz] = oilleft[idx];
            }
            int total = 0;
            int prev = 0;
            int post = 0;
            while(prev < sz)
            {
                total += oilleft[post++];
                while(total < 0)
                    total -= oilleft[prev++];
                if (post - prev == sz)return prev;
            }
            
            for (int idx = 0; idx < sz; ++idx)
            {
                oilleft[idx] = gas[idx] - cost[(idx+sz-1)%sz];
                oilleft[idx + sz] = oilleft[idx];
            }
            total = 0;
            prev = 2*sz - 1;
            post = 2*sz - 1;
            while(prev >= sz)
            {
                total += oilleft[post--];
                while(total < 0)
                    total -= oilleft[prev--];
                if (prev - post == sz)return prev%sz;
            }
            return -1;
        }
    };

  • 0
    W

    my accepted code output 4 for your input case, and I think you are right. The test samples are too few.


Log in to reply
 

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