Posted on 2014-01-11 03:01
Uriel 閱讀(159)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
LeetCode
O(n^2)的會(huì)超時(shí)，然后優(yōu)化方法想不出，參考了：
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 };