leetcode 1626. Best Team With No Conflicts(最佳无冲突团队)

news/2024/12/5 6:00:49/

在这里插入图片描述
scores数组中是每个队员的得分,ages数组中为对应队员的年龄,
现在要从这个队里挑选出一些队员,使总得分最高,
挑选时年龄大的要比年龄小的score更高(严格大于),才不会产生冲突。
返回最高的得分。

思路:

因为年龄大的分数不能低于年龄小的,存在一个比较的过程,
所以需要排序,按年龄从小到大排序,这样就从score-age的二维降到了只需要考虑score的一维。

选出尽可能多的队员,而且满足score是升序的(年龄已经升序排列),
所以等同于leetcode 300.最长递增子序列.

所以,按照最长递增子序列的DP来做。
当遍历到 i 时,和前面所有的元素(j = 0 ~ i-1)比较,当scores[i] >= scores[ j ] 时(注意是>=),
说明满足score升序的条件,这时dp[i] = max(dp[i], dp[ j ] + scores[i]), dp[ i ]的初始值为scores[i], 即前面score如果都不要了,就以现在的score为初始值。
(注意这里不是子序列的长度+1, 而是要加上score[ i ])
同时更新score总和的最大值。

还要注意排序时,当age相同时,score要按从小到大的顺序排列,这样才满足递增序列的条件。

class Solution {public int bestTeamScore(int[] scores, int[] ages) {int n = scores.length;Member[] members = new Member[n];int[] dp = new int[n];int res = 0;for(int i = 0; i < n; i++) {members[i] = new Member(scores[i], ages[i]);}Arrays.sort(members, (a, b)->(a.age==b.age?a.score-b.score:a.age-b.age));for(int i = 0; i < n; i++) {dp[i] = members[i].score;for(int j = i-1; j >= 0; j--) {if(members[i].score >= members[j].score) {dp[i] = Math.max(dp[i], dp[j] + members[i].score);}}res = Math.max(res, dp[i]);}return res;}
}class Member{int score = 0;int age = 0;public Member(int score, int age) {this.score = score;this.age = age;}
}

http://www.ppmy.cn/news/20969.html

相关文章

python小游戏——怀念经典坦克大战代码

♥️作者&#xff1a;小刘在这里 ♥️每天分享云计算网络运维课堂笔记&#xff0c;努力不一定有收获&#xff0c;但一定会有收获加油&#xff01;一起努力&#xff0c;共赴美好人生&#xff01; ♥️夕阳下&#xff0c;是最美的&#xff0c;绽放&#xff0c;愿所有的美好&#…

Python流程控制语句之跳转语句

上一篇&#xff1a;Python流程控制语句之循环语句 文章目录前言一、break 语句二、continue 语句三、pass 空语句总结前言 上一篇博客我们讲解了Python中的循环语句&#xff0c;知道循环条件一直满足时&#xff0c;代码将会一直执行下去&#xff0c;就像一辆迷路的车&#xff…

【flyway入门及使用】解决生产环境sql更新遗漏

flyway入门及使用 一、简单介绍 flyway开源的数据库版本管理工具 二、为什么要使用flyway 1.自己写的sql没有在全部环境执行 2.别人写的sql没有在全部环境执行 3.有人修改了已经执行过的SQL&#xff0c;期望再次执行 4.需要新增环境做数据迁移 三、flyway是如何工作 1…

国内在线图表工具,你能说出几个?

之前写过很多篇在线图表、数据分析处理类工具的内容&#xff0c;但都是针对单个问题写的&#xff0c;没有将其整合起来&#xff0c;今天就借着这个问题&#xff0c;做个国内在线图表工具的合集。 一共5大类&#xff0c;每一类各介绍一个代表性工具&#xff0c;全文较长&#x…

can‘t be used as a mixin because it extends a class other than ‘Object‘.

程序员如果敲一会就停半天&#xff0c;抱着一杯茶&#xff0c;表情拧巴&#xff0c;那才是在编程 Flutter 项目开发指导 从基础入门到精通使用目录 前言 - 基础关键字 class&#xff1a;声明一个类&#xff0c;提供具体的成员变量和方法实现。abstract class&#xff1a;声明一…

力扣刷题记录——796. 旋转字符串、884. 两句话中的不常见单词、1046. 最后一块石头的重量

本专栏主要记录力扣的刷题记录&#xff0c;备战蓝桥杯&#xff0c;供复盘和优化算法使用&#xff0c;也希望给大家带来帮助&#xff0c;博主是算法小白&#xff0c;希望各位大佬不要见笑&#xff0c;今天要分享的是——《力扣刷题记录——796. 旋转字符串、884. 两句话中的不常…

【Java Swing】Java组件及事件处理

图形用户接口1、Swing概述2、Swing顶级容器3、布局管理器4、事件处理5、Swing常用组件1、Swing概述 Swing是一种轻量级的组件&#xff0c;它由Java语言开发&#xff0c;可以通过使用简洁的代码、灵活的功能和模块化的组件来创建优雅的用户界面Swing组建的继承关系 2、Swing顶…

MybatisPlus调用原生SQL

文章目录前言方法一方法二总结前言 在有些情况下需要用到MybatisPlus查询原生SQL&#xff0c;MybatisPlus其实带有运行原生SQL的方法。 方法一 这也是网上流传最广的方法&#xff0c;但是我个人认为这个方法并不优雅&#xff0c;且采用${}的方式代码审计可能会无法通过&#…