FilesExpand file tree

 master

/

LeetCode134.java

Copy path

BlameMore file actions

BlameMore file actions

Latest commit

 

History

History

History

34 lines (33 loc) · 1.22 KB

 master

/

LeetCode134.java

Top

File metadata and controls

• Code
• Blame

34 lines (33 loc) · 1.22 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

26

27

28

29

30

31

32

33

34

package problems;

/**

* 如果 x 到不了 y + 1 (但能到 y)，那么从 x 到 y 的任一点出发都不可能到达 y + 1.

* 也可以假设：从 x 加油站出发经过 z 加油站最远能到达 y 加油站，那么从 z 加油站直接出发，不可能到达 y 下一个加油站。

* 因为从 x 出发到 z 加油站时还有存储的油，这都不能到达 y 的下一站，而直接从 z 出发刚开始是没有存储的油的，所以更不可能到达 y 的下一站

*/

public class LeetCode134 {

public int canCompleteCircuit(int[] gas, int[] cost) {

int n = gas.length;

int i = 0;

while (i < n) {

// 总汽油量，总耗油量

int sumOfGas = 0, sumOfCost = 0;

// cnt 为经过加油站的数量

int cnt = 0;

while (cnt < n) {

int j = (i + cnt) % n;

sumOfGas += gas[j];

sumOfCost += cost[j];

if(sumOfCost > sumOfGas) {

break;

}

cnt++;

}

if(cnt == n) {

return i;

} else {

i = i + cnt + 1;

}

}

return -1;

}

}