首页 > 代码库 > 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; } };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。