134_canCompleteCircuit.txt

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        //暴力法，遍历两次
        int size = gas.size();
        if(size==1){
            if(gas[0]<cost[0])
                return -1;
            return 0;
        }
        for(int i = 0;i<size;i++){
            bool flag = false;//辨识有无满足条件的答案
            int cur = gas[i];
            int j = i;
            int count = 0;
            while(count!=size){//还未循环一周
                if(cur >= cost[j]&&j!=size-1)
                    cur = gas[j+1]+cur-cost[j];
                //准备往回走了
                else if(j==size-1)
                    cur = gas[0]+cur-cost[j];
                else{
                    flag = true;
                    break;   
                }    
                j = (j == size-1)?0:j+1;
                count++;
            }
            if(flag == false)
                return i;
        }
        return -1;
    }
}

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        //一次遍历
        int N = gas.size();
        int i = 0;
        while(i<N){
            int sumofgas = 0,sumofcost = 0;
            int count = 0;
            //判断能否走完一圈
            while(count<N){
                int j = (i+count)%N;//j是下一站的位置，最后一站的下一站的第一站
                sumofgas += gas[j];
                sumofcost += cost[j];
                if(sumofgas < sumofcost)//不能走完直接break；
                    break;
                count++;
            }
            if(count==N)
                return i;
            else
                i = i+count+1;//不能从i到i+count则直接从i+count+1继续判断
        }
        return -1;
    }
};

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        //最巧妙的解法，参考题解神奇的z：使用图的思想分析该问题
        int N = gas.size();
        int spare = 0;//实时的总剩余油量
        int minindex = 0;
        int minspare = INT_MAX;
        for(int i = 0;i<N;i++){
            spare += gas[i]-cost[i];
            if(spare < minspare){
                minspare = spare;
                minindex = i;
            }
        }
        return spare<0?-1:(minindex+1)%N;
    }
};