首页 > 代码库 > LeetCode-Gas Station-加油站-最大子串算法应用
LeetCode-Gas Station-加油站-最大子串算法应用
https://oj.leetcode.com/problems/gas-station/
计算每个加油站的加油差diff[]。得到一个数组。从贪心的角度来说，如果我们找到一个最大子串，那么从他的起点l开始走，能够连续一直走并且累积最大量的汽油。
一个猜想是：如果这些汽油不足以走完全程，那么无论从哪里都无法走完全程。
可以反证一下：如果从p开始能够走完全程。那么从p走到l的这部分子串和必然大于0，这部分子串加上l开始最大子串能使子串更大。那么与从l开始最大子串矛盾。所以没有这样的p。
因此，用最大子串算法找出最大子串的起点l，然后执行一次模拟，就能确定能否走完全程了。
class Solution {public: int n,m; int canCompleteCircuit(vector<int> &gas, vector<int> &cost) { n=gas.size(); vector<int> d=gas; for(int i=0;i<n;i++) d[i]-=cost[i]; int l=-1; int maxs=-1; int cs=-1; int cl=-1; for(int i=0;i<2*n;i++) { int ci=i%n; if(cs<0) {cs=d[ci];cl=ci;} else cs+=d[ci]; if(cs>maxs) { maxs=cs; l=cl; } } int cur=0; for (int i=0;i<n;i++) { int cp=(l+i)%n; cur+=d[cp]; if(cur<0) return -1; } return l; }};
LeetCode-Gas Station-加油站-最大子串算法应用
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。