Re: [闲聊] 每日LeetCode

楼主: SecondRun (雨夜琴声)   2023-01-07 10:46:20
有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
作者: Jaka (Jaka)   2023-01-07 10:47:00
大师
作者: sustainer123 (caster)   2023-01-07 10:53:00
大师
作者: pandix (面包屌)   2023-01-07 11:55:00
大师

Links booklink

Contact Us: admin [ a t ] ucptt.com