Re: [閒聊] 每日LeetCode已回收

看板Marginalman作者SecondRun (雨とカプチーノ)時間2年前 (2023/01/07 10:46)推噓2(2推 0噓 2→)

留言4則, 4人參與討論串183/719 (看更多)

有n個加油站在圓環形道路上給定int陣列gas和cost gas[i]代表第i個加油站可獲得的油量 cost[i]代表從第i個加油站往下一個加油站需要消耗的油量假設你的油箱為無限大，從某個加油站出發找出是否可以繞一圈，如果不能則回傳-1，可以則回傳起點的index 注意:假如可以，那麼起點將會是唯一的 ex. gas = [1,2,3,4,5], cost = [3,4,5,1,2] 從index = 3出發，起始油量為0+4 index = 4,油量為4+5-1=8 0 8+1-2=7 1 7+2-3=6 2 6+3-4=5 答案為index=3 思考: 可以遍歷代表 1.總油量-總消耗會是正的 2.從起點到終點的途中油箱剩餘都是正的那麼從a點出發，假如油不足以從b-1點前往b點代表a~b的路段總和為負，可以把這段放到後面算從b當作起點繼續走，假如又不足以從c-1走到c點代表b~c也是負的路段，可以把這段放到後面算再次從c點開始，假如可以走到a點那麼只要檢查總油量是不是比總消耗還多就好如果總油量>總消耗我們的路程可以寫成c -> a -> b -> c 正負負把負的都丟到後面去了，而且已知三段總和為正，那麼從c一定可以繞完一圈 C# code https://i.imgur.com/ks3SWR9.png