本文主要是介绍2024.6.13每日一题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
LeetCode
子序列最大优雅度
题目链接:2813. 子序列最大优雅度 - 力扣(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 <= 105
items[i].length == 2
items[i][0] == profiti
items[i][1] == categoryi
1 <= profiti <= 109
1 <= categoryi <= n
1 <= k <= n
思路
代码
C++
class Solution {
public:long long findMaximumElegance(vector<vector<int>>& items, int k) {// 把利润从大到小排序ranges::sort(items, [](const auto &a, const auto &b) { return a[0] > b[0]; });long long ans = 0, total_profit = 0;unordered_set<int> vis;stack<int> duplicate; // 重复类别的利润for (int i = 0; i < items.size(); i++) {int profit = items[i][0], category = items[i][1];if (i < k) {total_profit += profit; // 累加前 k 个项目的利润if (!vis.insert(category).second) { // 重复类别duplicate.push(profit);}} else if (!duplicate.empty() && vis.insert(category).second) { // 之前没有的类别total_profit += profit - duplicate.top(); // 选一个重复类别中的最小利润替换duplicate.pop();} // else:比前面的利润小,而且类别还重复了,选它只会让 total_profit 变小,vis.size() 不变,优雅度不会变大ans = max(ans, total_profit + (long long) vis.size() * (long long) vis.size());}return ans;}
};
Java
class Solution {public long findMaximumElegance(int[][] items, int k) {// 把利润从大到小排序Arrays.sort(items, (a, b) -> b[0] - a[0]);long ans = 0;long totalProfit = 0;Set<Integer> vis = new HashSet<>();Deque<Integer> duplicate = new ArrayDeque<>(); // 重复类别的利润for (int i = 0; i < items.length; i++) {int profit = items[i][0];int category = items[i][1];if (i < k) {totalProfit += profit; // 累加前 k 个项目的利润if (!vis.add(category)) { // 重复类别duplicate.push(profit);}} else if (!duplicate.isEmpty() && vis.add(category)) { // 之前没有的类别totalProfit += profit - duplicate.pop(); // 选一个重复类别中的最小利润替换} // else:比前面的利润小,而且类别还重复了,选它只会让 totalProfit 变小,vis.size() 不变,优雅度不会变大ans = Math.max(ans, totalProfit + (long) vis.size() * vis.size()); // 注意 1e5*1e5 会溢出}return ans;}
}
这篇关于2024.6.13每日一题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!