算法题--环形加油站问题

image.png

0. 链接

1. 题目

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.

Return the starting gas station's index if you can travel around the circuit once in the clockwise direction, otherwise return -1.

Note:

If there exists a solution, it is guaranteed to be unique.
Both input arrays are non-empty and have the same length.
Each element in the input arrays is a non-negative integer.
Example 1:

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

Output: 3

Explanation:
Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 4. Your tank = 4 - 1 + 5 = 8
Travel to station 0. Your tank = 8 - 2 + 1 = 7
Travel to station 1. Your tank = 7 - 3 + 2 = 6
Travel to station 2. Your tank = 6 - 4 + 3 = 5
Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3.
Therefore, return 3 as the starting index.

Example 2:

Input: 
gas  = [2,3,4]
cost = [3,4,3]

Output: -1
Explanation:
You can't start at station 0 or 1, as there is not enough gas to travel to the next station.
Let's start at station 2 and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 0. Your tank = 4 - 3 + 2 = 3
Travel to station 1. Your tank = 3 - 3 + 3 = 3
You cannot travel back to station 2, as it requires 4 unit of gas but you only have 3.
Therefore, you can't travel around the circuit once no matter where you start.

2. 思路1: 暴力搜索

基本思路是:

依次尝试每个起点, 看看按照行程行驶，能否回到起点

分析:

对于每个节点, 都要遍历一圈, 因此时间复杂度为O(n^2), 空间复杂度为O(1)

复杂度

时间复杂度 O(n^2)
空间复杂度 O(1)

3. 代码

# coding:utf8
from typing import List


class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        n = len(gas)
        if n == 0:
            return -1

        for start in range(n):
            if gas[start] < cost[start]:
                continue

            left_gas = gas[start] - cost[start]
            i = (start + 1) % n
            valid = True

            while i != start:
                left_gas += gas[i] - cost[i]
                if left_gas < 0:
                    valid = False
                    break
                i = (i + 1) % n

            if valid:
                return start

        return -1


def my_test(solution, gas, cost):
    print('input: gas={}, cost={}; output: {}'.format(
        gas, cost, solution.canCompleteCircuit(gas, cost)))


solution = Solution1()
my_test(solution, [1, 2, 3, 4, 5], [3, 4, 5, 1, 2])
my_test(solution, [1, 2, 3, 4, 3, 2, 4, 1, 5, 3, 2, 4], [1, 1, 1, 3, 2, 4, 3, 6, 7, 4, 3, 1])

输出结果

input: gas=[1, 2, 3, 4, 5], cost=[3, 4, 5, 1, 2]; output: 3
input: gas=[1, 2, 3, 4, 3, 2, 4, 1, 5, 3, 2, 4], cost=[1, 1, 1, 3, 2, 4, 3, 6, 7, 4, 3, 1]; output: -1

4. 结果

image.png

5. 思路2: 得寸进尺法

过程

分析问题，可以得出两个结论:
(1) 如果存在答案，则每个节点都需要经过1次，然后绕回起点
(2) 如果存在答案, 则所有节点处的gas之和, 大于所有路程中的cost
先随机假设一个起点, 假设start = n - 1,则判断它是否能到达下一步 end = 0, 只需要判断left_gas = gas[start] - cost[start] >= 0是否成立,
- 如果成立, 就计算一下剩余gas量left_gas += gas[end] - cost[end], 然后把终点再向后移动一位end += 1
- 如果不成立, 说明起点gas不够, 就采取以退为进的办法, start -= 1, left_gas += gas[start] - cost[start]
按照这个步骤，如果start和end又在中间相遇，此时判断left_gas>=0是否成立，如果成立，说明start就是那个闪亮的起点; 否则说明环形不可达, 返回-1

分析
利用此法, 在两个指针start和end的帮助下，每个节点只被遍历1次，就得出了结论，时间复杂度降低到了O(n), 空间复杂度仍然是O(1)
时间复杂度 O(n)
空间复杂度 O(1)

6. 代码

# coding:utf8
from typing import List


class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        n = len(gas)
        if n == 0:
            return -1

        start = n - 1
        end = 0
        left_gas = gas[start] - cost[start]
        while start > end:
            if left_gas >= 0:
                left_gas += gas[end] - cost[end]
                end += 1
            else:
                start -= 1
                left_gas += gas[start] - cost[start]

        return start if left_gas >= 0 else -1


def my_test(solution, gas, cost):
    print('input: gas={}, cost={}; output: {}'.format(
        gas, cost, solution.canCompleteCircuit(gas, cost)))


solution = Solution()
my_test(solution, [1, 2, 3, 4, 5], [3, 4, 5, 1, 2])
my_test(solution, [1, 2, 3, 4, 3, 2, 4, 1, 5, 3, 2, 4], [1, 1, 1, 3, 2, 4, 3, 6, 7, 4, 3, 1])

输出结果

input: gas=[1, 2, 3, 4, 5], cost=[3, 4, 5, 1, 2]; output: 3
input: gas=[1, 2, 3, 4, 3, 2, 4, 1, 5, 3, 2, 4], cost=[1, 1, 1, 3, 2, 4, 3, 6, 7, 4, 3, 1]; output: -1

7. 结果

image.png