在一條環路上有?n?個加油站，其中第?i?個加油站有汽油?gas[i]?升。
你有一輛油箱容量無限的的汽車，從第?i?個加油站開往第?i+1?個加油站需要消耗汽油?cost[i]?升。你從其中的一個加油站出發，開始時油箱為空。
給定兩個整數數組?gas?和?cost?，如果你可以按順序繞環路行駛一周，則返回出發時加油站的編號，否則返回?-1?。如果存在解，則?保證?它是?唯一?的。
我覺得我的思路很笨 就是找到第一個可以往下走的 如果可以順利的話 那么就OK 如果不順利 那么就繼續往下找 因為解是唯一的 所以只要找到直接return就行 雖然不確定是不是會超過時間限制 但是還是先試一下
我的大體思路就是：我往下找 找到第一個滿足的 就開始計算步數和余量 只要往下走就往下走 步數要走到n才行? 計算此時的索引就使用取模的方法 如果到了什么時候rem<0 那么就break 不然就step+=1 如果等于n了 那么就return i （反正要么就是while結束了 要么就是break了） 如果并沒有return i 那么就證明是這個不行 那要繼續往下選擇
那么重點來了 我要使用i+1嗎？顯然不是 因為我走了step步之后無法走下去 那么選擇i和i+step中間的是可以保證走下去的嗎？
跳過失敗路徑中的所有站點是貪心算法的關鍵優化點之一，它能將時間復雜度從 O(n2) 降到 O(n)。這不是因為“某一步負數太多”，而是因為整個路徑的凈收益是負的，意味著從任何子起點都無法完成一圈。所以繼續進行的就是i+step+1
但是我領會到其中的奧妙了 你想啊 我從中間的出發 根本到不了下一步 為什么？ 我既然是走到這步才停 證明是因為前面的是有剩余的 到我這步又虧損了 虧損大了 才到不了 那你可能會覺得 誒 那我從虧損超級大的那一步往下走到不了嗎？你想啊 你既然是從虧損超級大的那一步往下走 既然可以往下走 就證明有剩余 有剩余都走不到這個step步 那中間的哪一個都不行（因為要想到達中間的某一步 任何一步 都是要有結余的 有結余還不行 那么我從頭開始更不行）我少了前面的補貼 還要面對后面的虧損 達咩達咩
好的來看代碼
class Solution(object):def canCompleteCircuit(self, gas, cost):i=0index=-1n=len(gas)while i <n:#如果當前的汽油不夠消耗到下一步的 就繼續往下找if gas[i]<cost[i]:i+=1continue#如果找到了這一個gas = [1,2,3,4,5], cost = [3,4,5,1,2]#現在是索引為3的地方 那么要是繼續往下走 就要滿足gas-cost+gas>=cost#計算剩余量和步數rem=0step=0while step<n:j = (i + step) % nrem += gas[j] - cost[j]if rem < 0:breakstep += 1if step==n:return i#證明這個i是不行的 那么我是需要走i+1的這一步的嗎？#不是的 因為我從i開始可以的 證明我i這步是有盈余的 既然走到這步不行了#那么就證明無論我從中間的哪一步開始 走到這步肯定都不行了 所以要跨過step這個步驟開始else:i=step+i+1return -1 solution=Solution() result=solution.canCompleteCircuit([2,3,4], [3,4,3]) print(result)
但是這個運行速度只超過百分之三十多 所以我們來分析一下排名第一的代碼
首先就是計算總和 如果消耗總和大于油量總和 那直接不行?
然后就是直接計算盈余 一旦盈余小于0 改變開始的索引？ 感覺這個for循環寫的還是挺深奧的 如果小于0的話 證明這個起點不行 那么是嘗試下一個這個我明白 但是為什么直接每個點開始計算結余呢？從第一個點開始 如果這個剩余小于0 那這個點不行 使用i+1這個點 如果是大于0的 那么這個點就不變 i繼續往下走 在這個過程中 只要這個剩余小于0 就證明這個包括這個中間的點都是不行的 （看我上面的解釋） 喵喵喵啊
class Solution(object):def canCompleteCircuit(self, gas, cost):""":type gas: List[int]:type cost: List[int]:rtype: int"""if sum(gas) < sum(cost):return -1cursum = 0start_idx = 0for i in range(len(gas)):cursum += gas[i] - cost[i]if cursum < 0:start_idx = i + 1cursum = 0return start_idx
如果喜歡這個帖子 歡迎點贊收藏！
