【leetcode】1090. Largest Values From Labels
2024-10-07 11:26:01
题目如下:
We have a set of items: the
i
-th item has valuevalues[i]
and labellabels[i]
.Then, we choose a subset
S
of these items, such that:
|S| <= num_wanted
- For every label
L
, the number of items inS
with labelL
is<= use_limit
.Return the largest possible sum of the subset
S
.Example 1:
Input: values = [5,4,3,2,1], labels = [1,1,2,2,3],num_wanted
= 3, use_limit = 1
Output: 9
Explanation: The subset chosen is the first, third, and fifth item.Example 2:
Input: values = [5,4,3,2,1], labels = [1,3,3,3,2],num_wanted
= 3, use_limit = 2
Output: 12
Explanation: The subset chosen is the first, second, and third item.Example 3:
Input: values = [9,8,8,7,6], labels = [0,0,0,1,1],num_wanted
= 3, use_limit = 1
Output: 16
Explanation: The subset chosen is the first and fourth item.Example 4:
Input: values = [9,8,8,7,6], labels = [0,0,0,1,1],num_wanted
= 3, use_limit = 2
Output: 24
Explanation: The subset chosen is the first, second, and fourth item.Note:
1 <= values.length == labels.length <= 20000
0 <= values[i], labels[i] <= 20000
1 <= num_wanted, use_limit <= values.length
解题思路:贪心算法。每次取values中的最大值,如果对应labels没有超过限制,那么表示最大值可取;否则继续判断次大值。
代码如下:
class Solution(object):
def largestValsFromLabels(self, values, labels, num_wanted, use_limit):
"""
:type values: List[int]
:type labels: List[int]
:type num_wanted: int
:type use_limit: int
:rtype: int
"""
res = 0
def cmpf(v1,v2):
if v1[0] - v2[0] != 0:
return v2[0] - v1[0]
return v2[1] - v1[1]
val_list = sorted(zip(values,labels),cmp=cmpf) dic = {}
inx = 0
while num_wanted > 0 and inx < len(val_list):
v,l = val_list[inx]
if l not in dic or dic[l] < use_limit:
res += v
dic[l] = dic.setdefault(l,0) + 1
num_wanted -= 1
inx += 1
return res
最新文章
- SQLMAP参数介绍
- ko 简单例子
- Java的SPI机制与简单的示例
- POJ 1741 Tree 树分治
- 转MongoDB 使用Skip和limit分页
- cocos2d ccmenulabel
- SWD接口:探索&;泄密&;延伸
- IAR中 C语言位定义
- DM368启动串口打印分析
- 在打包程序中自动安装SQL Server数据库 .
- web从入门开始(4)--------链接
- nginx反向代理cas server之1:多个cas server负载均衡配置以及ssl配置
- 阿里云Https部署网站
- Delphi中使用ISuperObject解析Json数据
- 实验吧—隐写术——WP之 Fair-Play
- HDU 4819 Mosaic (二维线段树&;区间最值)题解
- cmdb截图
- python中__name__属性的使用
- 徐州网络赛H-Ryuji doesn&#39;t want to study【线段树】
- JavaScript--语法2--语句结构
热门文章
- find查找特殊权限用法
- 错误 warning: LF will be replaced by CRLF in README.md.
- DRF中的视图集的使用
- 006-Spring Boot自动配置-Condition、Conditional、Spring提供的Conditional自动配置
- VMware 接入 Openstack — 使用 Openstack 创建 vCenter 虚拟机
- eclipse 背景绿豆沙颜色
- day18 时间:time:,日历:calendar,可以运算的时间:datatime,系统:sys, 操作系统:os,系统路径操作:os.path,跨文件夹移动文件,递归删除的思路,递归遍历打印目标路径中所有的txt文件,项目开发周期
- JAVA的学习
- vue—拖拽
- locale报错,显示中文乱码