贪心算法day05（k次取反后最大数组和 田径赛马）

目录

1.k次取反后最大化的数组和

2.按身高排序

 3.优势洗牌

---

1.k次取反后最大化的数组和

题目链接：. - 力扣（LeetCode）

思路：

代码：

class Solution {public int largestSumAfterKNegations(int[] nums, int k) {//如何找到最小的数字并且将最小的数字重新放回数组中比较//分情况讨论  如果操作次数小于负数的个数 就不需要将更改的数字从新添加进行比较，只需要将数组从小到大排序后依次取放相加//如果操作次数大于负数的个数 那么也不需要将更改的数字从新添加进行比较// 只需要在最开始的时候找到数组全为正数时的最小值 接着对负数全部取反变为正数相加 剩下的奇数次操作只需将之前找出的数组正数最小值取反一次就好int n = nums.length,min = Integer.MAX_VALUE,m = 0;for(int x:nums){if(x < 0)m++;min = Math.min(min,Math.abs(x));//正数中的最小值}int ret = 0;//操作次数较少时，把最小的负数变为正数if(m > k){Arrays.sort(nums);//对数组进行排序for (int i = 0; i < k; i++) {ret+=-nums[i];}for (int i = k; i < n; i++) {ret+=nums[i];}}else{//把负数全部变成正数for(int x:nums) ret += Math.abs(x);//如果是偶数不进行处理 正数操作偶数次还是正数if((m - k)% 2 != 0){ret -= min*2;}}return ret;}
}

2.按身高排序

题目链接：. - 力扣（LeetCode）

 思路：

class Solution {public String[] sortPeople(String[] names, int[] heights) {int n = names.length;Integer[] index = new Integer[n];//创建一个下标数组for (int i = 0; i < n; i++) {index[i] = i;}//将下标按照身高降低进行排序Arrays.sort(index,(i,j)->{return heights[j] - heights[i];});//提取结果String[] ret = new String[n];for (int i = 0; i < n; i++) {ret[i] = names[index[i]];}return ret;}}

 3.优势洗牌

题目链接：. - 力扣（LeetCode）

思路：

代码：

  public int[] advantageCount(int[] nums1, int[] nums2) {int n = nums1.length;Arrays.sort(nums1);Integer[] index2 = new Integer[n];for (int i = 0; i < n; i++) {index2[i] = i;}Arrays.sort(index2,(i,j)->{return nums2[i] - nums2[j];});int left = 0,right = n - 1;int[] ret = new int[n];for (int x:nums1) {if(x > nums2[index2[left]]){ret[index2[left++]] = x;}else{ret[index2[right--]] = x;}}return ret;}