LeetCode134. 加油站-Java&Go-两种想法

• 算法
  • 1.如果gas总和小于cost总和，一定不存在答案
  • 2.如果gas总和大于等于cost总和，一定存在答案
    • 因为题目给定答案唯一，所以遍历一遍数组之后，最终使得从start开始gas[i]-cost[i]之和大于等于0的那个位置即是答案

public int canCompleteCircuit(int[] gas, int[] cost) {
    int sumGas = 0, sumCost = 0, start = 0, tank = 0;
    for (int i = 0; i < gas.length; i++) {
        sumGas += gas[i];
        sumCost += cost[i];
        tank += gas[i] - cost[i];
        if (tank < 0) {
            start = i + 1;
            tank = 0;
        }
    }
    return sumGas < sumCost ? -1 : start;
}

func canCompleteCircuit(gas []int, cost []int) int {
    sumGas, sumCost := 0, 0
    start, tank := 0, 0
    for i := range gas {
        sumGas += gas[i]
        sumCost += cost[i]
        tank += gas[i] - cost[i]
        if tank < 0 {
            start = i + 1
            tank = 0
        }
    }
    if sumGas < sumCost {
        return -1
    } else {
        return start
    }
}

• 算法
  • 1.新定义left数组记录每个位置gas[i]-cost[i]的值
  • 2.选择left[i]大于等于0的位置开始，检查是否可以环行一周，中间如果出现油箱没有油了就停止检查当前left[i]，继续检查下一个left[i]

public int canCompleteCircuit(int[] gas, int[] cost) {
    int n = gas.length;
    int[] left = new int[n];
    for (int i = 0; i < n; i++) {
        left[i] = gas[i] - cost[i];
    }

    for (int i = 0; i < n; i++) {
        if (left[i] >= 0) {
            int sum = left[i], j = 1;
            while (j < n) {
                sum += left[(i+j)%n];
                if (sum < 0) {
                    break;
                }
                j++;
            }
            if (j == n) {
                return i;
            }
        }
    }
    return -1;
}

func canCompleteCircuit(gas []int, cost []int) int {
    n := len(gas)
    left := make([]int, n)
    for i := range left {
        left[i] = gas[i] - cost[i]
    }

    for i := range left {
        if left[i] >= 0 {
            sum := left[i]
            j := 1
            for j < n {
                sum += left[(i+j)%n]
                if sum < 0 {
                    break
                }
                j++
            }
            if j == n {
                return i
            }
        }
    }
    return -1
}