當(dāng)前位置:首頁(yè) > 公眾號(hào)精選 > 程序員小灰
[導(dǎo)讀]讀完本文,可以去力扣解決如下題目:134.加油站(Medium)今天講一個(gè)貪心的老司機(jī)的故事,就是力扣第134題「加油站」:題目應(yīng)該不難理解,就是每到達(dá)一個(gè)站點(diǎn)i,可以加gas[i]升油,但離開(kāi)站點(diǎn)i需要消耗cost[i]升油,問(wèn)你從哪個(gè)站點(diǎn)出發(fā),可以兜一圈回來(lái)。要說(shuō)暴力解法,肯...

讀完本文,可以去力扣解決如下題目:134.加油站(Medium

今天講一個(gè)貪心的老司機(jī)的故事,就是力扣第 134 題「加油站」:

題目應(yīng)該不難理解,就是每到達(dá)一個(gè)站點(diǎn)i,可以加gas[i]升油,但離開(kāi)站點(diǎn)i需要消耗cost[i]升油,問(wèn)你從哪個(gè)站點(diǎn)出發(fā),可以兜一圈回來(lái)。

要說(shuō)暴力解法,肯定很容易想到,用一個(gè) for 循環(huán)遍歷所有站點(diǎn),假設(shè)為起點(diǎn),然后再套一層 for 循環(huán),判斷一下是否能夠轉(zhuǎn)一圈回到起點(diǎn):

int?n?=?gas.length;
for?(int?start?=?0;?start?????for?(int?step?=?0;?step?????????int?i?=?(start? ?step)?%?n;
????????tank? =?gas[i];
????????tank?-=?cost[i];
????????//?判斷油箱中的油是否耗盡
????}
}
很明顯時(shí)間復(fù)雜度是 O(N^2),這么簡(jiǎn)單粗暴的解法一定不是最優(yōu)的,我們?cè)噲D分析一下是否有優(yōu)化的余地。

暴力解法是否有重復(fù)計(jì)算的部分?是否可以抽象出「狀態(tài)」,是否對(duì)同一個(gè)「狀態(tài)」重復(fù)計(jì)算了多次?

以前講動(dòng)態(tài)規(guī)劃算法時(shí)候,我曾經(jīng)說(shuō)過(guò),變化的量就是「狀態(tài)」。那么觀察這個(gè)暴力窮舉的過(guò)程,變化的量有兩個(gè),分別是「起點(diǎn)」和「當(dāng)前油箱的油量」,但這兩個(gè)狀態(tài)的組合肯定有不下 O(N^2) 種,顯然沒(méi)有任何優(yōu)化的空間

所以說(shuō)這道題肯定不是通過(guò)簡(jiǎn)單的剪枝來(lái)優(yōu)化暴力解法的效率,而是需要我們發(fā)現(xiàn)一些隱藏較深的規(guī)律,從而減少一些冗余的計(jì)算

下面我們介紹兩種方法巧解這道題,分別是數(shù)學(xué)圖像解法和貪心解法。

圖像解法

汽車(chē)進(jìn)入站點(diǎn)i可以加gas[i]的油,離開(kāi)站點(diǎn)會(huì)損耗cost[i]的油,那么可以把站點(diǎn)和與其相連的路看做一個(gè)整體,將gas[i] - cost[i]作為經(jīng)過(guò)站點(diǎn)i的油量變化值:

這樣,題目描述的場(chǎng)景就被抽象成了一個(gè)環(huán)形數(shù)組,數(shù)組中的第i個(gè)元素就是gas[i] - cost[i]。

有了這個(gè)環(huán)形數(shù)組,我們需要判斷這個(gè)環(huán)形數(shù)組中是否能夠找到一個(gè)起點(diǎn)start,使得從這個(gè)起點(diǎn)開(kāi)始的累加和一直大于等于 0。

如何判斷是否存在這樣一個(gè)起點(diǎn)start?又如何計(jì)算這個(gè)起點(diǎn)start的值呢?

我們不妨就把 0 作為起點(diǎn),計(jì)算累加和的代碼非常簡(jiǎn)單:

int?n?=?gas.length,?sum?=?0;
for?(int?i?=?0;?i?????//?計(jì)算累加和
????sum? =?gas[i]?-?cost[i];
}
sum就相當(dāng)于是油箱中油量的變化,上述代碼中sum的變化過(guò)程可能是這樣的:

顯然,上圖將 0 作為起點(diǎn)肯定是不行的,因?yàn)?code style="font-size: inherit;line-height: inherit;padding: 2px 4px;border-radius: 4px;margin-right: 2px;margin-left: 2px;color: rgb(233, 105, 0);background: rgb(248, 248, 248);">sum在變化的過(guò)程中小于 0 了,不符合我們「累加和一直大于等于 0」的要求。

那如果 0 不能作為起點(diǎn),誰(shuí)可以作為起點(diǎn)呢?

看圖說(shuō)話,圖像的最低點(diǎn)最有可能可以作為起點(diǎn):

如果把這個(gè)「最低點(diǎn)」作為起點(diǎn),就是說(shuō)將這個(gè)點(diǎn)作為坐標(biāo)軸原點(diǎn),就相當(dāng)于把圖像「最大限度」向上平移了。

再加上這個(gè)數(shù)組是環(huán)形數(shù)組,最低點(diǎn)左側(cè)的圖像可以接到圖像的最右側(cè):

這樣,整個(gè)圖像都保持在 x 軸以上,所以這個(gè)最低點(diǎn) 4,就是題目要求我們找的起點(diǎn)。

不過(guò),經(jīng)過(guò)平移后圖像一定全部在 x 軸以上嗎?不一定,因?yàn)檫€有無(wú)解的情況:

如果sum(gas[...]) < sum(cost[...]),總油量小于總的消耗,那肯定是沒(méi)辦法環(huán)游所有站點(diǎn)的。

綜上,我們就可以寫(xiě)出代碼:

int?canCompleteCircuit(int[]?gas,?int[]?cost)?{
????int?n?=?gas.length;
????//?相當(dāng)于圖像中的坐標(biāo)點(diǎn)和最低點(diǎn)
????int?sum?=?0,?minSum?=?Integer.MAX_VALUE;
????int?start?=?0;
????for?(int?i?=?0;?i?????????sum? =?gas[i]?-?cost[i];
????????if?(sum?????????????//?經(jīng)過(guò)第 i 個(gè)站點(diǎn)后,使 sum 到達(dá)新低
????????????//?所以站點(diǎn)?i? ?1?就是最低點(diǎn)(起點(diǎn))
????????????start?=?i? ?1;
????????????minSum?=?sum;
????????}
????}
????if?(sum?0)?{
????????//?總油量小于總的消耗,無(wú)解
????????return?-1;
????}
????//?環(huán)形數(shù)組特性
????return?start?==?n???0?:?start;
}
以上是觀察函數(shù)圖像得出的解法,時(shí)間復(fù)雜度為 O(N),比暴力解法的效率高很多。

下面我們介紹一種使用貪心思路寫(xiě)出的解法,和上面這個(gè)解法比較相似,不過(guò)分析過(guò)程不盡相同。

貪心解法

用貪心思路解決這道題的關(guān)鍵在于以下這個(gè)結(jié)論:

如果選擇站點(diǎn)i作為起點(diǎn)「恰好」無(wú)法走到站點(diǎn)j,那么ij中間的任意站點(diǎn)k都不可能作為起點(diǎn)

比如說(shuō),如果從站點(diǎn)1出發(fā),走到站點(diǎn)5時(shí)油箱中的油量「恰好」減到了負(fù)數(shù),那么說(shuō)明站點(diǎn)1「恰好」無(wú)法到達(dá)站點(diǎn)5;那么你從站點(diǎn)2,3,4任意一個(gè)站點(diǎn)出發(fā)都無(wú)法到達(dá)5,因?yàn)榈竭_(dá)站點(diǎn)5時(shí)油箱的油量也必然被減到負(fù)數(shù)。

如何證明這個(gè)結(jié)論?

假設(shè)tank記錄當(dāng)前油箱中的油量,如果從站點(diǎn)i出發(fā)(tank = 0),走到j時(shí)恰好出現(xiàn)tank < 0的情況,那說(shuō)明走到i, j之間的任意站點(diǎn)k時(shí)都滿(mǎn)足tank > 0,對(duì)吧。

如果把k作為起點(diǎn)的話,相當(dāng)于在站點(diǎn)k時(shí)tank = 0,那走到j時(shí)必然有tank < 0,也就是說(shuō)k肯定不能是起點(diǎn)。

拜托,從i出發(fā)走到k好歹tank > 0,都無(wú)法達(dá)到j,現(xiàn)在你還讓tank = 0了,那更不可能走到j了對(duì)吧。

綜上,這個(gè)結(jié)論就被證明了。

回想一下我們開(kāi)頭說(shuō)的暴力解法是怎么做的?

如果我發(fā)現(xiàn)從i出發(fā)無(wú)法走到j,那么顯然i不可能是起點(diǎn)。

現(xiàn)在,我們發(fā)現(xiàn)了一個(gè)新規(guī)律,可以推導(dǎo)出什么?

如果我發(fā)現(xiàn)從i出發(fā)無(wú)法走到j,那么i以及i, j之間的所有站點(diǎn)都不可能作為起點(diǎn)。

看到冗余計(jì)算了嗎?看到優(yōu)化的點(diǎn)了嗎?

這就是貪心思路的本質(zhì),如果找不到重復(fù)計(jì)算,那就通過(guò)問(wèn)題中一些隱藏較深的規(guī)律,來(lái)減少冗余計(jì)算

根據(jù)這個(gè)結(jié)論,就可以寫(xiě)出如下代碼:

int?canCompleteCircuit(int[]?gas,?int[]?cost)?{
????int?n?=?gas.length;
????int?sum?=?0;
????for?(int?i?=?0;?i?????????sum? =?gas[i]?-?cost[i];
????}
????if?(sum?0)?{
????????//?總油量小于總的消耗,無(wú)解
????????return?-1;
????}
????//?記錄油箱中的油量
????int?tank?=?0;
????//?記錄起點(diǎn)
????int?start?=?0;
????for?(int?i?=?0;?i?????????tank? =?gas[i]?-?cost[i];
????????if?(tank?0)?{
????????????//?無(wú)法從?start?走到?i
????????????//?所以站點(diǎn)?i? ?1?應(yīng)該是起點(diǎn)
????????????tank?=?0;
????????????start?=?i? ?1;
????????}
????}
????return?start?==?n???0?:?start;
}
這個(gè)解法的時(shí)間復(fù)雜度也是 O(N),和之前圖像法的解題思路有所不同,但代碼非常類(lèi)似。

其實(shí),你可以把這個(gè)解法的思路結(jié)合圖像來(lái)思考,可以發(fā)現(xiàn)它們本質(zhì)上是一樣的,只是理解方式不同而已。

對(duì)于這種貪心算法,沒(méi)有特別套路化的思維框架,主要還是靠多做題多思考,將題目的場(chǎng)景進(jìn)行抽象的聯(lián)想,找出隱藏其中的規(guī)律,從而減少計(jì)算量,進(jìn)行效率優(yōu)化。

好了,這道題就講到這里,希望對(duì)你拓寬思路有幫助。

_____________

本站聲明: 本文章由作者或相關(guān)機(jī)構(gòu)授權(quán)發(fā)布,目的在于傳遞更多信息,并不代表本站贊同其觀點(diǎn),本站亦不保證或承諾內(nèi)容真實(shí)性等。需要轉(zhuǎn)載請(qǐng)聯(lián)系該專(zhuān)欄作者,如若文章內(nèi)容侵犯您的權(quán)益,請(qǐng)及時(shí)聯(lián)系本站刪除。
關(guān)閉
關(guān)閉