leetcode Gas Station

深度遍历：

如果有5个站， 就有5种方案：

1-2-3-4-5

2-3-4-5-1

3-4-5-1-2

。。。

判断每一种是否可能：

class Solution {
public:
    bool isS(int g, vector<int>  gas, vector<int> cost, int c)
    {
        int n=gas.size();
        int s=(c+1)%n;
        for(int i=0;i<n-1;i++)
        {
            g=g+gas[s]-cost[s];
            if(g<0)
                return false;
            s=(s+1)%n;
            
        }
        return true;
    }
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        
        
        for(int i=0;i<gas.size();i++)
        {
            int g=gas[i]-cost[i];
            if(g>=0)
              if (isS(g,gas, cost, i))
                  return i;
                
            else
                continue;
        }
        return -1;
    }
};

　　使用贪心法的最优子结构：

如果0到i时的累积油量为负值，则0-i开始的值都不行, 从 i开始判断。 并累积总的 diff， 看是否有解

class Solution(object):
    def canCompleteCircuit(self, gas, cost):
        """
        :type gas: List[int]
        :type cost: List[int]
        :rtype: int
        """
        
        x=0
        n=len(gas)
        cur_g=0
        total=0
        for i in range(n):
            diff=gas[i]-cost[i]
            cur_g=cur_g+diff
            total=total+diff
                
            if cur_g<0:
                cur_g=0
                x=i+1
                
        return x if total>=0 else -1