资兴市网站建设专业,做细分领域的同城网站,微信公共平台wordpress,长垣高端建站题目链接#xff1a;1005. K 次取反后最大化的数组和
题目描述
给你一个整数数组 nums 和一个整数 k #xff0c;按以下方法修改该数组#xff1a;
选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。
重复这个过程恰好 k 次。可以多次选择同一个下标 i 。
以这种方式修改…题目链接1005. K 次取反后最大化的数组和
题目描述
给你一个整数数组 nums 和一个整数 k 按以下方法修改该数组
选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。
重复这个过程恰好 k 次。可以多次选择同一个下标 i 。
以这种方式修改数组后返回数组 可能的最大和 。
示例 1
输入nums [4,2,3], k 1
输出5
解释选择下标 1 nums 变为 [4,-2,3] 。示例 2
输入nums [3,-1,0,2], k 3
输出6
解释选择下标 (1, 2, 2) nums 变为 [3,1,0,2] 。示例 3
输入nums [2,-3,-1,5,-4], k 2
输出13
解释选择下标 (1, 4) nums 变为 [2,3,-1,5,4] 。提示
1 nums.length 104-100 nums[i] 1001 k 104
文章讲解代码随想录
视频讲解贪心算法这不就是常识还能叫贪心LeetCode1005.K次取反后最大化的数组和_哔哩哔哩_bilibili
题解1暴力法
思路先翻转负数再翻转0然后翻转正数需要处理多种细节。
/*** param {number[]} nums* param {number} k* return {number}*/
var largestSumAfterKNegations function(nums, k) {nums.sort((a, b) a - b);let sum 0;// 翻转负数let i 0;while (i nums.length nums[i] 0 k--) {sum -nums[i];}// 消耗多余翻转次数if (k 0 i nums.length) {if (nums[i] 0) {// 翻转0k 0;} else {// 翻转正数if (i 0) {sum - nums[i];} else {if (k % 2 1) {if (nums[i] -nums[i - 1]) {sum - nums[i];} else {sum 2 * nums[i - 1] nums[i];}} else {sum nums[i];}}}i;} else if (k 0) {if (k % 2 1) {sum 2 * nums[i - 1];}}while (i nums.length) {sum nums[i];}return sum;
};
分析时间复杂度为 O(nlogn)空间复杂度为 O(1)。
题解2贪心算法
思路先对数组按绝对值进行降序排列进行两次贪心策略先翻转负数如果次数还有剩余此时数组中全是非负数然后翻转最小的非负数。
/*** param {number[]} nums* param {number} k* return {number}*/
var largestSumAfterKNegations function(nums, k) {// 将数组按绝对值降序排序nums.sort((a, b) Math.abs(b) - Math.abs(a));// 翻转负数nums nums.map((num) k 0 num 0 k-- -num || num);// 翻转正数if (k % 2 1) {nums[nums.length - 1] -nums[nums.length - 1];}return nums.reduce((a, b) a b);
};
分析时间复杂度为 O(nlogn)空间复杂度为 O(1)。
收获
贪心算法的套路并不固定有些题目需要使用两次贪心策略要注意以局部最优到全局最优的角度思考问题。
