// todo
标签： todo
494.目标和
目标
给你一个非负整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
- 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
示例 1：
输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3示例 2：
输入：nums = [1], target = 1
输出：1说明：
- 1 <= nums.length <= 20
- 0 <= nums[i] <= 1000
- 0 <= sum(nums[i]) <= 1000
- -1000 <= target <= 1000
思路
有一个数组，可以在数组元素前加上正负号来组成表达式，问表达式等于target的数目。
如果当前元素为正则累加，否则相减，递归直到所有元素都已列入表达式，如果累加结果等于target则返回1，否则返回0。
//todo 改为递推，或记忆化搜索
代码
/**
* @date 2024-06-30 20:07
*/
public class FindTargetSumWays494 {
public int findTargetSumWays(int[] nums, int target) {
return dfs(nums, 1, nums[0], target) + dfs(nums, 1, -nums[0], target);
}
public int dfs(int[] nums, int i, int res, int target) {
if (i == nums.length) {
return res - target == 0 ? 1 : 0;
}
return dfs(nums, i + 1, res + nums[i], target) + dfs(nums, i + 1, res - nums[i], target);
}
}
性能
2741.特别的排列
目标
给你一个下标从 0 开始的整数数组 nums ，它包含 n 个 互不相同 的正整数。如果 nums 的一个排列满足以下条件，我们称它是一个特别的排列：
- 对于 0 <= i < n - 1 的下标 i ，要么 nums[i] % nums[i+1] == 0 ，要么 nums[i+1] % nums[i] == 0 。
请你返回特别排列的总数目，由于答案可能很大，请将它对 109 + 7 取余 后返回。
示例 1：
输入：nums = [2,3,6]
输出：2
解释：[3,6,2] 和 [2,6,3] 是 nums 两个特别的排列。示例 2：
输入：nums = [1,4,3]
输出：2
解释：[3,1,4] 和 [4,1,3] 是 nums 两个特别的排列。说明：
- 2 <= nums.length <= 14
- 1 <= nums[i] <= 10^9
思路
有一个互不相同的正整数数组，问使得相邻元素可以被整除（对于相邻元素a % b == 0 || b % a == 0）的排列有多少种。
排列数的计算需要使用dfs，但如果不保存重复子问题的话会超时。
难点在于是否将保存的结果计入，例如 [2,6,3]，虽然dfs 2 -> 6 -> 3 与 6 -> 2 -> 3有重复的子问题3，但是后者不符合题目条件。
// todo
代码
性能
2732.找到矩阵中的好子集
目标
给你一个下标从 0 开始大小为 m x n 的二进制矩阵 grid 。
从原矩阵中选出若干行构成一个行的 非空 子集，如果子集中任何一列的和至多为子集大小的一半，那么我们称这个子集是 好子集。
更正式的，如果选出来的行子集大小（即行的数量）为 k，那么每一列的和至多为 floor(k / 2) 。
请你返回一个整数数组，它包含好子集的行下标，请你将子集中的元素 升序 返回。
如果有多个好子集，你可以返回任意一个。如果没有好子集，请你返回一个空数组。
一个矩阵 grid 的行 子集 ，是删除 grid 中某些（也可能不删除）行后，剩余行构成的元素集合。
示例 1：
输入：grid = [[0,1,1,0],[0,0,0,1],[1,1,1,1]]
输出：[0,1]
解释：我们可以选择第 0 和第 1 行构成一个好子集。
选出来的子集大小为 2 。
- 第 0 列的和为 0 + 0 = 0 ，小于等于子集大小的一半。
- 第 1 列的和为 1 + 0 = 1 ，小于等于子集大小的一半。
- 第 2 列的和为 1 + 0 = 1 ，小于等于子集大小的一半。
- 第 3 列的和为 0 + 1 = 1 ，小于等于子集大小的一半。示例 2：
输入：grid = [[0]]
输出：[0]
解释：我们可以选择第 0 行构成一个好子集。
选出来的子集大小为 1 。
- 第 0 列的和为 0 ，小于等于子集大小的一半。示例 3：
输入：grid = [[1,1,1],[1,1,1]]
输出：[]
解释：没有办法得到一个好子集。说明：
- m == grid.length
- n == grid[i].length
- 1 <= m <= 10^4
- 1 <= n <= 5
grid[i][j]要么是 0 ，要么是 1 。
思路
有一个 m*n 的 二进制矩阵，任选k行，如果每一列的和不大于 k/2，则称为矩阵的好子集，返回任意一个好子集行标的集合。
在写这篇题解的时候才注意到是二进制矩阵，即元素值不是0就是1。这道题是根据提示写的，如果存在好子集则一定存在k为1或2的好子集，然后就根据好子集的要求循环判断。
当k为1时，好子集元素值全为0.当k为2时，任选两行遍历列判断是否有和大于1。
// todo 看一下题解
代码
/**
* @date 2024-06-25 0:28
*/
public class GoodSubsetofBinaryMatrix2732 {
public List<Integer> goodSubsetofBinaryMatrix(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
List<Integer> list = new ArrayList<>();
Queue<Integer> queue = new ArrayDeque<>();
here:
for (int i = 0; i < m; i++) {
queue.offer(i);
for (int j = 0; j < n; j++) {
if (grid[i][j] != 0) {
continue here;
}
}
list.add(i);
}
if (list.size() > 0) {
return list;
}
while (!queue.isEmpty()) {
int i = queue.poll();
here:
for (int j = i + 1; j < m; j++) {
for (int k = 0; k < n; k++) {
if (grid[i][k] + grid[j][k] > 1){
continue here;
}
}
list.add(i);
list.add(j);
return list;
}
}
return list;
}
}
性能
503.下一个更大元素II – 单调栈
目标
给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。
数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。
示例 1:
输入: nums = [1,2,1]
输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2；
数字 2 找不到下一个更大的数；
第二个 1 的下一个最大的数需要循环搜索，结果也是 2。示例 2:
输入: nums = [1,2,3,4,3]
输出: [2,3,4,-1,4]说明:
- 1 <= nums.length <= 10^4
- -10^9 <= nums[i] <= 10^9
思路
暴力解法需要针对每一个元素向后搜索，时间复杂度为O(n^2)。这里面有一些重复的操作，例如，数组 [5,4,3,2,1,6] 找下一个更大的元素，从 5 向后搜索 与从 4 向后搜索有重复的部分 3 2 1。单调栈的核是这样处理的，先将第一个元素下标压入栈中，指针移到下一个元素，如果栈顶对应元素大于等于当前元素则将当前元素下标也压入栈中，否则弹栈，记录 res[stack.pop()] = 当前元素，直到栈顶元素大于等于当前元素。
针对这个题目，栈中保存的下标对应的元素值从栈底到栈顶是单调递减的，如果遇到第一个更大元素就弹栈了，因此称为单调栈。
这样做的好处是避免了重复的查找，它将重复搜索的部分使用栈保存了起来，这样就变成了从后向前搜索。如果栈顶元素遇到了第一个更大的元素，那么它也是前面同样小于该值的第一个更大元素，从而避免了重复查找。
这里对循环数组的处理是将原数组拼接到后面，下标进行取模运算。
代码
/**
* @date 2024-06-24 0:18
*/
public class NextGreaterElements503 {
public int[] nextGreaterElements_v4(int[] nums) {
int n = nums.length;
int[] res = new int[n];
Arrays.fill(res, -1);
int[] stack = new int[n];
int top = -1;
for (int i = 0; i < 2 * n - 1; i++) {
int index = i % n;
while (top > -1 && nums[stack[top]] < nums[index]) {
res[stack[top--]] = nums[index];
}
if (i < n) {
stack[++top] = index;
}
}
return res;
}
}
性能
2713.矩阵中严格递增的单元格数
目标
给你一个下标从 1 开始、大小为 m x n 的整数矩阵 mat，你可以选择任一单元格作为 起始单元格 。
从起始单元格出发，你可以移动到 同一行或同一列 中的任何其他单元格，但前提是目标单元格的值 严格大于 当前单元格的值。
你可以多次重复这一过程，从一个单元格移动到另一个单元格，直到无法再进行任何移动。
请你找出从某个单元开始访问矩阵所能访问的 单元格的最大数量 。
返回一个表示可访问单元格最大数量的整数。
示例 1：
输入：mat = [[3,1],[3,4]]
输出：2
解释：上图展示了从第 1 行、第 2 列的单元格开始，可以访问 2 个单元格。可以证明，无论从哪个单元格开始，最多只能访问 2 个单元格，因此答案是 2 。示例 2：
输入：mat = [[1,1],[1,1]]
输出：1
解释：由于目标单元格必须严格大于当前单元格，在本示例中只能访问 1 个单元格。 示例 3：
输入：mat = [[3,1,6],[-9,5,7]]
输出：4
解释：上图展示了从第 2 行、第 1 列的单元格开始，可以访问 4 个单元格。可以证明，无论从哪个单元格开始，最多只能访问 4 个单元格，因此答案是 4 。 说明：
- m == mat.length
- n == mat[i].length
- 1 <= m, n <= 10^5
- 1 <= m * n <= 10^5
-10^5 <= mat[i][j] <= 10^5
思路
有一个二维矩阵，我们可以从任意元素出发到达同行或同列的任意严格大于该元素值的位置，问我们最多能访问到多少单元格。
最直接的想法就是建立一个有向无环图，然后求最大路径长度。但是建图的过程需要循环mn(m+n)次，针对每个元素判断其同行同列上严格大于的元素。显然会超时。
于是考虑使用记忆化搜索，结果测试用例 558/566 超时，这个二维数组只有一行，有 100000列，从 1~100000，我在本地测试的时候报栈溢出。
我想要将其转为迭代的形式，但是时间紧迫，简单起见对一行或一列的情况做了特殊处理，排序后去重，最后勉强通过了。
官网题解使用的是动态规划，有时间详细看一下。//todo
代码
/**
* @date 2024-06-19 16:28
*/
public class MaxIncreasingCells2713 {
public int maxIncreasingCells(int[][] mat) {
int res = 0;
int m = mat.length;
int n = mat[0].length;
if (m == 1) {
res = n;
Arrays.sort(mat[0]);
for (int i = 1; i < n; i++) {
if (mat[0][i] == mat[0][i - 1]) {
res--;
}
}
return res;
} else if (n == 1) {
res = m;
Arrays.sort(mat, (a, b) -> a[0] - b[0]);
for (int i = 1; i < m; i++) {
if (mat[i][0] == mat[i - 1][0]) {
res--;
}
}
return res;
}
int l = m * n;
// 将二维坐标映射到一维，dp记录的是从该点为起点的能移动的最大次数
int[] dp = new int[l];
Arrays.fill(dp, -1);
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
res = Math.max(res, move(mat, mat[i][j], i * n + j, i, j, dp));
}
}
return res;
}
public int move(int[][] mat, int curVal, int next, int i, int j, int[] dp) {
int m = mat.length;
int n = mat[0].length;
if (dp[next] > -1) {
return dp[next];
} else if (dp[next] == -2) {
return 1;
}
boolean noNext = true;
for (int k = 0; k < n; k++) {
if (mat[i][k] > curVal) {
noNext = false;
dp[next] = Math.max(dp[next], move(mat, mat[i][k], i * n + k, i, k, dp) + 1);
}
}
for (int k = 0; k < m; k++) {
if (mat[k][j] > curVal) {
noNext = false;
dp[next] = Math.max(dp[next], move(mat, mat[k][j], k * n + j, k, j, dp) + 1);
}
}
if (noNext) {
dp[next] = -2;
return 1;
}
return dp[next];
}
}
性能
522.最长特殊序列ⅠⅠ
目标
给定字符串列表 strs ，返回其中 最长的特殊序列 的长度。如果最长特殊序列不存在，返回 -1 。
特殊序列 定义如下：该序列为某字符串 独有的子序列（即不能是其他字符串的子序列）。
s 的 子序列可以通过删去字符串 s 中的某些字符实现。
- 例如，"abc" 是 "aebdc" 的子序列，因为您可以删除"aebdc"中的下划线字符来得到 "abc" 。"aebdc"的子序列还包括"aebdc"、 "aeb" 和 "" (空字符串)。
示例 1：
输入: strs = ["aba","cdc","eae"]
输出: 3示例 2:
输入: strs = ["aaa","aaa","aa"]
输出: -1说明:
- 2 <= strs.length <= 50
- 1 <= strs[i].length <= 10
- strs[i] 只包含小写英文字母
思路
想要使用动态规划一定要先写弄清递推公式，否则思考的方向错了，编码会更加复杂。
这个题需要将每一个字符串与其它字符串比较，判断是否是其它字符串的子序列。
我们无法利用前面计算过的最长特殊序列来得出新的最长特殊序列，例如：
- "aabbcc", "aabbcc", "cb", "abc" 前两个字符串没有特殊子序列，前三个字符串最长特殊子序列为 "cb"，而单看 "cb" 与 "abc" 的最长特殊序列是 "abc"，但 "abc" 是前面两个字符串的子序列。
- "a", "b", "c", "d", "e", "f", "a", "b", "c", "d", "e", "f" 这组字符串如果不到最后一个，最长特殊子序列长度为1，如果整体来看子序列都不是唯一的。
//todo
代码
性能
202.快乐数
目标
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」 定义为：
- 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
- 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
- 如果这个过程 结果为 1，那么这个数就是快乐数。
如果 n 是 快乐数 就返回 true ；不是，则返回 false 。
示例 1：
输入：n = 19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1示例 2：
输入：n = 2
输出：false提示：
1 <= n <= 2^31 - 1
思路
难点是如何确定停止条件，我甚至想过记录循环次数如果超过某一个数就返回false。我意识到这可能是一个数学问题，就放弃了。
看了题解才明白，问题看似是开放的，但也是有规律的，关键是如何分析这个问题。
考虑最终可能出现的情况：
- 最终会得到 1。
- 最终会进入循环。
- 值会越来越大，最后接近无穷大。
考虑不同位数数字的最大值，进行一次计算的结果：
| 位数 | 最大值 | 下一个值 |
|---|---|---|
| 1 | 9 | 81 |
| 2 | 99 | 162 |
| 3 | 999 | 243 |
| 4 | 9999 | 324 |
| 13 | 9999999999999 | 81*13=1053 |
相应位上小于最大值的数字，其下一个值也必定小于最大值的下一个值。
意识到存在循环是很重要的，然后我们可以使用哈希表记录出现过的元素，也可以使用弗洛伊德循环检测算法（Floyd's Cycle-Finding Algorithm）又称为龟兔赛跑算法（Tortoise and Hare Algorithm），注意不是图论中求最短路径的弗洛伊德算法。
// todo 自己实现一下
代码
/**
* @date 2024-06-15 20:59
*/
public class IsHappy202 {
/**
* 快慢指针，也是用来检测链表中是否存在环
* 快慢如果相遇就说明存在环，否则快的先遇到1
*/
class Solution_v1 {
public int getNext(int n) {
int totalSum = 0;
while (n > 0) {
int d = n % 10;
n = n / 10;
totalSum += d * d;
}
return totalSum;
}
public boolean isHappy(int n) {
int slowRunner = n;
int fastRunner = getNext(n);
while (fastRunner != 1 && slowRunner != fastRunner) {
slowRunner = getNext(slowRunner);
fastRunner = getNext(getNext(fastRunner));
}
return fastRunner == 1;
}
}
/**
* Set记录每次的数字，如果重复就返回false
*/
class Solution {
private int getNext(int n) {
int totalSum = 0;
while (n > 0) {
int d = n % 10;
n = n / 10;
totalSum += d * d;
}
return totalSum;
}
public boolean isHappy(int n) {
Set<Integer> seen = new HashSet<>();
while (n != 1 && !seen.contains(n)) {
seen.add(n);
n = getNext(n);
}
return n == 1;
}
}
/**
* 实际上只会存在一个循环4→16→37→58→89→145→42→20→4
*/
private static Set<Integer> cycleMembers =
new HashSet<>(Arrays.asList(4, 16, 37, 58, 89, 145, 42, 20));
public int getNext(int n) {
int totalSum = 0;
while (n > 0) {
int d = n % 10;
n = n / 10;
totalSum += d * d;
}
return totalSum;
}
public boolean isHappy(int n) {
while (n != 1 && !cycleMembers.contains(n)) {
n = getNext(n);
}
return n == 1;
}
}
性能
略
2786.访问数组中的位置使分数最大
目标
给你一个下标从 0 开始的整数数组 nums 和一个正整数 x 。
你 一开始 在数组的位置 0 处，你可以按照下述规则访问数组中的其他位置：
- 如果你当前在位置 i ，那么你可以移动到满足 i < j 的 任意 位置 j 。
- 对于你访问的位置 i ，你可以获得分数 nums[i] 。
- 如果你从位置 i 移动到位置 j 且 nums[i] 和 nums[j] 的 奇偶性 不同，那么你将失去分数 x 。
请你返回你能得到的 最大 得分之和。
注意 ，你一开始的分数为 nums[0] 。
示例 1：
输入：nums = [2,3,6,1,9,2], x = 5
输出：13
解释：我们可以按顺序访问数组中的位置：0 -> 2 -> 3 -> 4 。
对应位置的值为 2 ，6 ，1 和 9 。因为 6 和 1 的奇偶性不同，所以下标从 2 -> 3 让你失去 x = 5 分。
总得分为：2 + 6 + 1 + 9 - 5 = 13 。示例 2：
输入：nums = [2,4,6,8], x = 3
输出：20
解释：数组中的所有元素奇偶性都一样，所以我们可以将每个元素都访问一次，而且不会失去任何分数。
总得分为：2 + 4 + 6 + 8 = 20 。说明：
- 2 <= nums.length <= 10^5
- 1 <= nums[i], x <= 10^6
思路
给定一个数组 nums 与 正整数 x，从下标 0 开始，允许从任意位置 i 开始向后访问位置 j，如果nums[i] 与 nums[j] 的奇偶性相同，则可以获得 nums[j] 分，否则获得 nums[j] - x 分。求能够获得的分数总和的最大值。
刚开始就想到要从后向前，自底向上动态规划，如果当前的奇偶性与与后面的奇偶性相同就累加，否则就将后面的值减去x。接着又想到并不是要每一个节点都要访问，如果节点没有访问奇偶性和谁比较呢？并且后面的得分取决于前一个元素的奇偶性，考虑到昨天的题 子序列最大优雅度，觉得可能方向又错了。
于是就尝试贪心算法，从下标0开始，执行while循环，如果后面的元素奇偶性与之相同，直接累加。对于奇偶性不同的，我们可以考虑累加或者跳过。这样问题就变成了从这个新位置开始向后能获取的最大分数。注意新的位置奇偶性发生了变化。
这么一想问题又变成记忆化搜索了，于是就可以转换为递推/动态规划问题。
// todo 转换为动态规划的写法
代码
/**
* @date 2024-06-14 8:43
*/
public class MaxScore2786 {
public long maxScore(int[] nums, int x) {
int n = nums.length;
long[][] mem = new long[n + 1][2];
for (int i = 0; i < mem.length; i++) {
mem[i] = new long[]{Integer.MIN_VALUE, Integer.MIN_VALUE};
}
long res = nums[0];
int flag = nums[0] % 2;
int i = 1;
while (i < n && nums[i] % 2 == flag) {
res += nums[i];
i++;
}
res += Math.max(0, maxScore(nums, x, i, flag, mem));
return res;
}
public long maxScore(int[] nums, int x, int start, int preFlag, long[][] mem) {
int n = nums.length;
if (start >= n) {
return 0;
}
// 如果选择该节点
int flag = nums[start] % 2;
long select = nums[start];
if (preFlag != flag) {
select -= x;
}
int i = start + 1;
while (i < n && nums[i] % 2 == flag) {
select += nums[i];
i++;
}
if (mem[i][flag] == Integer.MIN_VALUE) {
mem[i][flag] = maxScore(nums, x, i, flag, mem);
}
select += Math.max(0, mem[i][flag]);
// 如果跳过该节点
if (mem[start + 1][preFlag] == Integer.MIN_VALUE) {
mem[start + 1][preFlag] = maxScore(nums, x, start + 1, preFlag, mem);
}
return Math.max(select, mem[start + 1][preFlag]);
}
}
性能
2813.子序列最大优雅度
目标
给你一个长度为 n 的二维整数数组 items 和一个整数 k 。
items[i] = [profiti, categoryi]，其中 profiti 和 categoryi 分别表示第 i 个项目的利润和类别。
现定义 items 的 子序列 的 优雅度 可以用 total_profit + distinct_categories^2 计算，其中 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^5
- items[i].length == 2
items[i][0] == profitiitems[i][1] == categoryi- 1 <= profiti <= 10^9
- 1 <= categoryi <= n
- 1 <= k <= n
思路
已知一个二维数组，元素为[利润, 种类]，数组子序列的优雅值定义为利润和 + 不同种类数量^2，让我们求子序列最大的优雅值是多少。
这道题没有做出来，思考方向错了。刚开始想的是使用记忆化搜索，但是后来发现问题的解不一定能够从子问题得出。即 k-1 子序列的优雅值不一定能够得到 k 子序列的优雅值。
例如：{10, 5} -> {10, 2}, {6, 1}, {9, 5}，k = 3，我们先固定第一项，然后从后面取 k 为 2 的优雅值最大子序列 {10, 2}, {9, 5}。但是与第一项结合之后，发现类别有重复的，优雅值为 29 + 4 = 33，小于取 {10, 2}, {6, 1} 得到的优雅值 26 + 9 = 35。
因此使用递归或者动态规划都是不可解的，不能转换成规模更小的子问题。 //2024.06.14 也有可能是可以解的，只不过没有找到正确的切入点。参考访问数组中的位置使分数最大
官网题解使用的是贪心算法，由于后面会对之前的贪心选择做出调整，有网友称为反悔贪心算法。
由于我们求的是优雅值，相对顺序没有影响，因此可以排序。
然后先取最大的k个值，如果其中类别有重复的，尝试用后面的不同类别替换类别重复但利润较小的，直到没有重复的即可。
这是357场周赛的最后一题，2500多分。
代码
//todo