贪心 Leetcode 1005 K次取反后最大化的数组和

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

Leetcode 1005

学习记录自代码随想录

给定一个整数数组 A，我们只能用以下方法修改该数组：我们选择某个索引 i 并将 A[i] 替换为 -A[i]，然后总共重复这个过程 K 次。（我们可以多次选择同一个索引 i。）
以这种方式修改数组后，返回数组可能的最大和。

示例 1：
输入：A = [4,2,3], K = 1
输出：5
解释：选择索引 (1,) ，然后 A 变为 [4,-2,3]。

示例 2：
输入：A = [3,-1,0,2], K = 3
输出：6
解释：选择索引 (1, 2, 2) ，然后 A 变为 [3,1,0,2]。

示例 3：
输入：A = [2,-3,-1,5,-4], K = 2
输出：13
解释：选择索引 (1, 4) ，然后 A 变为 [2,3,-1,5,4]。

提示：
1 <= A.length <= 10000
1 <= K <= 10000
-100 <= A[i] <= 100

要点：1.想到对数组进行排序，按绝对值排序更快；
2.若有负数则取反绝对值最大的复数，若全为正数则反复取反绝对值最小的正数；

方法一：排序后，对最小值取反，之后再次排序，再次对最小值取反，直到k为0，因为需要反复排序效率低

class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        int result = 0;
        
        // 要想到数组的排序
        sort(nums.begin(), nums.end());
        while(k){
            nums[0] = -nums[0];
            k--;
            sort(nums.begin(), nums.end());
        }

        for(int a : nums) result += a;
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

方法二：四步：1.按绝对值从大到小排序；2.遍历数组，若有负数取反，k–；3.遍历完数组后k仍大于0，则反复取反绝对值最小的数直至k为0;4.求和取反；

class Solution {
    // static bool cmp(int a, int b){
    //     return abs(a) > abs(b);
    // } 
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        int result = 0;
        
        // 1.此处按绝对值从大到小排序，保证大绝对值的复数在前面
        // sort(nums.begin(), nums.end(), cmp);
        sort(nums.begin(), nums.end(), [](int a, int b){return abs(a) > abs(b);});
        // 2.有负数取反
        for(int i = 0; i < nums.size(); i++){
            if(nums[i] < 0 && k > 0){
                nums[i] *= -1;
                k--;
            }
        }
        // 3.若k仍>0，反复反转最小绝对值的数
        if(k % 2 == 1) nums[nums.size()-1] *= -1;

        for(int a : nums) result += a;
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25