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 False100360. 将 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 res100329. 使数组等于目标数组所需的最少操作次数
原题链接
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)