Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594

[LeetCode]Gas Station-2014.01.09

Posted on 2014-01-11 03:01 Uriel 阅读(133) 评论(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 };

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理