制作xml网站地图文件,seo优化方案策划书,娄底建设企业网站,设计师网站1688Leetcode 第 135 场双周赛题解 Leetcode 第 135 场双周赛题解题目1#xff1a;3222. 求出硬币游戏的赢家思路代码复杂度分析 题目2#xff1a;3223. 操作后字符串的最短长度思路代码复杂度分析 题目3#xff1a;3224. 使差值相等的最少数组改动次数思路代码复杂度分析 题目4… Leetcode 第 135 场双周赛题解 Leetcode 第 135 场双周赛题解题目13222. 求出硬币游戏的赢家思路代码复杂度分析 题目23223. 操作后字符串的最短长度思路代码复杂度分析 题目33224. 使差值相等的最少数组改动次数思路代码复杂度分析 题目43225. 网格图操作后的最大分数思路代码复杂度分析 Leetcode 第 135 场双周赛题解
题目13222. 求出硬币游戏的赢家
思路
要用价值为 75 和 10 的硬币凑出价值总和为 115 的硬币唯一的可能是 1 个 75 4 个 10。
如果一开始 Alice 就没法选或者偶数轮后 Alice 没法选那么 Bob 胜出否则 Alice 胜出。
设 kmin(x, ⌊y/4⌋)这是能玩的回合数判断 k 的奇偶性即可。
代码
/** lc appleetcode.cn id3222 langcpp** [3222] 求出硬币游戏的赢家*/// lc codestart
class Solution
{
public:string losingPlayer(int x, int y){return min(x, y / 4) % 2 ? Alice : Bob;}
};
// lc codeend复杂度分析
时间复杂度O(1)。
空间复杂度O(1)。
题目23223. 操作后字符串的最短长度
思路
操作次数取决于每种字母的出现次数与字母的位置无关。
假设某个字母出现了 c 次那么操作后该字母最少能剩下多少
根据题意只有当 c≥3 时才能操作每次操作可以把 c 减少 2。
如果 c3, 5, 7,⋯ 是奇数那么不断减 2最终 c1。如果 c4, 6, 8,⋯ 是偶数那么不断减 2最终 c2。
累加每种字母最终剩下的 c即为答案。
代码
/** lc appleetcode.cn id3223 langcpp** [3223] 操作后字符串的最短长度*/// lc codestart
class Solution
{
public:int minimumLength(string s){unordered_mapchar, int freq;for (char c : s)freq[c];int ans 0;for (auto [c, cnt] : freq)ans cnt % 2 ? 1 : 2;return ans;}
};
// lc codeend复杂度分析
时间复杂度O(n∣Σ∣)其中 n 是字符串 s 的长度∣Σ∣ 是字符集合的大小本题字符均为小写字母所以 ∣Σ∣26。
空间复杂度O(∣Σ∣)其中 ∣Σ∣ 是字符集合的大小本题字符均为小写字母所以 ∣Σ∣26。
题目33224. 使差值相等的最少数组改动次数
思路
想一想什么情况下答案是 0什么情况下答案是 1
如果答案是 0意味着所有 ∣nums[i]−nums[n−1−i]∣ 都等于同一个数 X。
如果答案是 1意味着有 n/2−1 个 ∣nums[i]−nums[n−1−i]∣ 都等于同一个数 X。我们只需要修改那对不相等的设这两个数分别为 pnums[i], qnums[n−1−i]。
不妨设 p≤q分类讨论
如果修改 p那么把 p 改成 0 可以让差值尽量大此时差值为 q。如果修改 q那么把 q 改成 k 可以让差值尽量大此时差值为 k−p。如果 max(q,k−p)≥X改其中一个数就行。如果 max(q,k−p)Xp 和 q 两个数都要改。
注意题目保证 n 是偶数。 代码
/** lc appleetcode.cn id3224 langcpp** [3224] 使差值相等的最少数组改动次数*/// lc codestart
class Solution
{
public:int minChanges(vectorint nums, int k){vectorint 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 codeend复杂度分析
时间复杂度O(nk)其中 n 是数组 nums 的长度。
空间复杂度O(k)。
题目43225. 网格图操作后的最大分数
思路
题解【图解】DP 及其优化从 n^4 到 n^3 到 n^2Python/Java/C/Go
代码
#
# lc appleetcode.cn id3225 langpython3
#
# [3225] 网格图操作后的最大分数
## lc codestart
class Solution:def maximumScore(self, grid: List[List[int]]) - int:n len(grid)# 每列的前缀和从上到下col_sum [list(accumulate(col, initial0)) for col in zip(*grid)]# pre 表示第 j1 列的黑格个数# decTrue 意味着第 j1 列的黑格个数 (pre) 第 j2 列的黑格个数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 第 j2 列的黑格个数# 第 j1 列的第 [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 第 j2 列的黑格个数# 此时第 j2 列全黑最优递归过程中一定可以枚举到这种情况# 第 j1 列全白是最优的所以只需考虑 pre0 的情况# 由于第 j1 列在 dfs(j1) 的情况二中已经统计过这里不重复统计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 codeend复杂度分析
时间复杂度O(n3)其中 n 是数组 grid 的长度。由于每个状态只会计算一次动态规划的时间复杂度 状态个数 × 单个状态的计算时间。本题状态个数等于 O(n2)单个状态的计算时间为 O(n)所以动态规划的时间复杂度为 O(n3)。
空间复杂度O(n2)其中 n 是数组 grid 的长度。
