P196 加油站

描述#

这个题目说的是，在一条环形公路上有 n 个加油站，编号是 0 ~ n-1。第 i 个加油站提供的油量是 gas[i]，从第 i 个加油站开到第 i+1 个加油站需要的油量是 cost[i]。

给你一辆油箱容量无限大的汽车，并且一开始油箱为空。你要计算出，是否可以从某个加油站开始，顺时针绕环形公路一周。如果可以，返回出发加油站的编号；否则，返回 -1。

注意，给你的 gas 数组和 cost 数组都不为空，并且长度相同。另外，这个题目保证，要么不存在绕行公路一周的方案，要么就只有唯一一个出发点，可以绕行公路一周。

比如说，给你的 gas 数组和 cost 数组是：
gas:  [1, 2, 4, 8]
cost: [4, 8, 1, 2]
只要从编号为 2 的加油站开始，就可以顺利绕行公路一周：
// 到达 3 号加油站时的油量
0 + 4 - 1 = 3
// 到达 0 号加油站时的油量
3 + 8 - 2 = 9
// 到达 1 号加油站时的油量
9 + 1 - 4 = 6
// 回到 2 号加油站时的油量
6 + 2 - 8 = 0
这样就从 2 号加油站出发，顺利绕行一周，回到 2 号加油站。因此你要返回的出发加油站编号就是 2。

代码#

public class AlgoCasts {

  // Time: O(n^2), Space: O(1)
  public int canCompleteCircuitBruteForce(int[] gas, int[] cost) {
    int n = gas.length;
    for (int i = 0; i < n; ++i) {
      int tank = 0;
      for (int j = i; j < i+n; ++j) {
        int k = j % n;
        tank += gas[k] - cost[k];
        if (tank < 0) break;
      }
      if (tank >= 0) return i;
    }
    return -1;
  }

  // Time: O(n), Space: O(1)
  public int canCompleteCircuitSkip(int[] gas, int[] cost) {
    int n = gas.length, j = 0;
    for (int i = 0; i < n; i = j+1) {
      int tank = 0;
      for (j = i; j < i+n; ++j) {
        int k = j % n;
        tank += gas[k] - cost[k];
        if (tank < 0) break;
      }
      if (tank >= 0) return i;
    }
    return -1;
  }

  // Time: O(n), Space: O(1)
  public int canCompleteCircuitGreedy(int[] gas, int[] cost) {
    int n = gas.length, start = 0;
    int total = 0, tank = 0;
    for (int i = 0; i < n; ++i) {
      total += gas[i] - cost[i];
      tank += gas[i] - cost[i];
      if (tank < 0) {
        start = i + 1;
        tank = 0;
      }
    }
    return total < 0 ? -1 : start;
  }

}