算法題--環(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: 暴力搜索

  1. 基本思路是:
  • 依次嘗試每個(gè)起點(diǎn), 看看按照行程行駛益兄,能否回到起點(diǎn)
  1. 分析:
  • 對于每個(gè)節(jié)點(diǎn), 都要遍歷一圈, 因此時(shí)間復(fù)雜度為O(n^2), 空間復(fù)雜度為O(1)
  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)尺法

  1. 過程
  • 分析問題蠢正,可以得出兩個(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è)步驟,如果startend又在中間相遇饼丘, 此時(shí)判斷left_gas>=0是否成立笼恰,如果成立,說明start就是那個(gè)閃亮的起點(diǎn); 否則說明環(huán)形不可達(dá), 返回-1
  1. 分析
    利用此法, 在兩個(gè)指針startend的幫助下朴则,每個(gè)節(jié)點(diǎn)只被遍歷1次权纤,就得出了結(jié)論,時(shí)間復(fù)雜度降低到了O(n), 空間復(fù)雜度仍然是O(1)
  2. 時(shí)間復(fù)雜度 O(n)
  3. 空間復(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
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末乌妒,一起剝皮案震驚了整個(gè)濱河市汹想,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌撤蚊,老刑警劉巖古掏,帶你破解...
    沈念sama閱讀 222,807評論 6 518
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異侦啸,居然都是意外死亡冗茸,警方通過查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,284評論 3 399
  • 文/潘曉璐 我一進(jìn)店門匹中,熙熙樓的掌柜王于貴愁眉苦臉地迎上來夏漱,“玉大人,你說我怎么就攤上這事顶捷」掖拢” “怎么了?”我有些...
    開封第一講書人閱讀 169,589評論 0 363
  • 文/不壞的土叔 我叫張陵,是天一觀的道長葵蒂。 經(jīng)常有香客問我交播,道長,這世上最難降的妖魔是什么践付? 我笑而不...
    開封第一講書人閱讀 60,188評論 1 300
  • 正文 為了忘掉前任秦士,我火速辦了婚禮,結(jié)果婚禮上永高,老公的妹妹穿的比我還像新娘隧土。我一直安慰自己,他們只是感情好命爬,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,185評論 6 398
  • 文/花漫 我一把揭開白布曹傀。 她就那樣靜靜地躺著,像睡著了一般饲宛。 火紅的嫁衣襯著肌膚如雪皆愉。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 52,785評論 1 314
  • 那天艇抠,我揣著相機(jī)與錄音幕庐,去河邊找鬼。 笑死家淤,一個(gè)胖子當(dāng)著我的面吹牛异剥,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播媒鼓,決...
    沈念sama閱讀 41,220評論 3 423
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼错妖!你這毒婦竟也來了绿鸣?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 40,167評論 0 277
  • 序言:老撾萬榮一對情侶失蹤暂氯,失蹤者是張志新(化名)和其女友劉穎潮模,沒想到半個(gè)月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體痴施,經(jīng)...
    沈念sama閱讀 46,698評論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡擎厢,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,767評論 3 343
  • 正文 我和宋清朗相戀三年,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了辣吃。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片动遭。...
    茶點(diǎn)故事閱讀 40,912評論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡,死狀恐怖神得,靈堂內(nèi)的尸體忽然破棺而出厘惦,到底是詐尸還是另有隱情,我是刑警寧澤哩簿,帶...
    沈念sama閱讀 36,572評論 5 351
  • 正文 年R本政府宣布宵蕉,位于F島的核電站酝静,受9級特大地震影響,放射性物質(zhì)發(fā)生泄漏羡玛。R本人自食惡果不足惜别智,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,254評論 3 336
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望稼稿。 院中可真熱鬧薄榛,春花似錦、人聲如沸渺杉。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,746評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽是越。三九已至耳舅,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間倚评,已是汗流浹背浦徊。 一陣腳步聲響...
    開封第一講書人閱讀 33,859評論 1 274
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留天梧,地道東北人盔性。 一個(gè)月前我還...
    沈念sama閱讀 49,359評論 3 379
  • 正文 我出身青樓,卻偏偏與公主長得像呢岗,于是被迫代替她去往敵國和親冕香。 傳聞我的和親對象是個(gè)殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,922評論 2 361