Posted on 2014-01-11 03:01
Uriel 阅读(134)
评论(0) 编辑 收藏 引用 所属分类:
LeetCode
O(n^2)的会超时，然后优化方法想不出，参考了：
http://blog.csdn.net/lbyxiafei/article/details/12183461 1 class Solution {
2 public:
3 int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
4 int sum = 0, cnt = 0, st = 0;
5 for(int i = 0; i < gas.size(); ++i) {
6 sum += gas[i] - cost[i];
7 cnt += gas[i] - cost[i];
8 if(sum < 0) {
9 sum = 0;
10 st = (i + 1) % gas.size();
11 }
12 }
13 if(cnt < 0) return -1;
14 return st;
15 }
16 };