首页 > 代码库 > leetcode-Gas Station-134
leetcode-Gas Station-134
输入两个数组,gas[i]表示在i位置能加的油,cost[i]表示在i位置到i+1位置消耗的油,这n个位置围成一个圈,求是否存在从某一点出发能走完全程
第一想法是贪心,先处理处gas[i]/cost[i],然后从这个比值最大的点开始走,但找到反例:(5,4),(6,4),(5,5),(4,7),按刚才思路应该从第二个点开始走,但是走不到第四个点,所以贪心的出发点是错误的,不应该以每个点的性价比考虑,而应该按照整体来考虑:出发的前段时间尽可能选择加油比消耗大的存储尽可能多的油,用于后面消耗,也就是先尽可能的存储油
所以先处理diff[i]=gas[i]-cost[i],记录每个点能存储的油,如果sum(diff[i])<0 说明整体的存储小于0,肯定不能走完,return -1
否则找到最大和连续子序列的开头就是所求
1 class Solution { 2 public: 3 int canCompleteCircuit(vector<int>& gas, vector<int>& cost) { 4 if(gas.size()==0) return 0; 5 vector<int> diff; 6 int sum=0; 7 for(int i=0;i<gas.size();i++){ 8 diff.push_back(gas[i]-cost[i]); 9 sum+=diff.back();10 }11 if(sum<0) return -1;12 int cur=diff[0];13 int indx=0;14 for(int i=1;i<diff.size();i++){15 if(cur<0){16 cur=0;17 indx=i;18 }19 cur+=diff[i];20 }21 //if(cur<0) return -1;22 return indx;23 }24 };
leetcode-Gas Station-134
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。