LeetCode 算法题库【134】——加油站

加油站

题目描述：

解题思路：

• 第一种：贪心算法。这道题通过读题很好发现一个特点，就是如果总的汽油量小于总的耗油量，那么是完全不可能绕一周的，所以这样的情况下，直接返回-1。从头开始遍历，到第i个加油站时，若剩余的油量小于消耗的油量，则不能到达下一站，而且无论从i之前的哪一个加油站开始出发，都不能到达i+1站，所以，每次出现这种情况的时候，都要从i+1开始，若从这里开始能达到最后一个加油站，说明也一定能环绕。
• 时间复杂度：O(N)

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        if sum(gas) < sum(cost):
            return -1
        differ_oil = 0
        start = 0
        for i in range(len(gas)):
            differ_oil += gas[i] - cost[i]
            if differ_oil < 0:
                start = i + 1
                differ_oil = 0
        return start

• 第二种：反向遍历版贪心算法。这个方法前提和第一种一样，首先需要保证这个总的汽油量大于或等于总的耗油量，否则就说明不能绕路一周。先将每个加油站能加的油和到下一个加油站消耗的油的差都算出来并放入数组differ_oil中保存，然后我们需要建立一个长度为len(gas)的数组来保存从后往前每次到达一个加油站所剩下的油，我们是通过先建立一个len(gas)-1长度的空数组，然后在最后append数组differ_oil的最后一个差值来得到。然后我们从len(gas)-2这个位置开始往前遍历，每次都将剩余的油量赋值给result相应位置。通过这道题的原理，因为如果总的汽油量比耗油量更大是一定可以绕路一周，所以我们从剩余油量最大的位置开始循环，就可以成功完成一次绕路。所以最后返回这个最大剩余油量的位置即可。
• 时间复杂度：O(N)

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        if sum(gas) < sum(cost):
            return -1
        differ_oil = []
        for i in range(len(gas)):
            differ_oil.append(gas[i] - cost[i])
        result = [_ for _ in range(len(gas) - 1)]
        result.append(differ_oil[len(gas) - 1])
        for j in range(len(gas) - 2, -1, -1):
            result[j] = result[j+1] + differ_oil[j]
        return result.index(max(result))