題目鏈接:https://leetcode.com/problems/gas-station/
題目:
There are N gas stations along a circular route, where the amount of gas at station i is gas[i]
.
You have a car with an unlimited gas tank and it costs cost[i]
of gas to travel from station i to
its next station (i+1). You begin the journey with an empty tank at one of the gas stations.
Return the starting gas station's index if you can travel around the circuit once, otherwise return ⑴.
Note:
The solution is guaranteed to be unique.
思路:
看了tag發現是貪心,想起老師上課說貪心實現起來是最簡單的,最難的是證明貪心策略的正確性。這里主要為了AC,多嘗試幾次可能的策略懶得證明了(寶寶TM不會證明?。。。:茏匀幌氲降牟呗杂校?、從gas最多的station開始 2、從cost最少的station開始 3、從剩余(gas-cost)最少的開始。
嘗試了幾次發現第2種是對的,但要注意如果有多個站點cost相同,要判斷這些站點是不是能完成環圈旅行。
算法: