station

发表于 2020-02-01| 更新于 2020-10-27

阅读量:

134.加油站
解法一：On2

c++

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        for(int i=0;i<gas.size();i++)
        {
         int sum=0;
         int flag=0;
            if(cost[i]>gas[i])continue;
            for(int j=i;;j++)
            {
                if(j==gas.size())j=0;
                if(j==i)flag++;			//起始结束，i`j两次重合
                if(flag==2)return i;   //第二次回到原点 
                sum+=gas[j]-cost[j];
                if(sum<0)break;
            }
        }
        return -1;
        
            
    }
};