【贪心算法题记录】134. 加油站
题目描述
题目🔗
初始答案
思路都在注释里，不够超出时间限制了。
class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {/* 首先出发站startIndex获得的汽油要大于前往下一站要消耗的汽油* 也就是：gas[startIndex] >= cost[startIndex]* 将计算公式写出来就是：例如从startIndex = 3出发* ((((0 + gas[3] - cost[3]) + gas[4] - cost[4]) + gas[0] - cost[0]) + gas[1] - cost [1]) + gas[2] - cost[2] = 0可以返回* 但是还有条件：每一次括号中的计算结果也要大于0*/ vector<int> v1(gas.size(), 0);for(int i = 0; i < gas.size(); i++){v1[i] = gas[i] - cost[i];}/* 上面的计算公式就变成了((((0 + v1[3]) + v1[4]) + v1[0]) + v1[1]) + v1[2] = 0* 那么下面我们根据条件“每一次括号中的计算结果也要大于0”来进行判断*/// 首先判断整体和如果小于0，那么肯定不能环绕一圈if(accumulate(v1.begin(), v1.end(), 0) < 0) return -1;int result = -1;for(int i = 0; i < gas.size(); i++){// 找到第一个汽油大于0的加油站if(v1[i] < 0) continue;int num = gas.size();int k = i;int sum = v1[k];while(num--){if(k == gas.size() - 1){sum += v1[0];k = 0;}else sum += v1[++k];if(sum < 0) break;}if(sum >= 0) result = i;}return result;}
};
贪心版分析
很久没有做贪心算法题了，已经完全不记得咋做了orz…
首先这题的限制在于：每个站点的净剩余油量都要大于等于0，即rest[i] = gas[i] - cost[i] >= 0。
那么i从索引0开始累加rest[i]，其和记为curSum，一旦curSum小于0，则说明从0到i这个区间内，无论选择哪一个站点作为起始站点，走到i都会断油，那么我们这时就可以选择i+1作为起始开始重新计算。
将上述分析总结就是：
局部最优：curSum一旦小于0，起始位置至少要是i+1才能满足条件。
全局最优：可以找到能跑一圈的起始位置。
class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int curSum = 0;int totalSum = 0;int start = 0;for(int i = 0; i < gas.size(); i++){curSum += gas[i] - cost[i];totalSum += gas[i] - cost[i];if(curSum < 0){start = i + 1;curSum = 0;}}if(totalSum < 0) return -1;return start;}
};