Insufficient Test Cases. And Suggested Test Cases To Be Added


  • 0
    S

    I was looking at my previous code for review purpose. But my answer that has previously passed and got accepted turns out to be buggy. Hence I will state my previous algorithm and add several of my suggested test cases.

    my previous code:

    class Solution {
    public:
        int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
            vector<int> result(gas.size(), 0);
            int sumExist = 0;
            for(int i = 0; i < result.size(); i++){
                result[i] = gas[i]-cost[i];
                sumExist += result[i];
            }
            if(sumExist < 0){
                return -1;
            }
            int posCount = 0;
            int maxVal = 0;
            int maxInd = -1;
            for(int i = 0; i < 2*result.size(); i++){
                if(result[i%result.size()] >= 0) posCount += result[i%result.size()];
                else if(result[i%result.size()] < 0) posCount = 0;
                /*if(posCount >= 0) posCount += result[i%result.size()];
                if(posCount < 0) posCount = 0;*/
                
                if(posCount > maxVal){
                    maxVal = posCount;
                    maxInd = i%result.size();
                }
            }
            int temp = maxVal;
            for(int i = maxInd + result.size(); i >= 0; i--){
                temp -= result[i%result.size()];
                if(temp == 0) return i%result.size();
            }
        }
    };
    

    This algorithm was wrong. I tried to use a result vector to calculate and store the difference between the gain of gas and the cost of gas. Then in my second run, I looped through this result vector and want to find the starting point of the longest sequence of positive numbers. Because I thought that when I have the longest consecutive positive numbers, I will have the maximum gain of gas,

    and this is wrong.

    In the case when my result vector is 2,-1, 1, 2, 3, 4, -11. or more specifically, in the case of
    gas [2,0,1,2,3,4,0]
    and cost [0,1,0,0,0,0,11]

    my algorithm would not work because instead of starting at 0, I will start at 2.

    Hence I suggest to add the test case above and let people had same thought as mine can correct their code.(my code in the comment area would work right.)


  • 0

    Thanks! I've added the test case you suggested.


Log in to reply
 

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