首页 > 其他 > 详细

LeetCode Gas Station

时间:2014-05-15 01:58:22      阅读:434      评论:0      收藏:0      [点我收藏+]
bubuko.com,布布扣
class Solution {
public:
    int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
        int len = gas.size();
        if (len < 1 || len != cost.size()) return -1;
        vector<int> diff(len, 0);
        for (int i=0; i<len; i++) {
            diff[i] = gas[i] - cost[i];
        }
        int p = len - 1;
        int q = 0;
        
        int sum = diff.back();
        int walk= len - 1;
        
        while (walk > 0) {
            while (walk > 0 && sum + diff[q] >= 0) {
                sum += diff[q++];
                walk--;
            }
            while (walk > 0 && sum + diff[q] < 0) {
                sum += diff[--p];
                walk--;
            }
        }
        if (sum < 0) return -1;
        return p == q ? p : -1;
    }
};
bubuko.com,布布扣

这题直接穷举的话就是O(N^2),估计会超时吧,于是想其他办法几度想去搜答案了,还是蒙了一下,思路:

先求出每个加油站和下一段路所需燃油的差存到diff中,这样问题就转换为,从diff的哪个元素开始向右绕一圈,每一步的diff前缀和始终为非负值,

因为要绕一圈必然包含所有的元素,那么先从diff的最后一个元素开始,如果是一个负值(gas[i]-cost[i] < 0)说明从该加油站直接开始是不行的,前面必定有加油站加油后多了一些出来才能补上这个负值,那我们就一直向前遍历diff元素,直到他们的和能填补这个负值为止,这时候的索引就是目前暂定的开始索引(开始为什么选择从最后一个元素进行,因为绕一圈起点最极端的情况就是从最后一个元素开始,然后一个个向前排除),有了前面的这些diff遍历后,一般他们的和会是个正数也就是说有油多出来,这时候我们尝试向diff后面的元素遍历(因为一开始在最后一个节点,这里的向后遍历,其实是从diff下标0开始向后遍历了),直到油不够。再向前遍历企图找到使得累加和为正的diff元素索引,这样的一个过程反复进行最后就可以得到结果了。

 

当然这题里假设如果有解的话只有一个,否则会有问题吧

 

另外看了下zheli哥的题解,有证明感觉比瞎蒙好

http://www.cnblogs.com/zhuli19901106/p/3568203.html

LeetCode Gas Station,布布扣,bubuko.com

LeetCode Gas Station

原文:http://www.cnblogs.com/lailailai/p/3728690.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!