Re: [閒聊] 每日LeetCode

作者: Rushia (みけねこ的鼻屎)   2023-01-07 15:27:42
※ 引述《fxfxxxfxx (愛麗絲)》之銘言:
: 134. Gas Station
給予兩個陣列,陣列gas[i]表示第i個位置的油量,陣列cost[i]表示前往i+1位置所需
的油量,若我們可以從某一個位置i走訪所有的加油站返回i的值,若無法走訪則返回-1。
(題目保證如果可以走完全程則必定只會有一個解)
Example:
Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
Output: 3
Explanation:
Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 +
4 = 4
Travel to station 4. Your tank = 4 - 1 + 5 = 8
Travel to station 0. Your tank = 8 - 2 + 1 = 7
Travel to station 1. Your tank = 7 - 3 + 2 = 6
Travel to station 2. Your tank = 6 - 4 + 3 = 5
Travel to station 3. The cost is 5. Your gas is just enough to travel back to
station 3.
Therefore, return 3 as the starting index.
思路:
1.如果一個車要從某個起點開始走完全程,他必須滿足:總油量 >= 總成本。
2.所以我們只需要把所有油量和成本相加判斷他是否大於等於0即可知道是否可以走完。
3.至於要如何知道要從哪一點開始走呢?
如果從當前點開始走走到某一個點導致 油量 < 下個點的成本時,代表從我們一開始
的點開始走的話必定走不到這個點,所以我們把起點改為當前點的下一個點:

Links booklink

Contact Us: admin [ a t ] ucptt.com