leetcode biweekly contest 124 双周赛的没有参加，总体难度还可以，t4 比较有意思的题目
100221. 相同分数的最大操作数目 I 给你一个整数数组 nums ，如果 nums 至少 包含 2 个元素，你可以执行以下操作：
一次操作的 分数 是被删除元素的和。
在确保 所有操作分数相同 的前提下，请你求出 最多 能进行多少次操作。
请你返回按照上述要求 最多 可以进行的操作次数。
示例 1：
输入：nums = [3,2,1,4,5] 输出：2 解释：我们执行以下操作： - 删除前两个元素，分数为 3 + 2 = 5 ，nums = [1,4,5] 。 - 删除前两个元素，分数为 1 + 4 = 5 ，nums = [5] 。 由于只剩下 1 个元素，我们无法继续进行任何操作。
示例 2：
输入：nums = [3,2,6,1,4] 输出：1 解释：我们执行以下操作： - 删除前两个元素，分数为 3 + 2 = 5 ，nums = [6,1,4] 。 由于下一次操作的分数与前一次不相等，我们无法继续进行任何操作。
提示：
2 <= nums.length <= 1001 <= nums[i] <= 1000
地址 https://leetcode.cn/contest/biweekly-contest-124/problems/maximum-number-of-operations-with-the-same-score-i/
题意 直接模拟
思路
每次查找数组的前两个元素，和是否相等即可。
复杂度分析：
时间复杂度：$O(n)$，其中 $n$ 表示给定数组的长度。
空间复杂度：$O(1)$。
代码 class Solution: def maxOperations(self, nums: List[int]) -> int: tot = nums[0] + nums[1] res = 0 for i in range(0, len(nums), 2): if i + 1 < len(nums) and nums[i] + nums[i + 1] == tot: res += 1 else: break return res
3039. 进行操作使字符串为空 给你一个字符串 s 。
请你进行以下操作直到 s 为 空 ：
每次操作 依次 遍历 'a' 到 'z'，如果当前字符出现在 s 中，那么删除出现位置 最早 的该字符。
请你返回进行 最后 一次操作 之前 的字符串 s 。
示例 1：
输入：s = "aabcbbca" 输出："ba" 解释：我们进行以下操作： - 删除 s = "aabcbbca" 中加粗加斜字符，得到字符串 s = "abbca" 。 - 删除 s = "abbca" 中加粗加斜字符，得到字符串 s = "ba" 。 - 删除 s = "ba" 中加粗加斜字符，得到字符串 s = "" 。 进行最后一次操作之前的字符串为 "ba" 。
示例 2：
输入：s = "abcd" 输出："abcd" 解释：我们进行以下操作： - 删除 s = "abcd" 中加粗加斜字符，得到字符串 s = "" 。 进行最后一次操作之前的字符串为 "abcd" 。
提示：
1 <= s.length <= 5 * 105s 只包含小写英文字母。
地址 https://leetcode.cn/contest/biweekly-contest-124/problems/apply-operations-to-make-string-empty/
题意 直接模拟即可
思路
我们知道最终剩下的字母一定是字母出现次数最多的字母，因此我们统计所有出现次数最多的字母，并输出其最后的一个排序即可，按照字母的先后顺序排序返回即可。
复杂度分析：
时间复杂度：$O(n)$，其中 $n$ 表示给定字符串的长度。
空间复杂度：$O(|\Sigma|)$。
代码 class Solution : def lastNonEmptyString (self, s: str ) -> str : cnt = [[] for _ in range (26 )] for i in range (len (s)): cnt[ord (s[i]) - ord ('a' )].append(i) mx = max (len (cnt[i]) for i in range (26 )) arr = [] for i in range (26 ): if len (cnt[i]) == mx: arr.append((cnt[i][-1 ], i)) arr.sort() return '' .join([chr (ord ('a' ) + i) for _, i in arr])
100220. 相同分数的最大操作数目 II 给你一个整数数组 nums ，如果 nums 至少 包含 2 个元素，你可以执行以下操作中的 任意 一个：
选择 nums 中最前面两个元素并且删除它们。
选择 nums 中最后两个元素并且删除它们。
选择 nums 中第一个和最后一个元素并且删除它们。
一次操作的 分数 是被删除元素的和。
在确保 所有操作分数相同 的前提下，请你求出 最多 能进行多少次操作。
请你返回按照上述要求 最多 可以进行的操作次数。
示例 1：
输入：nums = [3,2,1,2,3,4] 输出：3 解释：我们执行以下操作： - 删除前两个元素，分数为 3 + 2 = 5 ，nums = [1,2,3,4] 。 - 删除第一个元素和最后一个元素，分数为 1 + 4 = 5 ，nums = [2,3] 。 - 删除第一个元素和最后一个元素，分数为 2 + 3 = 5 ，nums = [] 。 由于 nums 为空，我们无法继续进行任何操作。
示例 2：
输入：nums = [3,2,6,1,4] 输出：2 解释：我们执行以下操作： - 删除前两个元素，分数为 3 + 2 = 5 ，nums = [6,1,4] 。 - 删除最后两个元素，分数为 1 + 4 = 5 ，nums = [6] 。 至多进行 2 次操作。
提示：
2 <= nums.length <= 20001 <= nums[i] <= 1000
地址 https://leetcode.cn/contest/biweekly-contest-124/problems/maximum-number-of-operations-with-the-same-score-ii/
题意 记忆化搜索
思路
由于给定的目标值只有三个，我们分别尝试这三个目标值，并通过三种不同的操作尝试达到目标值的操作次数，三个目标值如下：
$nums[0] + nums[1]$;
$num[0] + nums[n-1]$;
$nums[n-2] + nums[n-1]$;
通过记忆化搜索，$dfs(i,j,t)$ 表示数组 $[i,j]$ 中可以操作得到数 $t$ 的操作次数即可。
复杂度分析：
时间复杂度：$O(Cn^2)$, $n$ 表示给定的数组的长度，$C = 3$, 给定的值只有三种；
空间复杂度：$O(n^2)$；
代码 class Solution : def maxOperations (self, nums: List[int ]) -> int : n = len (nums) res = 0 @cache def dfs (i, j, target): ans = 0 if i >= j: return 0 if nums[i] + nums[i + 1 ] == target: ans = max (ans, 1 + dfs (i + 2 , j, target)) if nums[i] + nums[j] == target: ans = max (ans, 1 + dfs (i + 1 , j - 1 , target)) if nums[j - 1 ] + nums[j] == target: ans = max (ans, 1 + dfs (i , j - 2 , target)) return ans res = max (res, dfs (0 , n - 1 , nums[0 ] + nums[1 ])) res = max (res, dfs (0 , n - 1 , nums[0 ] + nums[n - 1 ])) res = max (res, dfs (0 , n - 1 , nums[n - 2 ] + nums[n - 1 ])) return res
100205. 修改数组后最大化数组中的连续元素数目 给你一个下标从 0 开始只包含 正 整数的数组 nums 。
一开始，你可以将数组中 任意数量 元素增加 至多 1 。
修改后，你可以从最终数组中选择 一个或者更多 元素，并确保这些元素升序排序后是 连续 的。比方说，[3, 4, 5] 是连续的，但是 [3, 4, 6] 和 [1, 1, 2, 3] 不是连续的。
请你返回 最多 可以选出的元素数目。
示例 1：
输入：nums = [2,1,5,1,1] 输出：3 解释：我们将下标 0 和 3 处的元素增加 1 ，得到结果数组 nums = [3,1,5,2,1] 。 我们选择元素 [3,1,5,2,1] 并将它们排序得到 [1,2,3] ，是连续元素。 最多可以得到 3 个连续元素。
示例 2：
输入：nums = [1,4,7,10] 输出：1 解释：我们可以选择的最多元素数目是 1 。
提示：
1 <= nums.length <= 1051 <= nums[i] <= 106
地址 https://leetcode.cn/contest/biweekly-contest-124/problems/maximize-consecutive-elements-in-an-array-after-modification/
题意
动态规划
思路
经典的动态规划题目。对于当前的 $x$, 它有两种选择：
要么接在 $x-1$ 的后面；
要么接在 $x$ 的后面，此时 $x$ 变为 $x+1$；
$f(x+1) = f(x) + 1, f(x) = f(x-1) + 1$;
复杂度分析：
时间复杂度：$O(n log n)$，其中 $n$ 表示数组的长度。
空间复杂度：$O(n)$，其中 $n$ 表示数组的长度。
代码 class Solution : def maxSelectedElements (self, nums: List [int ] ) -> int : nums.sort() f = defaultdict(int ) for x in nums: f[x + 1 ] = f[x] + 1 f[x] = f[x - 1 ] + 1 return max (f.values())
欢迎关注和打赏，感谢支持！
