关联LeetCode题号1005
本题特点
- 贪心：局部最优解：将负数取反得到比原值大的值，进而全局最优解整体和为最大
- 二次贪心: 如果取反次数大于负数个数，那么剩下次数如果为奇数，那么就将绝对值最小的数取反（贪心贪在：正数绝对值取反得到的值最小局部最优，进而全局最优得到最大的和）
本题思路
- 情况1：按照从大到小的排序，如果k不为0并且负数进行取反，
- 情况2：若k有剩余，并且剩余未奇数，将绝对值最小的数取反，偶数则无影响
class Solution:def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:nums.sort(key=lambda x: abs(x), reverse=True)for i in range(len(nums)):if nums[i] < 0 and k != 0:nums[i] *= -1k -= 1if k % 2 == 1:nums[-1] *= -1return sum(nums)Java写法
package leetcode;import org.junit.jupiter.api.Test;import java.util.Arrays;import java.util.stream.IntStream;/*** File Description: MaximizeSumOfArrayAfterKNegations* Author: Your Name* Date: 2024/12/23*/
public class MaximizeSumOfArrayAfterKNegations_1005 {public int largestSumAfterKNegations(int[] nums, int k) {Arrays.sort(nums);for (int i=0; i < nums.length; i++){if (nums[i] < 0){nums[i] *= -1;k --;}}if(k % 2 == 1){Arrays.sort(nums);nums[0] *= -1;}int sum = 0;for(int n: nums){sum += n;}return sum;}public int largestSumAfterKNegations2(int[] nums, int k) {nums = IntStream.of(nums).boxed().sorted((o1, o2) -> Math.abs(o2) - Math.abs(o1)).mapToInt(Integer::intValue).toArray();for (int i=0; i < nums.length; i++){if (nums[i] < 0 && k != 0){nums[i] *= -1;k --;}}if (k % 2 == 1){nums[nums.length-1] *= -1;}int sum = IntStream.of(nums).sum();return sum;}@Testpublic void largestSumAfterKNegationsTest(){int[] nums = {3, -1, 0, 2};int s = largestSumAfterKNegations(nums, 3);int s1 = largestSumAfterKNegations2(nums, 3);System.out.println(s1);}}
函数式编程&&lambda表达式
nums = IntStream.of(nums).boxed().sorted((o1, o2) -> Math.abs(o2) - Math.abs(o1)).mapToInt(Integer::intValue).toArray();
函数式编程☞结合Stream API
IntStream、LongStream、DoubleStream，java特别为这三种基本数值型提供了对应的 Stream。
IntStream.of(nums)创建流
boxed()方法将其元素封装为Integer对象，而不是基本的整型值。
sorted((o1, o2) -> Math.abs(o2) - Math.abs(o1)) 按照绝对值从大到小排序 --中间操作
mapToInt(Integer::intValue) 将Integer对象转换为基本数据类型 返回IntStream流--中间操作
方法引用- 类：：静态方法
toArray(); 将流转成数组--终止操作