leetcode 1005 K次取反后最大化的数组和

古城微笑少年丶 2022-08-28 09:42 109阅读 0赞

## 前言 ##

题目：[1005. K 次取反后最大化的数组和][1005. K]

参考题解：[K次取反后最大化的数组和-代码随想录][K_-]

--------------------

## 提交代码 ##

核心思路：尽可能将负数翻转。如果负数全部翻转之后，还有剩余翻转次数。全部用于翻转绝对值最小的那个数字。

### 方法一：自然数排序 ###

按照自然数排序，实现上面思路。比较繁琐，注意细节。

class Solution {
    public:
        int largestSumAfterKNegations(vector<int>& nums, int k) {
            sort(nums.begin(),nums.end()); // 从低到高排序
    
            int zero_lower_bound = lower_bound(nums.begin(),nums.end(),0) - nums.begin(); // 返回第一个大于等于0的位置
    
            if(k < zero_lower_bound+1){ // 全部用于将将负数变为整数
                for(int i=0; i<k; i++)
                    nums[i] = -nums[i];
            }else if(k > zero_lower_bound){
                for(int i=0; i<zero_lower_bound; i++) // 将全部负数变为整数之后
                    nums[i] = -nums[i];
                k = k-(zero_lower_bound+1-1); // 剩余翻转次数
                if(k%2 == 0) // 剩余为偶数，正反抵消
                    ; 
                else{ // 剩余为奇数，用一次翻转当前最小的元素
                    if(zero_lower_bound == 0) // 原来的元素全为整数，翻转第一个元素
                        nums[0] = -nums[0];
                    else if(zero_lower_bound == nums.size()) // 原来的元素全为负数，翻转最后一个元素
                        nums[zero_lower_bound -1] = -nums[zero_lower_bound-1];
                    else{ // 原来正负交替，翻转zero_lower_bound-1 or zero_lower_bound位置元素
                        int min_i;
                        if(nums[zero_lower_bound-1] < nums[zero_lower_bound])
                            min_i = zero_lower_bound-1;
                        else 
                            min_i = zero_lower_bound;
                        nums[min_i] = -nums[min_i];
                    }
                }
            }
    
            // 累加求和
            int result = 0;
            for(int num : nums)
                result += num;
            return result;
        }
    };

### 方法二：绝对值排序 ###

下面思路和代码实现，来自参考题解。

*  第一步：将数组按照绝对值大小从大到小排序，注意要按照绝对值的大小
 *  第二步：从前向后遍历，遇到负数将其变为正数，同时K–
 *  第三步：如果K还大于0，那么反复转变数值最小的元素，将K用完
 *  第四步：求和

class Solution {
    static bool cmp(int a, int b) {
        return abs(a) > abs(b);
    }
    public:
        int largestSumAfterKNegations(vector<int>& 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;
        }
    };

[1005. K]: https://leetcode-cn.com/problems/maximize-sum-of-array-after-k-negations/
[K_-]: https://github.com/youngyangyang04/leetcode-master/blob/master/problems/1005.K%E6%AC%A1%E5%8F%96%E5%8F%8D%E5%90%8E%E6%9C%80%E5%A4%A7%E5%8C%96%E7%9A%84%E6%95%B0%E7%BB%84%E5%92%8C.md