leetcode 134. 加油站

题解

找到 gas[i] >= cost[i] 作为起点, 判断是否可以行驶一周

示例代码(go)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
func canCompleteCircuit(gas []int, cost []int) int {
n := len(gas)
for i := 0; i < n; i++ {
if gas[i] >= cost[i] && canComplete(gas, cost, i) {
return i
}
}
return -1
}

func canComplete(gas []int, cost []int, i int) bool {
n := len(gas)
pre := gas[i] - cost[i]
for j := 1; j <= n; j++ {
k := (i+j) % n
if k == i {
return true
}
pre += gas[k] - cost[k]
if pre < 0 {
break
}
}
return false
}