134. Gas Station

二刷 06/2022

Version #2 Two Passes

基本上是照着答案才写出来

Runtime: 1 ms, faster than 100.00% of Java online submissions for Gas Station.

Memory Usage: 62.1 MB, less than 92.15% of Java online submissions for Gas Station.

class Solution {

    public int canCompleteCircuit(int[] gas, int[] cost) {

        //step1 start from index 0, try the furthest index that we can reach

        //step2 if we stopped at index i, try start from index i+1 and retry step1

        // It is guaranteed that if we start at index i and stoped at j(j > i), all indexes between index [i, j] won't be the answer, since the real_gas[k]=remaining gas before k + gas[k], which is larger than or equals to gas[k], if we cannot finish the trip with the real_gas[k], then we definitly cannot finish the trip with gas[k]

        int total = 0;

        for (int i = 0; i < gas.length; i++) {

            total += gas[i] - cost[i];

        }

        if (total < 0) {

            return -1;

        }

        // We just need to find the start point

        int diff = 0;

        int startIndex = 0;

        for (int i = 0; i < gas.length; i++) {

            diff += gas[i] - cost[i];

            if (diff < 0) {

                startIndex = i + 1;

                diff = 0;

            }

        }

        return startIndex;

    }

}

Version #1 Two Pointer
如果当前start得到的sum为负，就必须向前搜其他的start point
如果当前的为正，就可以尝试向后走
问题是最终返回的时候，如果最终start和end相遇时sum都为负，则不存在解
二刷

100.00 %
class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        // the difference between gasSum - costSum must always larger or equals to zero
        // (startIndex, endIndex]
        int len = gas.length;
        int diff = 0;
        int startIndex = len, endIndex = 0;
        while (startIndex > endIndex) {
            diff += gas[endIndex] - cost[endIndex];
            endIndex++;
            while (startIndex > endIndex && diff < 0) {
                startIndex--;
                diff += gas[startIndex] - cost[startIndex];
            }
        }
        return diff >= 0 ? startIndex % len : -1;
    }
}

一刷

100.00 %
class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int start = gas.length;
        int end = 0;
        int sum = 0;
        // [start, end)
        while (start > end) {
            sum += gas[end] - cost[end];
            while (start > end && sum < 0) {
                start--;
                sum += gas[start] - cost[start];
            }
            end++;
        }
        return sum < 0 ? -1 : start % gas.length;
    }
}