本文主要是介绍代码随想录算法训练营第三十四天 | 1005.K次取反后最大化的数组和,134. 加油站 , 135. 分发糖果,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
贪心,每次选择最小的数来取反
用了一个优先级队列来做处理,维护一个顺序的数组
class Solution {
public:typedef struct comp{bool operator()(const int & a,const int & b){return a > b;}}comp;int largestSumAfterKNegations(vector<int>& nums, int k) {int res = 0;priority_queue<int,vector<int>,comp> pq;for(auto & num : nums){pq.push(num);}for(int i = 0;i< k;i++){int minNum = pq.top();pq.pop();pq.push(minNum * -1);}for(int i = 0;i< nums.size();i++){int num = pq.top();pq.pop();res += num;}return res;}
};
这道题是一个贪心问题,从0下标起点出发,一直加油,耗油,前进,一直到某个位置耗油大于已有的油量时再也无法前进,那么也就是说,从起点到当前终止的位置,都是不能作为起点使用的:
很好理解吧,在每个节点其实都有 加油 - 耗油 = 净加油量,某个节点无法寸进以后,也就是说明,在起点出发的这个区间内,净油量无法满足消耗,需要在其它区间出发,用其他位置的净油量来把这里的缺口补上,由于我们是从0开始的,那么这一整段都不要了,下一个区间紧贴当前终止位置,继续查看
如果发现整个区间都没有起点(净油量无法满足消耗),就返回-1
class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int maxSize = gas.size();int curSum = 0;int totalSum = 0;int start = 0;for(int i = 0;i< maxSize;i++){int diff = gas[i] - cost[i];curSum += diff;totalSum += diff;if(curSum < 0){start = i+1;curSum = 0;}}if(totalSum < 0){return -1;}return start;}
};
这道题需要维护数组元素的左右关系,需要注意,一般的做法是把左右关系分开来维护,不要同时维护,要不会很乱
本题是从前往后遍历,先维护右孩子大于左孩子的+1
那么,这个遍历次序下可以确保前面填定的值不会受到后面的影响
然后是在右孩子大于左孩子的+1的基础上,从后往前遍历,维护左孩子大于右孩子的+1
class Solution {
public:int candy(vector<int>& ratings) {int res = 0;vector<int> nums(ratings.size(),1);for(int i = 1;i< ratings.size();i++){if(ratings[i-1] < ratings[i]){nums[i] = nums[i-1]+1;}}for(int i = ratings.size()-2;i >=0;i--){if(ratings[i] > ratings[i+1]){nums[i] = max(nums[i+1]+1,nums[i]);}}for(auto & i : nums){res += i;}return res;}
};
这篇关于代码随想录算法训练营第三十四天 | 1005.K次取反后最大化的数组和,134. 加油站 , 135. 分发糖果的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!