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