Thinking:

  • Method1:慢
    • 关于入口要找到gas大于cost。
class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int len = gas.length;
        for(int i = 0; i < len; i++){
            if(cost[i] <= gas[i]){
                if(valid(gas, cost, i))
                    return i;
            }
        }
        return -1;
    }
    private static boolean valid(int[] gas, int[] cost, int start){
        int remain = 0;
        int temp = start;
        for(; start < gas.length; start++){
            remain += (gas[start] - cost[start]);
            if(remain < 0) return false;
        }
        for(start = 0; start < temp; start++){
            remain += (gas[start] - cost[start]);
            if(remain < 0) return false;
        }
        return true;
    }
}
  • Method2:
class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int len = gas.length;
        int sum = 0;
        int total = 0;
        int index = 0;
        for(int i = 0; i < len; i++){
            sum += gas[i] - cost[i];
            if(sum < 0){
                total += sum;
                sum = 0;
                index = i+1;
            }
        }
        total += sum;
        return (total >= 0) ? index : -1;
    }
}

二刷

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int len = gas.length;
        int sum = 0;
        int index = 0;	// 可能成功的index的值。
        int total = 0;	// 用于记录所有gas和cost的差值。
        for(int i = 0; i < len; i++){
            sum += gas[i] - cost[i];	// 在某一个结点，获得当前的正负均值。
            if(sum < 0){
							//如果当前的正负均值小于0，则说明当前的结点不可能成为开始的结点。
							// 将当前的正负计数值清零。并移动到下一个结点。
                total += sum;
                sum = 0;
                index = i + 1;
            }
        }
        total += sum;
        return total < 0 ? -1: index;	// 如果差值为负数，则说明不可能成功，则返回-1
    }
}