Leetcode 第 135 场双周赛题解

Leetcode 第 135 场双周赛题解

题目1：3222. 求出硬币游戏的赢家

思路

要用价值为 75 和 10 的硬币凑出价值总和为 115 的硬币，唯一的可能是 1 个 75 + 4 个 10。

如果一开始 Alice 就没法选，或者偶数轮后 Alice 没法选，那么 Bob 胜出，否则 Alice 胜出。

设 k=min(x, ⌊y/4⌋)，这是能玩的回合数，判断 k 的奇偶性即可。

代码

/** @lc app=leetcode.cn id=3222 lang=cpp** [3222] 求出硬币游戏的赢家*/// @lc code=start
class Solution
{
public:string losingPlayer(int x, int y){return min(x, y / 4) % 2 ? "Alice" : "Bob";}
};
// @lc code=end

复杂度分析

时间复杂度：O(1)。

空间复杂度：O(1)。

题目2：3223. 操作后字符串的最短长度

思路

操作次数取决于每种字母的出现次数，与字母的位置无关。

假设某个字母出现了 c 次，那么操作后该字母最少能剩下多少？

根据题意，只有当 c≥3 时才能操作，每次操作可以把 c 减少 2。

• 如果 c=3, 5, 7,⋯ 是奇数，那么不断减 2，最终 c=1。
• 如果 c=4, 6, 8,⋯ 是偶数，那么不断减 2，最终 c=2。

累加每种字母最终剩下的 c，即为答案。

代码

/** @lc app=leetcode.cn id=3223 lang=cpp** [3223] 操作后字符串的最短长度*/// @lc code=start
class Solution
{
public:int minimumLength(string s){unordered_map<char, int> freq;for (char &c : s)freq[c]++;int ans = 0;for (auto &[c, cnt] : freq)ans += cnt % 2 ? 1 : 2;return ans;}
};
// @lc code=end

复杂度分析

时间复杂度：O(n+∣Σ∣)，其中 n 是字符串 s 的长度，∣Σ∣ 是字符集合的大小，本题字符均为小写字母，所以 ∣Σ∣=26。

空间复杂度：O(∣Σ∣)，其中 ∣Σ∣ 是字符集合的大小，本题字符均为小写字母，所以 ∣Σ∣=26。

题目3：3224. 使差值相等的最少数组改动次数

思路

想一想，什么情况下答案是 0？什么情况下答案是 1？

如果答案是 0，意味着所有 ∣nums[i]−nums[n−1−i]∣ 都等于同一个数 X。

如果答案是 1，意味着有 n/2−1 个 ∣nums[i]−nums[n−1−i]∣ 都等于同一个数 X。我们只需要修改那对不相等的，设这两个数分别为 p=nums[i], q=nums[n−1−i]。

不妨设 p≤q，分类讨论：

• 如果修改 p，那么把 p 改成 0 可以让差值尽量大，此时差值为 q。
• 如果修改 q，那么把 q 改成 k 可以让差值尽量大，此时差值为 k−p。
• 如果 max(q,k−p)≥X，改其中一个数就行。
• 如果 max(q,k−p)<X，p 和 q 两个数都要改。

注意题目保证 n 是偶数。

代码

/** @lc app=leetcode.cn id=3224 lang=cpp** [3224] 使差值相等的最少数组改动次数*/// @lc code=start
class Solution
{
public:int minChanges(vector<int> &nums, int k){vector<int> cnt(k + 1), cnt2(k + 1);int n = nums.size();for (int i = 0; i < n / 2; i++){int p = nums[i], q = nums[n - 1 - i];if (p > q){ // 保证 p <= qswap(p, q);}cnt[q - p]++;cnt2[max(q, k - p)]++;}int ans = n;int sum2 = 0; // 统计有多少对 (p,q) 都要改for (int x = 0; x <= k; x++){// 其他 n/2-cnt[x] 对 (p,q) 至少要改一个数，在此基础上，有额外的 sum2 对 (p,q) 还要再改一个数ans = min(ans, n / 2 - cnt[x] + sum2);// 对于后面的更大的 x，当前的这 cnt2[x] 对 (p,q) 都要改sum2 += cnt2[x];}return ans;}
};
// @lc code=end

复杂度分析

时间复杂度：O(n+k)，其中 n 是数组 nums 的长度。

空间复杂度：O(k)。

题目4：3225. 网格图操作后的最大分数

思路

题解：【图解】DP 及其优化：从 n^4 到 n^3 到 n^2（Python/Java/C++/Go）

代码

#
# @lc app=leetcode.cn id=3225 lang=python3
#
# [3225] 网格图操作后的最大分数
## @lc code=start
class Solution:def maximumScore(self, grid: List[List[int]]) -> int:n = len(grid)# 每列的前缀和（从上到下）col_sum = [list(accumulate(col, initial=0)) for col in zip(*grid)]# pre 表示第 j+1 列的黑格个数# dec=True 意味着第 j+1 列的黑格个数 (pre) < 第 j+2 列的黑格个数@cachedef dfs(j: int, pre: int, dec: bool) -> int:if j < 0:return 0res = 0# 枚举第 j 列有 cur 个黑格for cur in range(n + 1):if cur == pre:  # 情况一：相等# 没有可以计入总分的格子res = max(res, dfs(j - 1, cur, False))elif cur < pre:  # 情况二：右边黑格多# 第 j 列的第 [cur, pre) 行的格子可以计入总分res = max(res, dfs(j - 1, cur, True) + col_sum[j][pre] - col_sum[j][cur])elif not dec:  # 情况三：cur > pre >= 第 j+2 列的黑格个数# 第 j+1 列的第 [pre, cur) 行的格子可以计入总分res = max(res, dfs(j - 1, cur, False) + col_sum[j + 1][cur] - col_sum[j + 1][pre])elif pre == 0:  # 情况四（凹形）：cur > pre < 第 j+2 列的黑格个数# 此时第 j+2 列全黑最优（递归过程中一定可以枚举到这种情况）# 第 j+1 列全白是最优的，所以只需考虑 pre=0 的情况# 由于第 j+1 列在 dfs(j+1) 的情况二中已经统计过，这里不重复统计res = max(res, dfs(j - 1, cur, False))return res# 枚举第 n-1 列有 i 个黑格return max(dfs(n - 2, i, False) for i in range(n + 1))
# @lc code=end

复杂度分析

时间复杂度：O(n³)，其中 n 是数组 grid 的长度。由于每个状态只会计算一次，动态规划的时间复杂度 = 状态个数 × 单个状态的计算时间。本题状态个数等于 O(n²)，单个状态的计算时间为 O(n)，所以动态规划的时间复杂度为 O(n³)。

空间复杂度：O(n²)，其中 n 是数组 grid 的长度。