数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学Python 中标签的最大值
假设我们有一组项目：第 i 个项目的价值为 values[i]，标签为 labels[i]。然后，我们将选择这些项目的一个子集 S，使得：
- |S| <= num_wanted
- 对于每个标签 L，在 S 中具有标签 L 的项目数量 <= use_limit。
我们必须找到子集 S 的最大可能总和。
例如，如果输入类似于 values = [5,4,3,2,1] 和 labels = [1,1,2,2,3]，num_wanted = 3，use_limit = 1，则输出将为 9。这是因为选择的子集是第一个、第三个和第五个项目。
为了解决这个问题，我们将遵循以下步骤：
- 创建一个数组 v
- 对于 i 从 0 到 values 的长度
- 将 [values[i], labels[i]] 插入 v
- 对 v 数组进行排序
- ans := 0, use := 空映射，i := 0
- 当 num_wanted 和 i < v 的长度
- 如果 use 映射中不存在 v[i, 1]
- 将 num_wanted 减 1
- ans := ans + v[i, 0]
- use[v[i, 1]] := 1
- 否则 use[v[i, 1]] < use_limit
- 将 num_wanted 减 1
- ans := ans + v[i, 0]
- 将 use[v[i, 1]] 加 1
- 将 i 加 1
- 如果 use 映射中不存在 v[i, 1]
- 返回 ans
让我们来看下面的实现，以便更好地理解：
示例
class Solution(object):
def largestValsFromLabels(self, values, labels, num_wanted, use_limit):
v = []
for i in range(len(values)):
v.append([values[i],labels[i]])
v = sorted(v,key = lambda v:v[0],reverse=True)
ans = 0
use = {}
i = 0
while num_wanted and i < len(v):
if v[i][1] not in use:
num_wanted -=1
ans+=v[i][0]
use[v[i][1]] = 1
elif use[v[i][1]]<use_limit:
num_wanted -=1
ans+=v[i][0]
use[v[i][1]]+=1
i+=1
return ans
ob = Solution()
print(ob.largestValsFromLabels([5,4,3,2,1],[1,1,2,2,3],3,1))输入
[5,4,3,2,1] [1,1,2,2,3] 3 1
输出
9
更新于：2020年4月30日
129 次查看
广告