134. Gas Station

不会做。

1. 朴素的想法，就是针对每个位置判断一下，然后返回合法的位置，复杂度O（n^2）,显然会超时。

把这道题转化一下吧，求哪些加油站不能走完一圈回到自己，要求O(N)的复杂度。

如果sgas < scost，那么显然所有的站点都无法走完一圈。

2. 考虑怎么进行化简，寻找有没有什么可以利用的性质，考虑可不可以进行递推，对每个位置求出gas - cost，然后很明显观察到如果一个位置为负数，那么这个位置显然不能走完一圈，那么接下来

考虑怎么进行简化，找到负数，知道我们把它变成整数，否则，前面的站点都是无法走完一圈的。考虑接下来怎么进行转化，固定头指针的话，无法对其他节点进行更新，我想不出来，O(n)的方法，解决

这个问题，比如5，-3,5,5，-3.你把一个负数转变为一个正数以后，你怎么判断下一个负数在哪里啊，难道标记一下和，记录一下当前的和么。 

先贴一下leetcode原题的解法，从discuss看的：

1 class Solution { 2 public: 3     int canCompleteCircuit(vector
      
       & gas, vector
       
        & cost) { 4         int n = gas.size(); 5         int start = n - 1, end = 0; 6         int s = gas[start] - cost[start]; 7         while(end < start) { 8             if(s >= 0) { 9                 s += gas[end] - cost[end];10                 end++;11             } else {12                 start--;13                 s += gas[start] - cost[start];14             }15         }16         return s >= 0 ? start : -1;17         18     }19 };
       
      

转化的问题不会做。

还是不会，-w-。