顺德网站,百度广告官网,网站和做游戏,白山网站设计题目 1005 K 次取反后最大化的数组和 给你一个整数数组 nums 和一个整数 k #xff0c;按以下方法修改该数组#xff1a; 选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。 重复这个过程恰好 k 次。可以多次选择同一个下标 i 。 以这种方式修改数组后#xff0c;返回数组 可…题目 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(vectorint nums, int k) {priority_queueint, vectorint, greaterint 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(vectorint nums, int k) {// 定义一个最小堆优先队列用于存储数组中的元素priority_queueint, vectorint, greaterint 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(vectorint 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 cmathclass Solution {// 自定义比较函数用于 std::sort 排序// 该函数的作用是按照绝对值从大到小对元素进行排序static bool cmp (int a, int b){// 返回绝对值大的元素排在前面return abs(a) abs(b);}
public:// 该函数用于计算经过 k 次取反操作后数组元素的最大和int largestSumAfterKNegations(vectorint 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;}
};
