貪心三:加油站

題目地址: https://leetcode-cn.com/problems/gas-station/

題目描述:
在一條環(huán)路上有 N 個(gè)加油站观谦,其中第 i 個(gè)加油站有汽油 gas[i] 升。
你有一輛油箱容量無(wú)限的的汽車桨菜,從第 i 個(gè)加油站開往第 i+1 個(gè)加油站需要消耗汽油 cost[i] 升豁状。你從其中的一個(gè)加油站出發(fā),開始時(shí)油箱為空倒得。
如果你可以繞環(huán)路行駛一周泻红,則返回出發(fā)時(shí)加油站的編號(hào),否則返回 -1谊路。
說明:
如果題目有解菩彬,該答案即為唯一答案。
輸入數(shù)組均為非空數(shù)組惨恭,且長(zhǎng)度相同耙旦。
輸入數(shù)組中的元素均為非負(fù)數(shù)。
示例 1: 輸入: gas = [1,2,3,4,5] cost = [3,4,5,1,2]
輸出: 3 解釋: 從 3 號(hào)加油站(索引為 3 處)出發(fā)锉罐,可獲得 4 升汽油绕娘。此時(shí)油箱有 = 0 + 4 = 4 升汽油 開往 4 號(hào)加油站,此時(shí)油箱有 4 - 1 + 5 = 8 升汽油 開往 0 號(hào)加油站侨舆,此時(shí)油箱有 8 - 2 + 1 = 7 升汽油 開往 1 號(hào)加油站升酣,此時(shí)油箱有 7 - 3 + 2 = 6 升汽油 開往 2 號(hào)加油站噩茄,此時(shí)油箱有 6 - 4 + 3 = 5 升汽油 開往 3 號(hào)加油站复颈,你需要消耗 5 升汽油,正好足夠你返回到 3 號(hào)加油站凿菩。 因此帜讲,3 可為起始索引。
示例 2: 輸入: gas = [2,3,4] cost = [3,4,3]
輸出: -1 解釋: 你不能從 0 號(hào)或 1 號(hào)加油站出發(fā)获黔,因?yàn)闆]有足夠的汽油可以讓你行駛到下一個(gè)加油站在验。 我們從 2 號(hào)加油站出發(fā),可以獲得 4 升汽油腋舌。 此時(shí)油箱有 = 0 + 4 = 4 升汽油 開往 0 號(hào)加油站,此時(shí)油箱有 4 - 3 + 2 = 3 升汽油 開往 1 號(hào)加油站赞辩,此時(shí)油箱有 3 - 3 + 3 = 3 升汽油 你無(wú)法返回 2 號(hào)加油站授艰,因?yàn)榉党绦枰?4 升汽油,但是你的油箱只有 3 升汽油召庞。 因此来破,無(wú)論怎樣忘古,你都不可能繞環(huán)路行駛一周。
參考代碼:

class Solution {
public:
    int canCompleteCircuit(vector<int> gas, vector<int> cost) {
        
        int total = 0;
        for (int i = 0; i<gas.size(); i++) {
            total = total + gas[i] - cost[i];
        }
        if (total <0) {
            return  -1;
        }
        int current = 0;
        int index = 0;
        for (int i = 0; i<gas.size(); i++) {
            current = current + gas[i] - cost[i];
            if (current < 0) { // 在有解的條件下送朱,如果 (i,j) < 0, 那么 (i+k,j)也小于0
                index = i + 1;
                current = 0;
            }
        }
        return index;
    }
};

參考鏈接: https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0134.%E5%8A%A0%E6%B2%B9%E7%AB%99.md

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末炮沐,一起剝皮案震驚了整個(gè)濱河市回怜,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌翔试,老刑警劉巖,帶你破解...
    沈念sama閱讀 223,002評(píng)論 6 519
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件垦缅,死亡現(xiàn)場(chǎng)離奇詭異壁涎,居然都是意外死亡志秃,警方通過查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,357評(píng)論 3 400
  • 文/潘曉璐 我一進(jìn)店門庞溜,熙熙樓的掌柜王于貴愁眉苦臉地迎上來碑定,“玉大人,你說我怎么就攤上這事漫试。” “怎么了驾荣?”我有些...
    開封第一講書人閱讀 169,787評(píng)論 0 365
  • 文/不壞的土叔 我叫張陵播掷,是天一觀的道長(zhǎng)撼班。 經(jīng)常有香客問我,道長(zhǎng)砰嘁,這世上最難降的妖魔是什么勘究? 我笑而不...
    開封第一講書人閱讀 60,237評(píng)論 1 300
  • 正文 為了忘掉前任口糕,我火速辦了婚禮走净,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘伏伯。我一直安慰自己捌袜,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,237評(píng)論 6 398
  • 文/花漫 我一把揭開白布弄唧。 她就那樣靜靜地躺著霍衫,像睡著了一般。 火紅的嫁衣襯著肌膚如雪澄干。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 52,821評(píng)論 1 314
  • 那天麸俘,我揣著相機(jī)與錄音惧笛,去河邊找鬼。 笑死患整,一個(gè)胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的紧憾。 我是一名探鬼主播嘲碧,決...
    沈念sama閱讀 41,236評(píng)論 3 424
  • 文/蒼蘭香墨 我猛地睜開眼父阻,長(zhǎng)吁一口氣:“原來是場(chǎng)噩夢(mèng)啊……” “哼望抽!你這毒婦竟也來了煤篙?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 40,196評(píng)論 0 277
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤辑奈,失蹤者是張志新(化名)和其女友劉穎鸠窗,沒想到半個(gè)月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體稍计,經(jīng)...
    沈念sama閱讀 46,716評(píng)論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡臣嚣,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,794評(píng)論 3 343
  • 正文 我和宋清朗相戀三年硅则,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片怎虫。...
    茶點(diǎn)故事閱讀 40,928評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡困介,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出饥努,到底是詐尸還是另有隱情,我是刑警寧澤酷愧,帶...
    沈念sama閱讀 36,583評(píng)論 5 351
  • 正文 年R本政府宣布溶浴,位于F島的核電站,受9級(jí)特大地震影響士败,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜谅将,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,264評(píng)論 3 336
  • 文/蒙蒙 一饥臂、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧隅熙,春花似錦、人聲如沸囚戚。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,755評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)庐橙。三九已至,卻和暖如春态鳖,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背浆竭。 一陣腳步聲響...
    開封第一講書人閱讀 33,869評(píng)論 1 274
  • 我被黑心中介騙來泰國(guó)打工邦泄, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留,地道東北人顺囊。 一個(gè)月前我還...
    沈念sama閱讀 49,378評(píng)論 3 379
  • 正文 我出身青樓,卻偏偏與公主長(zhǎng)得像诚亚,于是被迫代替她去往敵國(guó)和親午乓。 傳聞我的和親對(duì)象是個(gè)殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,937評(píng)論 2 361

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