首页 > 代码库 > leetcode第一刷_Gas Station

leetcode第一刷_Gas Station

刚看到这个题时,觉得跟之前看到过的一个小猫钓鱼的题目很像,虽然具体的记不太清楚了,不过那个题用的应该是贪心,在惯性思维的驱使下,这个题的题意一开始又理解错了。。此题要求的是“走一圈回到原点”,即从位置i开始,最后还要回到i,而不是设计一个路线,踩完所有的点,使剩余的油量最大。一个更明显的条件是,题目只给出了从i到i+1的,没告诉你从i+1到i是多少,这种路线对称消耗就一样的假设完全我自己想象的。

因此,这个题的路线只有一条,从某个起始点开始,往前走,走一圈看能不能回来,能就是true,不能就是false,就这么简单。暴力法我就不说了,我们看看怎样O(N)时间解决战斗。先想一下什么样的点可以作为起始点?答案很明显,这个点的油量一定要大于等于走一步的消耗。第二个问题,怎样就知道能走完一圈了呢?走一圈收集的油量一定要比消耗的多或者相等。第三个问题,什么样的起始点肯定不能完成任务,或者说什么时候应该更新这个起始点呢?当走到某一步的时候发现走不下去了,所谓的走不下去了,就是从起始点开始的累积油量小于下一步的情况。最后一个问题,知道了上一个起始点不行,怎么选取下一个起始点呢?这里有个关键的观察,当从i开始,到j不行了,那么这条路径上的点都不能作为起始点,因为你想,从i开始,i为总剩余贡献的一定是正值或者0,从他开始都不行,那么后面的少了i的贡献,走到j的时候肯定更不行了。因此,下一个起始点应该从j+1位置开始尝试。

ac代码如下,想明白了写起来很简单:

class Solution {
public:
    int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
        int msize = gas.size();
        if(msize == 0)  return -1;
        vector<int> leftGas(msize);
        for(int i=0;i<msize;i++){
            leftGas[i] = gas[i] - cost[i];
        }
        int mgas = 0, start = 0;
        for(int i=0;i<msize;i++){
            mgas += leftGas[i];
            if(leftGas[i]<0&&mgas<0){
                start = i+1;
            }
        }
        if(mgas>=0)
            return start;
        return -1;
    }
};