当前位置: 首页 > news >正文

贪心算法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;//操作次数较少时,把最小的负数变为正数//怎么找出较小负数 这里使用sort排序来解决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)

思路:

为什么要创建一个下标数组,因为排序之后对应的最大优势nums1与最后输出结果不同,最后结果是按照未排序时的nums2对应的最大优势时的nums1。

如果在比较过程中出现相等的情况也是按照比不过处理直接拖累最强的一个

代码:

  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;}


http://www.mrgr.cn/news/70717.html

相关文章:

  • 设计模式之创建模式篇
  • Redis原理及应用
  • 蓝桥杯每日真题 - 第18天
  • 『Linux』 第四章 进程—— 进程状态讲解
  • 【Java 学习】数据类型、变量、运算符、条件和循环语句、跳转语句、关键字和标识符
  • 十九 Spring中的八大模式
  • 3.keeplived配置文件
  • VideoChat:开源的数字人实时对话系统,支持自定义数字人的形象和音色
  • 二维差分矩阵 模板题
  • 李佳琦回到巅峰背后,双11成直播电商分水岭
  • 链式结构二叉树
  • 【QT常用技术讲解】任务栏图标+socket网络服务+开机自启动
  • 项目管理平台盘点:2024推荐的9款优质工具
  • jmeter基础05_第1个http请求
  • 【论文速看】DL最新进展202411011-图像超分、Transformer
  • 分布式----Ceph部署(上)
  • 软件测试中的PIE模型
  • 11个简单易用的电商购物车设计案例
  • 算法每日双题精讲——滑动窗口(长度最小的子数组,无重复字符的最长子串)
  • 探索 Java 中的线程池自定义技巧:高效、灵活地管理并发任务!
  • D-Link NAS设备 account_mgr.cgi 未授权RCE漏洞复现(CVE-2024-10914)
  • 【linux】网络基础 ---- 应用层
  • PCL 点云拟合 Ransac拟合圆柱
  • FastHTML快速入门:服务器渲染超媒体应用的利器
  • 并发编程(9)——Actor/CSP设计模式
  • js 数据类型=》理解=》应用