134.加油站

链接：134.加油站
难度：Medium
标签：贪心、数组
简介：在一条环路上有  N  个加油站，其中第  i  个加油站有汽油  gas[i]  升。你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1  个加油站需要消耗汽油  cost[i]  升。你从其中的一个加油站出发，开始时油箱为空。如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。

题解 1 - typescript

• 编辑时间：2020-11-18
• 执行用时：272ms
• 内存消耗：40.9MB
• 编程语言：typescript
• 解法介绍：选取首点进行遍历计算。

function canCompleteCircuit(gas: number[], cost: number[]): number {
  const len = gas.length;
  const starts: number[] = [];
  for (let i = 0; i < len; i++) {
    gas[i] >= cost[i] && starts.push(i);
  }
  for (const start of starts) {
    let arg = gas[start] - cost[start];
    let i = (start + 1) % len;
    while (i !== start) {
      arg += gas[i] - cost[i];
      if (arg < 0) break;
      i = (i + 1) % len;
    }
    if (i === start) return i;
  }
  return -1;
}

题解 2 - python

• 编辑时间：2024-10-06
• 执行用时：95ms
• 内存消耗：22.05MB
• 编程语言：python
• 解法介绍：对于每一个下标进行尝试，如果尝试失败则从下一个失败点进行尝试。

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        def run(start: int) -> Tuple[int, int]:
            i = start
            cur = gas[start]
            for _ in range(n):
                cur -= cost[i]
                if cur < 0: return (-1, (i + 1) % n)
                i = (i + 1) % n
                cur += gas[i]
            return (start, i)
        n = len(gas)
        start = 0
        while True:
            res, next = run(start)
            if res != -1: return res
            if next <= start: return -1
            start = next