LeetCode 第407场周赛个人题解

目录

100372. 使两个整数相等的位更改次数

原题链接

思路分析

AC代码

100335. 字符串元音游戏

原题链接

思路分析

AC代码

100360. 将 1 移动到末尾的最大操作次数

原题链接

思路分析

AC代码

100329. 使数组等于目标数组所需的最少操作次数

原题链接

思路分析

AC代码

---

100372. 使两个整数相等的位更改次数

原题链接

100372. 使两个整数相等的位更改次数

思路分析

考虑不能存在某位k是1而n不是1，所以k必须是n的子集

n & k != k 就返回-1

否则返回 n ^ k 1 的 个数

时间复杂度：O(1)

AC代码

class Solution:def minChanges(self, n: int, k: int) -> int:if (n & k) != k:return -1return (n ^ k).bit_count()

100335. 字符串元音游戏

原题链接

100335. 字符串元音游戏

思路分析

考虑如果有奇数个元音，那么Alice全拿完就赢了

如果有偶数个元音，记为cnt，那么Alice拿包含cnt - 1个元音的串，照样赢

于是得出：只要有元音就赢

时间复杂度：O(N)

AC代码

class Solution:def doesAliceWin(self, s: str) -> bool:st = set(['a', 'e', 'i', 'o', 'u'])return True if sum(1 for x in s if x in st) else False

100360. 将 1 移动到末尾的最大操作次数

原题链接

100360. 将 1 移动到末尾的最大操作次数

思路分析

赛时写的分组循环，不好看，赛后改了下

我们考虑优先移动左边的1，如果优先移动右边的1那么所有左边的1都只能移动1次

那么我们直接遍历，每遇到一组连续0，前面1的贡献都+1

时间复杂度：O(N)

AC代码

class Solution:def maxOperations(self, s: str) -> int:res = c1 = 0n = len(s)        for i, x in enumerate(s):if x == '1':c1 += 1elif i and s[i - 1] == '1':res += c1return res

100329. 使数组等于目标数组所需的最少操作次数

原题链接

100329. 使数组等于目标数组所需的最少操作次数

思路分析

典中典的题，学差分的时候都会做这个类型的题目吧……

其实就是差分的一个结论：对于一个数组我们要将数组中每个数字变相等（每次可操作子数组-1/+1），最少操作次数为其差分数组从第二个数开始 的正数和 与 负数绝对值和 中大的那一个

为什么呢？

我们考虑原数组变相等 等价于 差分数组除了第一个数外全变为0，而区间操作对应差分数组中左边一个数+1 / -1，右边一个数执行相反操作

那么我们最优方案就是差分数组先正负抵消，再加上剩下的数字绝对值和

由于最后剩下的一定是正数或者负数，所以我们等价为 正数绝对值和 与 负数绝对值和 中 大的那一个

换到本题，等价于 nums - target 的数组全变0

等价于 nums - target 的差分数组全变0

和前面结论不同的是，结论是数组变相等，没有指定具体值，这里指定了0，所以就是整个差分数组的正数和 与 负数和的绝对值 中取大的那一个

时间复杂度：O(N)

AC代码

class Solution:def minimumOperations(self, nums: List[int], target: List[int]) -> int:n = len(nums)diff = [nums[i] - target[i] for i in range(n)]tmp = [nums[i] - target[i] for i in range(n)]for i in range(1, n):diff[i] = tmp[i] - tmp[i - 1]s1 = s2 = 0for x in diff:if x > 0:s1 += xelse:s2 -= xreturn max(s1, s2)