建设旅游网站的费用预算,微分销系统哪家比较好,WordPress主题开源,php 网站进入后台目录 一、1005. K 次取反后最大化的数组和
二、134. 加油站
三、135. 分发糖果 一、1005. K 次取反后最大化的数组和
题目链接#xff1a;力扣
文章讲解#xff1a;代码随想录
视频讲解#xff1a;
题目#xff1a;
给你一个整数数组 nums 和一个整数 k #xff0c…目录 一、1005. K 次取反后最大化的数组和
二、134. 加油站
三、135. 分发糖果 一、1005. K 次取反后最大化的数组和
题目链接力扣
文章讲解代码随想录
视频讲解
题目
给你一个整数数组 nums 和一个整数 k 按以下方法修改该数组
选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。 重复这个过程恰好 k 次。可以多次选择同一个下标 i 。
以这种方式修改数组后返回数组 可能的最大和 。
代码
class Solution {
public:int largestSumAfterKNegations(vectorint nums, int k) {sort(nums.begin(), nums.end());int position 0;int sum 0;for(int i 0; i nums.size(); i){if(nums[i] 0 k 0){k--;nums[i] -nums[i];position i;}sum nums[i];}if (k 0){if(k%2 1) return sum - 2*(nums[position] nums[(position1)%nums.size()] ? nums[(position1)%nums.size()] : nums[position]);else return sum; }return sum;}
};
时间复杂度: O(nc) 空间复杂度:O(c)
⏲9:19
总结取负局部最优最大的负数先取负。转变k次正负局部最优最小的数。
二、134. 加油站
题目链接134. 加油站 - 力扣LeetCode
文章讲解代码随想录 (programmercarl.com)
视频讲解
题目在一条环路上有 n 个加油站其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车从第 i 个加油站开往第 i1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发开始时油箱为空。
给定两个整数数组 gas 和 cost 如果你可以绕环路行驶一周则返回出发时加油站的编号否则返回 -1 。如果存在解则 保证 它是 唯一 的。代码
class Solution {
public:int canCompleteCircuit(vectorint gas, vectorint cost) {int sum 0;int total 0;int position 0;int flag 0;for (int i 0; i gas.size(); i){sum gas[i] - cost[i];total gas[i] - cost[i];if(sum 0){sum 0;position i1;}} if(total0) return -1;return position;}
};
时间复杂度: O(n) 空间复杂度O(1)
⏲25:07
总结局部最优当sum0则合理位置至少i1i1之前都不行。本质如果总数为正则应该正大于负局部来看若前面的和为负数则后面的和应为正数。
三、135. 分发糖果
题目链接135. 分发糖果 - 力扣LeetCode
文章讲解代码随想录 (programmercarl.com)
视频讲解
题目n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
你需要按照以下要求给这些孩子分发糖果
每个孩子至少分配到 1 个糖果。
相邻两个孩子评分更高的孩子会获得更多的糖果。
请你给每个孩子分发糖果计算并返回需要准备的 最少糖果数目 。代码
class Solution {
public:int candy(vectorint ratings) {vectorint candyvec(ratings.size(), 1);for (int i 1; i ratings.size(); i)//从左到右if (ratings[i] ratings[i-1]) candyvec[i] candyvec[i-1] 1;for (int i ratings.size()-2; i 0; i--)//从右到左if (ratings[i] ratings[i1]) candyvec[i] max(candyvec[i], candyvec[i1] 1);int ans 0;for (int i : candyvec)ans i;return ans;}
};class Solution {
public:int candy(vectorint ratings) {vectorint left(ratings.size(), 1);vectorint right(ratings.size(), 1);for(int i 1, j ratings.size()-2; i ratings.size(); j--, i){if(ratings[i] ratings[i-1]) left[i] left[i-1]1;if(ratings[j] ratings[j1]) right[j] right[j1]1;} int sum 0;for(int i 0; i ratings.size(); i){sum max(left[i], right[i]);}return sum;}
};
时间复杂度: O(n) 空间复杂度O(1)
⏲4:38
总结重点两边同时比较会顾此失彼。注意点右与左比较时只能正向遍历反向遍历会错失评分连续增长的情况(总之就是两个方向各来一遍)。 ps多个维度考虑时一般先考虑一个维度再考虑另外一个维度。
