Skip to main content

【LeetCode 134】加油站

·259 words·2 mins
WFUing
Author
WFUing
A graduate who loves coding.

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        int[] temp = new int[n];
        for(int i = 0; i < n; i++) {
            temp[i] = gas[i] - cost[i];
        }
        for(int i = 0; i < n; i++) {
            int ans = 0, flag = 1;
            for(int j = 0; j < n; j++) {
                ans += temp[(i+j)%n];
                if(ans < 0) {
                    flag = 0;
                    break;
                }
            }
            if(flag == 1) {
                return i;
            }
        }
        return -1;
    }
}

稍微优化一下。

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        int[] temp = new int[n];
        for(int i = 0; i < n; i++) {
            temp[i] = gas[i] - cost[i];
        }
        for(int i = 0; i < n; i++) {
            int ans = 0, flag = 1;
            for(int j = 0; j < n; j++) {
                ans += temp[(i+j)%n];
                if(ans < 0) {
                    // 补一下
                    i += j;
                    flag = 0;
                    break;
                }
            }
            if(flag == 1) {
                return i;
            }
        }
        return -1;
    }
}

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        int i = 0;
        while (i < n) {
            int sumOfGas = 0, sumOfCost = 0;
            int cnt = 0;
            while (cnt < n) {
                int j = (i + cnt) % n;
                sumOfGas += gas[j];
                sumOfCost += cost[j];
                if (sumOfCost > sumOfGas) {
                    break;
                }
                cnt++;
            }
            if (cnt == n) {
                return i;
            } else {
                i = i + cnt + 1;
            }
        }
        return -1;
    }
}