加油站-中等

难度：中等

题目描述：
在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。

说明:

如果题目有解，该答案即为唯一答案。
输入数组均为非空数组，且长度相同。
输入数组中的元素均为非负数。

示例：

输入:
gas  = [1,2,3,4,5]
cost = [3,4,5,1,2]

输出: 3

解释:
从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油
开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油
开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油
开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油
开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。
因此，3 可为起始索引。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

解题思路：
首先计算可以从那几站出发，然后计算是否可行

var canCompleteCircuit = function (gas, cost) {
  let len = gas.length;
  let arr = [];
  let num = -1;
  for (let i = 0; i < len; i++) {
    if (gas[i] >= cost[i]) {
      arr.push(i);
    }
  }
  for (let i = 0; i < arr.length; i++) {
    let newg = gas.slice(arr[i]);
    newg.push(...gas.slice(0, arr[i]));
    let newc = cost.slice(arr[i]);
    newc.push(...cost.slice(0, arr[i]));
    let result = 0;
    for (let j = 0; j < newg.length; j++) {
      result += newg[j] - newc[j];
      if (result < 0) {
        break;
      }
    }
    if (result >= 0) {
      num = arr[i];
      break;
    }
  }
  return num;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

1.首先要明白,总的汽油量要大于总路程，如果连这个目标都达不到，说明这个车子一定开不到终点
2.我们从第一个位置开始，如果中途断了，那么刚刚走过的路，也是在此地就中断的，因此我们只需要在断点开始（作为起始点），如果能走到终点，就能到达所有的地方

var canCompleteCircuit = function (gas, cost) {
  let gasCode = 0;
  let costCode = 0;
  for (let i = 0; i < gas.length; i++) {
    gasCode += gas[i];
  }
  for (let i = 0; i < gas.length; i++) {
    costCode += cost[i];
  }
  if (gasCode < costCode) {
    return -1;
  }
  let currentGas = 0;
  let start = 0;
  for (let i = 0; i < gas.length; i++) {
    currentGas = currentGas - cost[i] + gas[i];
    if (currentGas < 0) {
      currentGas = 0;
      start = i + 1;
    }
  }
  return start;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

← 寻找重复数-中等电话号码的字母组合-中等 →

# 加油站-中等

加油站-中等