网站关键词多少合适,永兴做网站,教务管理系统可行性研究报告,福建网站建设培训班基于官方题解#xff0c;进行补充说明 给你一个长度为 n 的二维整数数组 items 和一个整数 k 。 items[i] [profiti, categoryi]#xff0c;其中 profiti 和 categoryi 分别表示第 i 个项目的利润和类别。 现定义 items 的 子序列 的 优雅度 可以用 total_profit distinct_… 基于官方题解进行补充说明 给你一个长度为 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 105items[i].length 2items[i][0] profitiitems[i][1] categoryi1 profiti 1091 categoryi n 1 k n 步骤 初始化变量 categorySet用于记录当前子序列中出现的不同类别。 profit记录当前子序列的总利润。 res记录最大的优雅度。 st用来记录那些在子序列中出现了多次的类别的项目的利润。 排序首先按利润从高到低对项目进行排序。这样可以确保我们在选择前 k 个项目时总利润是最大的。 遍历项目对排序后的项目进行遍历。 如果当前项目在前 k 个范围内即子序列还没有达到长度 k 将其利润加入 profit。 将其类别加入 categorySet如果类别已经存在则将利润压入 st 堆栈中。 如果当前项目在 k1 项目之后即子序列已经达到长度 k并且 st 堆栈不为空且当前项目的类别不在 categorySet 中 从 st 中弹出一个利润最小的项目用当前项目替换它增加 profit 和 categorySet。 计算优雅度在每次更新 profit 和 categorySet 后计算当前优雅度并更新最大优雅度 res。
主要逻辑解释 排序Arrays.sort(items, (item0, item1) - item1[0] - item0[0]); 这个步骤确保我们优先选择利润高的项目以保证前 k 个项目的总利润最大。 前 k 项目 if (i k) {profit items[i][0];if (!categorySet.add(items[i][1])) {st.push(items[i][0]);} 对于前 k 个项目直接将利润加入总利润 profit。 将项目的类别加入 categorySet如果类别已经存在则将利润压入 st 堆栈中。 替换逻辑 else if (!st.isEmpty() categorySet.add(items[i][1])) {profit items[i][0] - st.pop();
} 对于第 k1 项目之后的项目如果 st 堆栈不为空且当前项目的类别不在 categorySet 中 从 st 中弹出一个利润最小的项目并用当前项目替换它。这样确保增加新的类别同时总利润减少最少。 计算优雅度 res Math.max(res, profit (long)categorySet.size() * categorySet.size()); 每次更新 profit 和 categorySet 后计算当前优雅度并更新最大优雅度 res。
代码
class Solution {// 初始化变量SetInteger categorySet new HashSet(); // 用于记录当前子序列中出现的不同类别long profit 0; // 当前子序列的总利润long res 0; // 记录最大的优雅度DequeInteger st new ArrayDeque(); // 记录重复类别项目的利润public long findMaximumElegance(int[][] items, int k) {// 按利润从高到低排序Arrays.sort(items, (item0, item1) - item1[0] - item0[0]);for (int i 0; i items.length; i ) {if (i k) {// 在前 k 个项目中// 将项目的利润加入总利润profit items[i][0];if (!categorySet.add(items[i][1])) {// 如果类别已经存在于 categorySet 中将利润压入堆栈。以便后面替换st.push(items[i][0]);}} else if (!st.isEmpty() categorySet.add(items[i][1])) {// 在第 k1 项目及之后并且当前项目的类别不在 categorySet 中// 且堆栈不为空时进行替换操作// 用当前项目替换利润最小的重复类别项目profit items[i][0] - st.pop();}// 计算当前优雅度并更新最大优雅度res Math.max(res, profit (long)categorySet.size() * categorySet.size());}// 返回最大优雅度return res;}
}
详解 st 队列
st 的作用是在处理项目时用于记录那些在子序列中类别出现重复的项目的利润。具体来说当 st 不为空且当前项目的类别与已选子序列中的所有类别都不相同时可以通过从 st 弹出一个利润最小的项目用当前项目替换它从而增加不同类别的数量并尽量减少总利润的减少。下面是更详细的解释
st 的作用 记录重复类别的项目利润当一个项目的类别在子序列中已经存在时将其利润值记录到 st 中。这是因为这些项目不会增加不同类别的数量但它们的利润可能在后续处理中被替换掉。 替换以增加不同类别的数量在处理第 k1 个及之后的项目时如果当前项目的类别不在已选子序列的类别集合 categorySet 中并且 st 不为空可以将当前项目的利润与 st 中最小的利润值进行替换从而增加不同类别的数量并尽量保持总利润的最大化。
详细解释
假设我们当前已经选择了前 k 个项目这时 categorySet 中记录了这些项目的类别。如果其中某些类别重复了那么这些重复类别项目的利润将被压入 st。当我们处理第 k1 个及之后的项目时 如果当前项目的类别不在 categorySet 中且 st 不为空 我们可以将 st 中最小的利润值弹出并用当前项目替换它。这样做有两个好处 增加不同类别的数量。 尽量减少总利润的减少因为我们选择了 st 中最小的利润值进行替换。
代码示例中的 st 用法
for (int i 0; i items.length; i) {if (i k) {profit items[i][0];if (!categorySet.add(items[i][1])) {st.push(items[i][0]);}} else if (!st.isEmpty() categorySet.add(items[i][1])) {profit items[i][0] - st.pop();}res Math.max(res, profit (long)categorySet.size() * categorySet.size());
}
分步解释 处理前 k 个项目 profit items[i][0];将利润加到总利润中。 if (!categorySet.add(items[i][1])) { st.push(items[i][0]); } 如果项目类别已经存在于 categorySet 中将其利润值压入 st。 处理第 k1 个及之后的项目 else if (!st.isEmpty() categorySet.add(items[i][1])) { profit items[i][0] - st.pop(); } 如果当前项目的类别不在 categorySet 中且 st 不为空弹出 st 中最小的利润值假设 st 是一个优先队列能够快速获得最小值并用当前项目的利润替换它。
