力扣每日一題:134.加油站 貪心+暴力雙解

134.加油站

https://leetcode-cn.com/problems/gas-station/

難度:中等

題目:

在一條環(huán)路上有N個(gè)加油站,其中第i個(gè)加油站有汽油gas[i]升六荒。

你有一輛油箱容量無限的的汽車,從第 i 個(gè)加油站開往第 i+1個(gè)加油站需要消耗汽油cost[i]升。
你從其中的一個(gè)加油站出發(fā),開始時(shí)油箱為空勃刨。

如果你可以繞環(huán)路行駛一周柱嫌,則返回出發(fā)時(shí)加油站的編號,否則返回 -1桶蝎。

說明:

  • 如果題目有解,該答案即為唯一答案谅畅。
  • 輸入數(shù)組均為非空數(shù)組登渣,且長度相同。
  • 輸入數(shù)組中的元素均為非負(fù)數(shù)毡泻。

示例:

示例1:

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

輸出: 3

解釋:
從 3 號加油站(索引為 3 處)出發(fā)绍豁,可獲得 4 升汽油。此時(shí)油箱有 = 0 + 4 = 4 升汽油
開往 4 號加油站牙捉,此時(shí)油箱有 4 - 1 + 5 = 8 升汽油
開往 0 號加油站竹揍,此時(shí)油箱有 8 - 2 + 1 = 7 升汽油
開往 1 號加油站,此時(shí)油箱有 7 - 3 + 2 = 6 升汽油
開往 2 號加油站邪铲,此時(shí)油箱有 6 - 4 + 3 = 5 升汽油
開往 3 號加油站芬位,你需要消耗 5 升汽油,正好足夠你返回到 3 號加油站带到。
因此昧碉,3 可為起始索引。

示例 2:

輸入: 
gas  = [2,3,4]
cost = [3,4,3]

輸出: -1

解釋:
你不能從 0 號或 1 號加油站出發(fā),因?yàn)闆]有足夠的汽油可以讓你行駛到下一個(gè)加油站被饿。
我們從 2 號加油站出發(fā)四康,可以獲得 4 升汽油。 此時(shí)油箱有 = 0 + 4 = 4 升汽油
開往 0 號加油站狭握,此時(shí)油箱有 4 - 3 + 2 = 3 升汽油
開往 1 號加油站闪金,此時(shí)油箱有 3 - 3 + 3 = 3 升汽油
你無法返回 2 號加油站,因?yàn)榉党绦枰?4 升汽油论颅,但是你的油箱只有 3 升汽油哎垦。
因此,無論怎樣恃疯,你都不可能繞環(huán)路行駛一周漏设。

分析

暴力解法:
初看這道題,暴力解法大家應(yīng)該都能想到今妄,以每一個(gè)點(diǎn)為出發(fā)點(diǎn)嘗試循環(huán)郑口。
當(dāng)循環(huán)的index大于len(gas)時(shí),我們針對index對len(gas)求余即可始終保持?jǐn)?shù)組下標(biāo)不越界盾鳞。
這種方式的復(fù)雜度為O(n**2),雖然這道題通過了犬性,但是還是很有超時(shí)風(fēng)險(xiǎn)的。
貪心算法
在面試和日常刷題匯總雁仲,貪心思維的考點(diǎn)還是比較多的,同樣的這道題也可以通過貪心的做法來實(shí)現(xiàn)琐脏。
首先我們需要判斷如果sum(gas) < sum(cost)攒砖,那么無論如何選擇都沒辦法滿足條件。
反之日裙,如果sum(gas) >= sum(cost)吹艇,那么總有一點(diǎn)開始是可以滿足條件的。

此時(shí)昂拂,我們從gas[0]開始判斷受神,如果gas[0] < cost[0],我們就選擇下一個(gè)節(jié)點(diǎn)。
但如果我們gas[i] > cost[i] 但 gas[i+1] < cost[i+1]呢格侯?
此時(shí)表示我們剛才遍歷過的所有位置鼻听,都是沒辦法滿足條件的。
我們直接將初始值設(shè)置為i+2,油箱清零联四,繼續(xù)計(jì)算即可撑碴。這樣只需要O(n)的時(shí)間復(fù)雜度即可完成解題。

暴力法解題:

class Solution:
    def canCompleteCircuit(self, gas, cost):
        if sum(gas) < sum(cost):
            return -1
        ln = len(gas)
        for i in range(ln):
            if gas[i] < cost[i]:
                continue
            total = 0
            for j in range(i, i + ln):
                j %= ln
                total += gas[j] - cost[j]
                if total < 0:
                    break
            else:
                return i
        return -1

貪心算法解題:

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

歡迎關(guān)注我的公眾號: 清風(fēng)Python朝墩,帶你每日學(xué)習(xí)Python算法刷題的同時(shí)醉拓,了解更多python小知識。

我的個(gè)人博客:https://qingfengpython.cn

力扣解題合集:https://github.com/BreezePython/AlgorithmMarkdown

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個(gè)濱河市亿卤,隨后出現(xiàn)的幾起案子愤兵,更是在濱河造成了極大的恐慌,老刑警劉巖排吴,帶你破解...
    沈念sama閱讀 222,946評論 6 518
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件秆乳,死亡現(xiàn)場離奇詭異,居然都是意外死亡傍念,警方通過查閱死者的電腦和手機(jī)矫夷,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,336評論 3 399
  • 文/潘曉璐 我一進(jìn)店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來憋槐,“玉大人双藕,你說我怎么就攤上這事⊙糇校” “怎么了忧陪?”我有些...
    開封第一講書人閱讀 169,716評論 0 364
  • 文/不壞的土叔 我叫張陵,是天一觀的道長近范。 經(jīng)常有香客問我嘶摊,道長,這世上最難降的妖魔是什么评矩? 我笑而不...
    開封第一講書人閱讀 60,222評論 1 300
  • 正文 為了忘掉前任叶堆,我火速辦了婚禮,結(jié)果婚禮上斥杜,老公的妹妹穿的比我還像新娘虱颗。我一直安慰自己,他們只是感情好蔗喂,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,223評論 6 398
  • 文/花漫 我一把揭開白布忘渔。 她就那樣靜靜地躺著,像睡著了一般缰儿。 火紅的嫁衣襯著肌膚如雪畦粮。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 52,807評論 1 314
  • 那天乖阵,我揣著相機(jī)與錄音宣赔,去河邊找鬼。 笑死瞪浸,一個(gè)胖子當(dāng)著我的面吹牛拉背,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播默终,決...
    沈念sama閱讀 41,235評論 3 424
  • 文/蒼蘭香墨 我猛地睜開眼椅棺,長吁一口氣:“原來是場噩夢啊……” “哼犁罩!你這毒婦竟也來了?” 一聲冷哼從身側(cè)響起两疚,我...
    開封第一講書人閱讀 40,189評論 0 277
  • 序言:老撾萬榮一對情侶失蹤床估,失蹤者是張志新(化名)和其女友劉穎,沒想到半個(gè)月后诱渤,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體丐巫,經(jīng)...
    沈念sama閱讀 46,712評論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,775評論 3 343
  • 正文 我和宋清朗相戀三年勺美,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了递胧。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 40,926評論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡赡茸,死狀恐怖缎脾,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情占卧,我是刑警寧澤遗菠,帶...
    沈念sama閱讀 36,580評論 5 351
  • 正文 年R本政府宣布,位于F島的核電站华蜒,受9級特大地震影響辙纬,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜叭喜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,259評論 3 336
  • 文/蒙蒙 一贺拣、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧捂蕴,春花似錦譬涡、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,750評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽沟使。三九已至委可,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間腊嗡,已是汗流浹背着倾。 一陣腳步聲響...
    開封第一講書人閱讀 33,867評論 1 274
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留燕少,地道東北人卡者。 一個(gè)月前我還...
    沈念sama閱讀 49,368評論 3 379
  • 正文 我出身青樓,卻偏偏與公主長得像客们,于是被迫代替她去往敵國和親崇决。 傳聞我的和親對象是個(gè)殘疾皇子材诽,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,930評論 2 361

推薦閱讀更多精彩內(nèi)容

  • 在一條環(huán)路上有 N 個(gè)加油站,其中第 i 個(gè)加油站有汽油 gas[i] 升恒傻。你有一輛油箱容量無限的的汽車脸侥,從第 i...
    Herz21閱讀 780評論 0 0
  • 本題考察的是最大子序列和 題目描述 在一條環(huán)路上有 N 個(gè)加油站,其中第 i 個(gè)加油站有汽油 gas[i] 升盈厘。你...
    小怪獸大作戰(zhàn)閱讀 1,990評論 0 1
  • 題目 在一條環(huán)路上有 N 個(gè)加油站睁枕,其中第 i 個(gè)加油站有汽油 gas[i] 升。 你有一輛油箱容量無限的的汽車沸手,...
    CryFace閱讀 516評論 0 1
  • 134 Gas Station 加油站 Description:There are N gas stations ...
    air_melt閱讀 197評論 0 0
  • 題目鏈接難度:中等 類型: 數(shù)組 在一條環(huán)路上有 N 個(gè)加油站外遇,其中第 i 個(gè)加油站有汽油 g...
    wzNote閱讀 3,633評論 0 1