【LeetCode - 每日一题】1090. 受标签影响的最大值 (2023.05.23)

news/2024/10/31 5:27:13/

1090. 受标签影响的最大值

题意

  • 涉及两个数组的排序
  • 分别对两个数组的选择有不同的要求

解法1 排序 + 哈希

这道题本质上其实很简单,首先根据 labels 排序,当 labels 相同时,根据 values 从大到小排序,然后将每个 labels 的前 useLimit 个取出来,再将这些取出来的值按从大到小排序,再取前 numWanted 作和即可。

道理也很简单,因为规定了每个 labels 最多只能取 useLimit 次,而要求的又是 values 的最大值,所以结果只和每个 labels 的前 useLimit 个最大的 values 有关。

又由于数据没有负数,所以直接将每个 labels 的前 useLimit 个取出来,直接排序然后无脑求前 numWanted 个数的和即可。

class Solution {
public:int largestValsFromLabels(vector<int>& values, vector<int>& labels, int numWanted, int useLimit) {unordered_map<int, vector<int> > mp;int ans = 0;for(int i = 0; i < values.size(); i++){mp[labels[i]].push_back(values[i]);}for(auto &[label, value] : mp){sort(value.begin(), value.end(), greater<int>());}vector<int> tmp;for(auto &[label, value] : mp){int n = useLimit > value.size() ? value.size() : useLimit;for(int i = 0; i < n; i++){tmp.push_back(value[i]);}}sort(tmp.begin(), tmp.end(), greater<int>());int n = numWanted > tmp.size() ? tmp.size() : numWanted;for(int i = 0; i < n; i++){   ans += tmp[i];}   return ans;}
};

解法2 只排序 values + 哈希

基于额外空间,利用下标同时排序两个数组。

只根据 values 排序,对于 useLimit 这个要求,通过 哈希表 进行维护。

class Solution {
public:int largestValsFromLabels(vector<int>& values, vector<int>& labels, int numWanted, int useLimit) {vector<int> ids(values.size());unordered_map<int,int> mp;int ans = 0;iota(ids.begin(), ids.end(), 0);    // 从 0 开始递增扩充// 这是个匿名函数啊害怕sort(ids.begin(), ids.end(), [&](int a, int b){return values[a] > values[b];});int cnt = 0;for(int i = 0; i < values.size(); i++){mp[labels[ids[i]]]++;if(mp[labels[ids[i]]] > useLimit){continue;}else{ans += values[ids[i]];cnt ++;}if(cnt == numWanted) break;}return ans;}
};

解法3 dfs(TLE)

没注意到数据规模,开头直接无脑 dfs 了,喜提超时。

class Solution {
public:int ans=0;void dfs(vector<int>& values, vector<int>& labels, int idx, int numWanted, int num_cnt, int useLimit, unordered_map<int,int>& mp, int sum){int max_cnt = 0;for(auto &[k,v]:mp){max_cnt = max(max_cnt, v);}// 不满足条件if(num_cnt > numWanted || max_cnt > useLimit || idx > values.size()){return ;}if(idx == values.size()){ans = max(ans, sum);return;}//选mp[labels[idx]]++;sum+=values[idx];num_cnt++;idx++;dfs(values, labels, idx, numWanted, num_cnt, useLimit, mp, sum);//不选mp[labels[idx-1]]--;sum-=values[idx-1];num_cnt--;dfs(values, labels, idx, numWanted, num_cnt, useLimit, mp, sum);}int largestValsFromLabels(vector<int>& values, vector<int>& labels, int numWanted, int useLimit) {unordered_map<int, int> mp;dfs(values, labels, 0, numWanted, 0, useLimit, mp, 0);return ans;}
};


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

相关文章

学习open62541 --- [77] 修改String类型变量的注意点

对于String类型的节点&#xff0c;其值的类型是UA_String&#xff0c;在这篇文章中我们解释了UA_String的生成方法。 当我们修改String类型节点的值时&#xff0c;会事先准备一个UA_String变量&#xff0c;这时就会遇到一个选择&#xff1a;是否需要动态分配内存&#xff0c;即…

决策树及决策树的划分依据(ID3、C4.5、CART)

一、决策树是什么&#xff1f; 决策树是一种基于树状结构的机器学习算法&#xff0c;用于解决分类和回归问题。它是一种自上而下的递归分割方法&#xff0c;通过对特征空间的递归划分来构建一个树形模型&#xff0c;用于进行预测和决策。在决策树中&#xff0c;每个内部节点表…

数学算法组合与排序

一句话总结&#xff1a;组合得次序是否重要&#xff0c;是否可重复&#xff0c;决定了组合数量 一、什么是组合&排序 组合可以是现实的一切事物、例如 [衣服&#xff0c;鞋子&#xff0c;眼镜...] 等等&#xff0c; 也可以表示一组数字 [1, 2, 3, 4, 5] &#xff0c;从个人…

python3.8,torch1.10.2+cu113、torch-geometric 安装

【1】conda create -n name python=3.8 【2】安装 torch 注意先看可适应的最高cuda版本 https://data.pyg.org/whl/ 版本对应 【3】按照顺序安装torch-geometric: torch-sparse、torch-scatter、torch-cluster、 torch-spline-conv \torch-geometric pip install torc…

七牛云图床设置

文章目录 七牛云图床设置下面是用picgo配置图床SSL证书申请https网站显示http图片解决方案 原文链接图床设置&#xff0c;免费SSL证书申请&#xff0c;https网站显示http链接的图片 七牛云图床设置 登录七牛云官网并进行个人注册&#xff0c;然后找到对象存储 点击空间管理&a…

iptables中SNAT、DNAT及iptables服务启动时会自动还原规则

目录 SNAT原理与应用​编辑 SNAT转换前提条件 临时打开&#xff1a; 永久打开&#xff1a; 示例​编辑 DNAT原理与应用​编辑 DNAT转换前提条件 示例​编辑 防火墙规则的备份和还原 导出&#xff08;备份&#xff09;所有表的规则 清空规则​编辑 导入&#xff08;还…

在git中如何撤销分支合并

背景 一个项目&#xff0c;主要开发在dev分支&#xff0c;目前dev分支有需求A&#xff0c;在别的菜单页面也有一个需求B&#xff0c;于是在dev分支下新建了一个分支dev_b&#xff0c;打算等A需求上线&#xff0c;再合并dev_b分支到dev。 具体的操作步骤&#xff1a; 在本地切换…

linux(软硬链接)

目录&#xff1a; 1.软连接 2.硬链接 ----------------------------------------------------------------------------------------------------------------------------- 1.软连接 linux当中有两个概念&#xff0c;一个是软连接&#xff0c;一个是硬链接&#xff0c;在学习…