算法題--環(huán)形加油站問題

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: 暴力搜索

基本思路是:

依次嘗試每個(gè)起點(diǎn), 看看按照行程行駛益兄，能否回到起點(diǎn)

分析:

對于每個(gè)節(jié)點(diǎn), 都要遍歷一圈, 因此時(shí)間復(fù)雜度為O(n^2), 空間復(fù)雜度為O(1)

復(fù)雜度

時(shí)間復(fù)雜度 O(n^2)
空間復(fù)雜度 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])

輸出結(jié)果

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. 結(jié)果

image.png

5. 思路2: 得寸進(jìn)尺法

過程

分析問題蠢正，可以得出兩個(gè)結(jié)論:
(1) 如果存在答案锻霎，則每個(gè)節(jié)點(diǎn)都需要經(jīng)過1次遣疯，然后繞回起點(diǎn)
(2) 如果存在答案, 則所有節(jié)點(diǎn)處的gas之和, 大于所有路程中的cost
先隨機(jī)假設(shè)一個(gè)起點(diǎn), 假設(shè)start = n - 1,則判斷它是否能到達(dá)下一步 end = 0, 只需要判斷left_gas = gas[start] - cost[start] >= 0是否成立,
- 如果成立, 就計(jì)算一下剩余gas量left_gas += gas[end] - cost[end], 然后把終點(diǎn)再向后移動(dòng)一位end += 1
- 如果不成立, 說明起點(diǎn)gas不夠, 就采取以退為進(jìn)的辦法, start -= 1, left_gas += gas[start] - cost[start]
按照這個(gè)步驟，如果start和end又在中間相遇饼丘，此時(shí)判斷left_gas>=0是否成立笼恰，如果成立，說明start就是那個(gè)閃亮的起點(diǎn); 否則說明環(huán)形不可達(dá), 返回-1

分析
利用此法, 在兩個(gè)指針start和end的幫助下朴则，每個(gè)節(jié)點(diǎn)只被遍歷1次权纤，就得出了結(jié)論，時(shí)間復(fù)雜度降低到了O(n), 空間復(fù)雜度仍然是O(1)
時(shí)間復(fù)雜度 O(n)
空間復(fù)雜度 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])

輸出結(jié)果

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. 結(jié)果

image.png