吴师兄学算法day08 贪心 134. 加油站

题目：134. 加油站

理解难点：

• 理解比较难，
• 就是遍历1遍，尽可能找局部满足要求的。如果总油耗满足要求。那局部油耗找的出发点就是对的。
• 遍历的时候，因为答案唯一，要么就满足要求，要么不满足要求。而<0 证明之前的都不满足要求，满足要求的一定在后面。
• 这题还是个环，环这里有点没太理解。环也是线的一种？

画图理解中：

我的代码：

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        cur_sum = 0
        total_sum = 0
        start = 0
        for i in range(len(gas)):
            # 每次计算油耗和总油耗
            cur_sum += gas[i] - cost[i]
            total_sum += gas[i] - cost[i]
            if cur_sum < 0:
                # 重新出发
                cur_sum = 0  # 油耗归零
                start = i + 1   # 重新出发
        # 现在start 存放的是尽可能满足要求的
        # 如果总油耗不为负数,则start是满足要求的
        if total_sum<0:
            return -1
        return start

老师的代码：

from typing import List


class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        # 获取加油站的数量
        n = len(gas)

        # 一开始，默认汽车储备的汽油数量为 0
        remainGas = 0

        # 需要统计一下，所有加油站的汽油总量能否支持汽车跑完所有的路程
        for i in range(n):
            remainGas += gas[i] - cost[i]

        # 如果发现加油站的汽油总量小于所有的路程需要消耗的汽油总量
        # 即汽车最终油箱汽油为负，那无论选择在哪出发，都不可能绕环路行驶一周
        print(remainGas)
        if remainGas < 0:
            return -1

        # 如果发现加油站的汽油总量大于或者等于所有的路程需要消耗的汽油总量
        # 那么可以绕环路行驶一周，接下来去寻找出发位置

        # 一开始，默认汽车此时储备的汽油数量为 0
        currentGas = 0

        # 一开始，默认汽车出发位置在索引为 0 的加油站
        i = 0

        # index 表示最终选择的出发点，默认为 0
        index = 0

        # 依次遍历每个加油站，在遍历的过程中，会执行一些【跳跃操作】
        while i < n:

            # 汽车在 i 号加油站加了 gas[i]
            # 开到 i + 1 号加油站消耗了 cost[i] 的汽油
            currentGas += gas[i] - cost[i]

            # 如果发现油箱里面的汽油是非负数
            # 即汽车可以开到  j 号加油站，j >= i + 1，那么就让汽车继续尝试往前开
            # 寻找出从 i 号加油站出发到最远的加油站的位置 j ，在这期间汽车是会从中间的加油站加油的
            if currentGas >= 0:
                print("此时油量为正数:", currentGas, "此时的i:", i)
                i += 1

            # 如果发现油箱里面的汽油是负数
            # 意味着汽车无法从 i 号加油站开到 j 号加油站，同时也意味着无法从 i + 1 号加油站开到 j 号加油站
            # 那么就直接尝试让汽车从 j 号加油站开始重新出发
            else:
                print("此时为负数:", currentGas)
                # 重新初始化汽车油箱油量
                currentGas = 0

                # 最终选择的出发点为 j 号加油站
                index = i + 1
                print("重新选择的加油站", index)

                # 开始出发
                i += 1
        print("最后邮箱:", currentGas)
        # 最终找到了合适的出发点
        return index


if __name__ == '__main__':
    obj = Solution()
    gas = [5, 2, 2, 7, 5, 5, 6, 1]
    cost = [3, 4, 5, 6, 7, 2, 1, 5]
    # diff = [2,-2,-3,1,-2,3,5,-4]
    print(obj.canCompleteCircuit(gas, cost))

卡尔的写法：

from typing import List


class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        curSum = 0  # 当前累计的剩余油量
        totalSum = 0  # 总剩余油量
        start = 0  # 起始位置

        for i in range(len(gas)):
            curSum += gas[i] - cost[i]
            totalSum += gas[i] - cost[i]

            if curSum < 0:  # 当前累计剩余油量curSum小于0
                start = i + 1  # 起始位置更新为i+1
                curSum = 0  # curSum重新从0开始累计

        # if totalSum < 0:
        #     return -1  # 总剩余油量totalSum小于0，说明无法环绕一圈

        return start

if __name__ == '__main__':
    obj = Solution()
    gas = [5, 2, 2, 7, 5, 5, 6, 1]
    cost = [3, 4, 5, 6, 7, 2, 1, 5]
    # diff = [2,-2,-3,1,-2,3,5,-4]
    print(obj.canCompleteCircuit(gas, cost))

github上的代码：

class Solution:
  def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
    ans = 0
    net = 0
    summ = 0

    # Try to start from each index.
    for i in range(len(gas)):
      net += gas[i] - cost[i]
      summ += gas[i] - cost[i]
      if summ < 0:
        summ = 0
        ans = i + 1  # Start from the next index.

    return -1 if net < 0 else ans

总结：

• 不行就抄一遍。
• 多画图，多理解。
• 不完全理解也没关系，边背边理解。
• 背诵中理解！
• 加油！！！

参考：

吴师兄：https://r07na4yqwor.feishu.cn/docx/KJ0OduxXfoGwMcxUs00cBX4onyr

卡尔代码及题解

github 大神代码：https://walkccc.me/LeetCode/problems/0134/#__tabbed_1_3