网站开发选择框代码,男科24小时免费咨询,公司哪家好点,logo制作在线生成器题目来源#xff1a;https://leetcode.cn/problems/maximize-sum-of-array-after-k-negations/description/ C题解1#xff1a;最直接的想法就是负的变正的#xff0c;如果负的元素数量小于k#xff0c;就挑选绝对值大的负数变正#xff1b;如果负的元素数量大于k#xf…题目来源https://leetcode.cn/problems/maximize-sum-of-array-after-k-negations/description/ C题解1最直接的想法就是负的变正的如果负的元素数量小于k就挑选绝对值大的负数变正如果负的元素数量大于k那么还需要根据剩下的k待变换数的奇偶性来判断偶数就不用管了奇数就减去2倍的绝对值最小数。
class Solution {
public:int largestSumAfterKNegations(vectorint nums, int k) {sort(nums.begin(), nums.end());int res 0, len nums.size();for(int i 0; i len; i) {if(nums[i] 0 i k) nums[i] -nums[i];else if(nums[i] 0 i k) k 0;else if(nums[i] 0 i k){if((k - i) % 2 ! 0) {if(i 0) {nums[i] -nums[i];}else {if(nums[i] nums[i-1]) {nums[i] -nums[i];}else {res res - 2 * nums[i-1];}}}k 0;} res res nums[i];}// k没有变0说明还需要进行取反操作if(k len (k - len) % 2 1) {res res - 2 * nums[len - 1];}return res;}
};
C题解2来源代码随想录采用贪心算法的思路来求解。重写了sort的cmp函数。
第一步将数组按照绝对值大小从大到小排序注意要按照绝对值的大小第二步从前向后遍历遇到负数将其变为正数同时K--第三步如果K还大于0那么反复转变数值最小的元素将K用完第四步求和
class Solution {
static bool cmp(int a, int b) {return abs(a) abs(b);
}
public:int largestSumAfterKNegations(vectorint A, int K) {sort(A.begin(), A.end(), cmp); // 第一步for (int i 0; i A.size(); i) { // 第二步if (A[i] 0 K 0) {A[i] * -1;K--;}}if (K % 2 1) A[A.size() - 1] * -1; // 第三步int result 0;for (int a : A) result a; // 第四步return result;}
};
