Leetcode 第 135 场双周赛题解
- Leetcode 第 135 场双周赛题解
- 题目1:3222. 求出硬币游戏的赢家
- 思路
- 代码
- 复杂度分析
- 题目2:3223. 操作后字符串的最短长度
- 思路
- 代码
- 复杂度分析
- 题目3:3224. 使差值相等的最少数组改动次数
- 思路
- 代码
- 复杂度分析
- 题目4:3225. 网格图操作后的最大分数
- 思路
- 代码
- 复杂度分析
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(n3),其中 n 是数组 grid 的长度。由于每个状态只会计算一次,动态规划的时间复杂度 = 状态个数 × 单个状态的计算时间。本题状态个数等于 O(n2),单个状态的计算时间为 O(n),所以动态规划的时间复杂度为 O(n3)。
空间复杂度:O(n2),其中 n 是数组 grid 的长度。