leetcode/prob134.java at master · dilemmawalker/leetcode · GitHub

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
35
36
37
38
class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n=gas.length;

        for(int i=0;i<n;i++){
            boolean flag=false;
            if(gas[i]>=cost[i]){
                flag=check(i,gas,cost);
            }
            if(flag)
                return i;
        }
        return -1;
    }
    public boolean check(int idx,int[]gas,int []cost){
        int n=gas.length;
        int c=0;
        // System.out.println(idx);
        // c+=gas[idx];
        for(int i=idx;i<n;i++){
            if(i!=idx && c<=0)
                return false;
            c+=gas[i];
            c-=cost[i];

        }
        for(int i=0;i<idx;i++){
            if(c<=0)
                return false;
            c+=gas[i];
            c-=cost[i];

        }
        if(c<0)
            return false;
        return true;
    }
}