网站策划运营,网页设计免费模板参考网页,百度搜索推广多少钱,青岛网站做网站多少钱本文属于「征服LeetCode」系列文章之一#xff0c;这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁#xff0c;本系列将至少持续到刷完所有无锁题之日为止#xff1b;由于LeetCode还在不断地创建新题#xff0c;本系列的终止日期可能是永远。在这一系列刷题文章… 本文属于「征服LeetCode」系列文章之一这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁本系列将至少持续到刷完所有无锁题之日为止由于LeetCode还在不断地创建新题本系列的终止日期可能是永远。在这一系列刷题文章中我不仅会讲解多种解题思路及其优化还会用多种编程语言实现题解涉及到通用解法时更将归纳总结出相应的算法模板。 为了方便在PC上运行调试、分享代码文件我还建立了相关的仓库https://github.com/memcpy0/LeetCode-Conquest。在这一仓库中你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解还可以一同分享给他人。 由于本系列文章的内容随时可能发生更新变动欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。 给你一个长度为 n 的二维整数数组 items 和一个整数 k 。
items[i] [profiti, categoryi]其中 profiti 和 categoryi 分别表示第 i 个项目的利润和类别。
现定义 items 的 子序列 的 优雅度 可以用 total_profit distinct_categories2 计算其中 total_profit 是子序列中所有项目的利润总和distinct_categories 是所选子序列所含的所有类别中不同类别的数量。
你的任务是从 items 所有长度为 k 的子序列中找出 最大优雅度 。
用整数形式表示并返回 items 中所有长度恰好为 k 的子序列的最大优雅度。
注意 数组的子序列是经由原数组删除一些元素可能不删除而产生的新数组且删除不改变其余元素相对顺序。
示例 1
输入items [[3,2],[5,1],[10,1]], k 2
输出17
解释
在这个例子中我们需要选出长度为 2 的子序列。
其中一种方案是 items[0] [3,2] 和 items[2] [10,1] 。
子序列的总利润为 3 10 13 子序列包含 2 种不同类别 [2,1] 。
因此优雅度为 13 22 17 可以证明 17 是可以获得的最大优雅度。示例 2
输入items [[3,1],[3,1],[2,2],[5,3]], k 3
输出19
解释
在这个例子中我们需要选出长度为 3 的子序列。
其中一种方案是 items[0] [3,1] items[2] [2,2] 和 items[3] [5,3] 。
子序列的总利润为 3 2 5 10 子序列包含 3 种不同类别 [1, 2, 3] 。
因此优雅度为 10 32 19 可以证明 19 是可以获得的最大优雅度。示例 3
输入items [[1,1],[2,1],[3,1]], k 3
输出7
解释
在这个例子中我们需要选出长度为 3 的子序列。
我们需要选中所有项目。
子序列的总利润为 1 2 3 6子序列包含 1 种不同类别 [1] 。
因此最大优雅度为 6 12 7 。提示
1 items.length n 10^5items[i].length 2items[i][0] profitiitems[i][1] categoryi1 profiti 10^91 categoryi n1 k n 解法 反悔贪心
按照利润从大到小排序。先把前 k k k 个项目选上。
考虑选第 k 1 k1 k1 个项目为了选它我们必须从前 k k k 个项目中移除一个项目。由于已经按照利润从大到小排序选这个项目不会让 t o t a l _ p r o f i t total\_profit total_profit 变大所以我们重点考虑能否让 d i s t i n c t _ c a t e g o r i e s distinct\_categories distinct_categories 变大。分类讨论
如果第 k 1 k1 k1 个项目和前面某个已选项目的类别相同那么无论怎么移除都不会让 d i s t i n c t _ c a t e g o r i e s distinct\_categories distinct_categories 变大所以无需选择这个项目。如果第 k 1 k1 k1 个项目和前面任何已选项目的类别都不一样考虑移除前面已选项目中的哪一个 如果移除的项目的类别只出现一次那么选第 k 1 k1 k1 个项目后 d i s t i n c t _ c a t e g o r i e s distinct\_categories distinct_categories 一减一增保持不变所以不考虑这种情况。如果移除的项目的类别重复出现多次那么选第 k 1 k1 k1 个项目后 d i s t i n c t _ c a t e g o r i e s distinct\_categories distinct_categories 会增加一此时有可能会让优雅度变大一定要选择这个项目。为什么说「一定」呢因为 t o t a l _ p r o f i t total\_profit total_profit 只会变小我们现在的目标就是让 t o t a l _ p r o f i t total\_profit total_profit 保持尽量大同时让 d i s t i n c t _ c a t e g o r i e s distinct\_categories distinct_categories 增加那么能让 d i s t i n c t _ c a t e g o r i e s distinct\_categories distinct_categories 增加就立刻选上因为后面的利润更小现在不选的话将来 t o t a l _ p r o f i t total\_profit total_profit 只会更小。
按照这个过程继续考虑选择后面的项目。计算优雅度取最大值即为答案。
代码实现时应移除已选项目中类别和前面重复且利润最小的项目这可以用一个栈 d u p l i c a t e duplicate duplicate 来维护由于利润从大到小排序所以栈顶就是最小的利润前面 k k k 次中如果出现了多个重复项则在栈中也会有多个项。注意对于后面的项目由于我们只考虑之前没出现过的类别也就是说这个后面的项目的类别只出现了一次所以不应当加到 d u p l i c a t e duplicate duplicate 中。
class Solution {
public:long long findMaximumElegance(vectorvectorint items, int k) {// 利润从大到小排序sort(items.begin(), items.end(), [](const auto a, const auto b) {return a[0] b[0];});long long totalProfit 0, ans 0;// 利润和 totalProfit 在最大 k 个利润的基础上不会变大unordered_setint vis; // 判断类别是否出现过stackint dup; // 重复类别的利润,栈顶最小for (int i 0, n items.size(); i n; i) {int profit items[i][0], category items[i][1];if (i k) {totalProfit profit;if (vis.count(category)) dup.push(profit);else vis.insert(category);} // 如果新添加的项目的类别之前选过了,则distinct_categories不会变大 else if (!dup.empty() !vis.count(category)) {// 如果新添加的项目的类别之前没有选过,distinct_categories^2可能变大vis.insert(category);// 我们移除最小利润的项目// 如果移除的项目的类别只有1个,则distinct_categories-11,不变,但总利润可能变小// 如果移除的项目的类别有多个,则distinct_categories1,这种情况就是可行的totalProfit - dup.top(); dup.pop(); // 移除掉一个重复且利润最小的项目totalProfit profit; // 本项目目前只出现了一次,不应加入dup中;且以后出现也不会被考虑}ans max(ans, totalProfit (long long)(vis.size() * vis.size()));}return ans;}
};
