頻道欄目
首頁 > 資訊 > 其他 > 正文

LeetCode Gas Station

16-04-28        來源:[db:作者]  
收藏   我要投稿

 

原題

在一條環形的路上有N個加油站,每個加油站里有gas[i]的汽油,從第i個加油站到第i+1個加油站需要花費cost[i]的汽油。假設汽車的油箱可以裝無數的汽油,判斷一輛沒有油的汽車是否可以從其中的某一個加油站出發并行駛一圈后返回該加油站。如果可以的話,返回起始加油站的下標,否則返回-1。

注意點:

如果有答案的話,答案是唯一的 不用考慮逆向行駛

例子:

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

輸出: 4

解題思路

選擇從一個加油站出發,如果車要能夠到達下一個加油站,就需要這個加油站的gas>cost。不妨設c[i] = gas[i] - cost[i],c[i]表示的是從某一加油站得到的汽油減去到達下一個加油站需要耗費的汽油后剩余的汽油數目,對c求和得到的是從出發開始到當前加油站剩余的汽油數目,如果這個這個和為負,說明當前這種行駛方案無法到達當前的加油站。也就是說要使車能夠不斷的向前行進,就要保證途中對c的求和始終大于0。

如果cost的和大于gas的和,顯然汽車是無法成功走完一圈的,下面證明如果cost的和小于等于gas的和,必然存在一種方案能夠讓汽車走完一圈。

現在有c[0]+c[1]+...+c[n-2]+c[n-1]>=0,我們對c的前i項求和,假設當i=j時,這個和是所有和中最小的,也就是說:

c[0]+c[1]+...+c[j-1]<=c[0]+c[1]+...c[j]
c[0]+c[1]+...+c[j-1]<=c[0]+c[1]+...c[j]+c[j+1]
...
c[0]+c[1]+...+c[j-1]<=c[0]+c[1]+...c[j]+c[j+1]+...+c[n-1]

也就是說:

c[j]>=0
c[j]+c[j+1]>=0
...
c[j]+c[j+1]+...+c[n-1]>=0

同時,因為前j項的求和是最小的,還能得到下面的不等式:

c[0]+c[1]+...+c[j-1]<=c[0]+c[1]+...+c[j-2]
c[0]+c[1]+...+c[j-1]<=c[0]+c[1]+...+c[j-3]
...
c[0]+c[1]+...+c[j-1]<=c[0]

轉換可以得到:

c[j-1]<=0
c[j-2]+c[j-1]<=0
...
c[1]+c[1]+...+c[j-1]<=0

再組合最初始的條件c[0]+c[1]+...+c[n-2]+c[n-1]>=0,我們可以得到:

c[j]+c[j+1]+...+c[n-1]+c[0]+c[1]+...+c[j-2]>=0
c[j]+c[j+1]+...+c[n-1]+c[0]+c[1]+...+c[j-3]>=0
c[j]+c[j+1]+...+c[n-1]+c[0]>=0

至此我們可以看出,如果從j出發的話,對c的求和始終都滿足大于等于零的要求,也就是說j是我們選擇出發的加油站。

AC源碼

class Solution(object):
    def canCompleteCircuit(self, gas, cost):
        """
        :type gas: List[int]
        :type cost: List[int]
        :rtype: int
        """
        if sum(gas) < sum(cost):
            return -1
        min_sum, min_index, total = 0, 0, 0
        for i in range(len(gas)):
            total += gas[i] - cost[i]
            if min_sum > total:
                min_sum, min_index = total, i + 1
        return -1 if total < 0 else min_index


if __name__ == "__main__":
    assert Solution().canCompleteCircuit([5], [4]) == 0
    assert Solution().canCompleteCircuit([5, 1, 2, 3, 4], [4, 4, 1, 5, 1]) == 4

歡迎查看我的Github (https://github.com/gavinfish/LeetCode-Python) 來獲得相關源碼。

相關TAG標簽
上一篇:臺積電:絕大多數7nm客戶都會轉向6nm_IT新聞_博客園
下一篇:最后一頁
相關文章
圖文推薦

關于我們 | 聯系我們 | 廣告服務 | 投資合作 | 版權申明 | 在線幫助 | 網站地圖 | 作品發布 | Vip技術培訓 | 舉報中心

版權所有: 紅黑聯盟--致力于做實用的IT技術學習網站

美女MM131爽爽爽毛片