leetcode(力扣) 134. 加油站 (贪心 & 两种情况，老司机逻辑题)

题目描述

在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。
给定两个整数数组 gas 和 cost ，如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。

示例 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 可为起始索引。

示例 2:
输入: gas = [2,3,4], cost = [3,4,3]
输出: -1
解释:
你不能从 0 号或 1 号加油站出发，因为没有足够的汽油可以让你行驶到下一个加油站。
我们从 2 号加油站出发，可以获得 4 升汽油。 此时油箱有 = 0 + 4 = 4 升汽油
开往 0 号加油站，此时油箱有 4 - 3 + 2 = 3 升汽油
开往 1 号加油站，此时油箱有 3 - 3 + 3 = 3 升汽油
你无法返回 2 号加油站，因为返程需要消耗 4 升汽油，但是你的油箱只有 3 升汽油。
因此，无论怎样，你都不可能绕环路行驶一周。

思路分析

感觉这是一道逻辑题。经常开长途高速的司机朋友应该比较容易懂？？玄学了。。。

首先 ，如果总加油量 gas 小于总消耗量 cost，那么这一圈是肯定开不回来的，这不用说。

另外还有一个情况就是，如果我们确定能走完一圈，那么要把总亏损最多的那一站留在最后再走，也就是从总亏损最多的加油站的后面一个作为起点，让前面尽量累计多一点油给后面用。

举个例子，力扣里的测试用例，gas = [5,1,2,3,4],cost = [4,4,1,5,1]。
从0开始 对应位置相减可以算的本站的剩余油量情况。
得到剩余油量数组 temp = [1,-3,1,-2,3]。
将剩余油量相加，到下标3时的总亏损最多，为 -3。
所以要从4号开始前面累计足够多的油给下标为3时，即总亏损最多的加油站用。

能用这种逻辑的条件就是题目所给的，如有答案，则保证答案唯一。

还有一个小细节，如果总亏损最大的加油站在最后一站，那么就要从起点开始。

完整代码

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        sum_cost = 0
        sum_gas = 0
        temp =0  
  
        temp_min = float('inf') # 记录总亏损的最大值。
        res = 0
        for i in range(len(gas)):
            temp += gas[i]-cost[i]   # 当前的总亏损值
            if temp_min > temp:   # 出现更小的值，即出现更大的亏损
                temp_min = temp
                res = i  # 记录此时下标
            sum_cost += cost[i]
            sum_gas += gas[i]
        if sum_gas<sum_cost: # 确保有答案。
            return -1
        return 0 if res+1 == len(gas) else res+1  #总亏损为最后一站，则从起点开始
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

---

最近又看到这道题了，leetcode官方更新了新的测试用例 上面的代码A不了了。

新用例很长，大概就是 gas[2,0,0,0,0] cost [0,1,0,0,0]。

按照之前的思路 ，那就是从下标为2的地方开始走，此时油箱为0所以走不了。

额绝了，最后加个特判就行了，如果起点的油是0，就吧起点往后挪一个位置。

新代码

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        temp = []
        su_gas = 0
        su_cost = 0
        for i in range(len(gas)):
            su_gas +=gas[i]
            su_cost +=cost[i]
            if len(temp)!=0:
                temp.append(gas[i]-cost[i]+temp[i-1])
            else:
                temp.append(gas[i]-cost[i])
        num = min(temp)
        inx = temp.index(num)
        if  su_gas<su_cost:
            return -1
        while inx+1<len(gas) and gas[inx+1] == 0  :
            inx+=1
        return inx+1 if inx+1<len(temp) else 0


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