摘要：前言的受标签影响的最大值我们有一个项的集合，其中第项的值为，标签为。我们从这些项中选出一个子集，这样一来对于任意的标签，子集中标签为的项的数目总满足。返回子集的最大可能的和。示例输入输出解释选出的子集是第一项，第二项和第三项。
前言
Weekly Contest 141的 受标签影响的最大值：
解题思路我们有一个项的集合，其中第 i 项的值为 values[i]，标签为 labels[i]。
我们从这些项中选出一个子集 S，这样一来：
|S| <= num_wanted
对于任意的标签 L，子集 S 中标签为 L 的项的数目总满足 <= use_limit。
返回子集 S 的最大可能的 和。
示例1：
输入：values = [5,4,3,2,1], labels = [1,1,2,2,3], num_wanted = 3, use_limit = 1 输出：9 解释：选出的子集是第一项，第三项和第五项。示例2：
输入：values = [5,4,3,2,1], labels = [1,3,3,3,2], num_wanted = 3, use_limit = 2 输出：12 解释：选出的子集是第一项，第二项和第三项。示例3：
输入：values = [9,8,8,7,6], labels = [0,0,0,1,1], num_wanted = 3, use_limit = 1 输出：16 解释：选出的子集是第一项和第四项。示例4：
输入：values = [9,8,8,7,6], labels = [0,0,0,1,1], num_wanted = 3, use_limit = 2 输出：24 解释：选出的子集是第一项，第二项和第四项。提示：
1 <= values.length == labels.length <= 20000
0 <= values[i], labels[i] <= 20000
1 <= num_wanted, use_limit <= values.length
本题题目可能会有点难以理解，可用把题目中的项看做带有值的标签。而labels就是标签列表，values就是标签列表对应的标签值列表。
简单点说，标签与标签值的关系为多对多，一个标签可以有多个标签值，而一个相同的值可以多个标签都使用。
而题目的意思就是在所有项中选取num_wanted个元素，但是选取的元素如果存在标签一致的情况，只能存在use_limit个相同标签的项。找出满足上述条件的子集，且该子集的项的标签值之和最大，并返回该最大值。
下面我以示例4作为例子，讲解一下我的解题思路：
输入：values = [9,8,8,7,6], labels = [0,0,0,1,1], num_wanted = 3, use_limit = 2 输出：24 解释：选出的子集是第一项，第二项和第四项。
将values和labels转化为以values为key，每个key对应多个label的结构，同时以key从大到小进行排序。内容如下所示
9 : [0] 8 : [0,0] 7 : [1] 6 : [1]
依次遍历第1步中的数据并进行处理，处理步骤如下：
遍历key对应的label列表
如果该label使用次数小于use_limit，则将将最大值加上对应的key，同时num_wanted自减
每轮循环都要判断num_wanted是否为0
实现代码 /**
* 1090. 受标签影响的最大值
* @param values 标签值列表
* @param labels 标签名列表
* @param num_wanted 期待的标签个数
* @param use_limit 每个标签可重复的次数
* @return
*/
public int largestValsFromLabels(int[] values, int[] labels, int num_wanted, int use_limit) {
// value和label的映射，需要注意使用的是入参values作为key倒序（从大到小）存储
Map> valueLabelMap = new TreeMap<>(Comparator.reverseOrder());
// 每个label的出现次数
Map occurTimes = new HashMap<>();
// 最大值
int result = 0;
for(int i=0;i list=new ArrayList<>();
list.add(labels[i]);
valueLabelMap.put(values[i],list);
}
}
Iterator>> it=valueLabelMap.entrySet().iterator();
while (it.hasNext()){ // 遍历TreeMap
Map.Entry> entry = it.next();
// 对应的值
Integer value = entry.getKey();
List labelList = entry.getValue();
labelList.sort(Comparator.comparing(Integer::intValue));
for(int i=0;i
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/77774.html
摘要：目标中间一段空白把导航栏分为左右两个部分在导航栏上加上一个搜索框，但不被的样式污染。 前置 本文需要对CSS，Vue，ElementUI有基本的了解。 本文以ElementUI提供的导航菜单组件为基础。 本文希望能在此组件基础上实现以下内容： 中间一段空白把导航栏分为左右两个部分 在导航栏上加上一个搜索框，但不被 el-menu-item 的样式污染。 先研究清楚ElementUI...
摘要：本文通过一个简单实例，介绍中的一个叫模块，可以实现全自动获取数据分析数据最终生成分析报告的全部操作。另外更有用的在于通过嵌入网络爬虫，以及对外部的接口，可以快速实现大量手工劳动才能完成的工作，提高工作效率 日常工作当中，特别是金融行业当中，有不少人的工作是提取数据，分析数据，得到可视化图表，并加入自已的研究分析结论，最终生成分析报告，并且有不少报告是定期生成，存在不少重复手工劳动。本文...
摘要：屏幕分辨率是指一块屏幕中画面水平方向的像素值画面垂直方向的像素值。图像分辨率是指每英寸图像内的像素点数。图像分辨率是有单位的，叫像素每英寸。设备像素可能不相同物理像素不会改变，单位是。及英寸，而英寸等于厘米举个 viewport是什么 移动端中，分为两个视口： layout viewport 布局视口: 视口的分辨率接近于PC显示器,也就是html的宽度接近于pc端的宽度。 visu...
摘要：目前基于的环境，有些脚本还是无法获取到内核的变量即使安装了的，更新了的版本，还是不行，需要手动指定参数位置。是执行编译好的脚本。常见错误记录版本太老，导致无法识别到变量，安装可以通过手动调整获取变量的方式。 目前基于ubuntu12 的环境，有些stap 脚本还是无法获取到 内核的变量 （即使安装了ubuntu14 的elfutils，更新了 libc6的版本，还是不行），需要手动指定...
摘要：云端闪存部署细节块存储仅可用于连接到虚拟实例或虚拟机。在这些产品中，只有弹性块存储具有明确使用闪存存储的功能。谷歌云平台提供三种主要存储选项云存储对象永久磁盘块和云文件存储文件。随着闪存存储价格下降且设备容量提升，闪存存储逐渐成为企业的首选存储选项。公共云平台上的存储同样是如此，这些平台具有基于固态的存储产品，可为需要存储功能的应用程序提高性能和吞吐量。本文中，让我们来看看哪些闪存作为云存储...
阅读 3239·2021-11-18 10:02
阅读 2940·2021-11-16 11:39
阅读 3491·2021-09-13 10:25
阅读 1409·2021-09-08 09:35
阅读 1740·2021-07-26 23:38
阅读 2425·2019-08-30 15:44
阅读 2104·2019-08-30 13:51
阅读 1100·2019-08-26 11:35
