【练习】【贪心】力扣1005. K 次取反后最大化的数组和

题目

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] 。

来源：力扣1005. K 次取反后最大化的数组和

思路（注意事项）

思路一：建立小根堆，每次修改堆顶（即最小值）。
思路二：贪心（条件排序）

纯代码1

class Solution {
public:int largestSumAfterKNegations(vector<int>& nums, int k) {priority_queue<int, vector<int>, greater<int>> q;for (int i = 0; i < nums.size() ; i ++) q.push(nums[i]);int ans = 0;for (int i = 0 ;i < k; i ++){int t = - q.top();q.pop();q.push(t);}while(!q.empty()) ans += q.top(), q.pop();return ans;}
};

题解1（加注释）

class Solution {
public:int largestSumAfterKNegations(vector<int>& nums, int k) {// 定义一个最小堆（优先队列），用于存储数组中的元素priority_queue<int, vector<int>, greater<int>> q;// 将数组中的所有元素放入最小堆for (int i = 0; i < nums.size(); i++) q.push(nums[i]);// ans 用于存储最终的累加和int ans = 0;// 进行 k 次取反操作for (int i = 0; i < k; i++) {// 取出堆顶元素（当前最小的元素）int t = -q.top();// 将堆顶元素弹出q.pop();// 将取反后的元素重新放入堆中q.push(t);}// 计算堆中所有元素的和while (!q.empty()) {ans += q.top(); // 取出堆顶元素并累加到 ansq.pop();        // 弹出堆顶元素}// 返回最终的累加和return ans;}
};

纯代码2

class Solution {
static bool cmp (int a, int b)
{return abs(a) > abs(b);
}
public:int largestSumAfterKNegations(vector<int>& nums, int k) {sort (nums.begin(), nums.end(), cmp);int ans = 0;for (int i = 0; i < nums.size() && k > 0; i ++)if (nums[i] < 0) nums[i] = - nums[i], k --;if (k % 2 == 1) nums[nums.size() - 1] *= -1;for (auto i : nums) ans += i;return ans;}
};

题解2（加注释）

#include <vector>
#include <algorithm>
#include <cmath>class Solution {// 自定义比较函数，用于 std::sort 排序// 该函数的作用是按照绝对值从大到小对元素进行排序static bool cmp (int a, int b){// 返回绝对值大的元素排在前面return abs(a) > abs(b);}
public:// 该函数用于计算经过 k 次取反操作后数组元素的最大和int largestSumAfterKNegations(vector<int>& nums, int k) {// 使用自定义的 cmp 函数对数组进行排序，使得绝对值大的元素排在前面sort (nums.begin(), nums.end(), cmp);// 用于存储最终的数组元素和int ans = 0;// 遍历数组，优先将绝对值大的负数取反for (int i = 0; i < nums.size() && k > 0; i ++) {// 如果当前元素是负数，将其取反，并将 k 减 1if (nums[i] < 0) {nums[i] = - nums[i];k --;}}// 如果 k 还有剩余且为奇数，说明还需要进行一次取反操作// 此时对绝对值最小的元素进行取反，因为前面已经按绝对值从大到小排序，所以最后一个元素绝对值最小if (k % 2 == 1) {nums[nums.size() - 1] *= -1;}// 遍历数组，计算所有元素的和for (auto i : nums) {ans += i;}// 返回最终的和return ans;}
};