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 <= q
swap(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：
思路
代码
在这里插入代码片
复杂度分析
时间复杂度：O()。
空间复杂度：O()。
标签：code,题目,lc,nums,int,题解,复杂度,双周,Leetcode From： https://blog.csdn.net/ProgramNovice/article/details/140899027