leetcode weekly contest 407

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

给你两个正整数 n 和 k。

你可以选择 n 的 二进制表示 中任意一个值为 1 的位，并将其改为 0。

返回使得 n 等于 k 所需要的更改次数。如果无法实现，返回 -1。

示例 1：

输入： n = 13, k = 4

输出： 2

解释：
最初，n 和 k 的二进制表示分别为 n = (1101)2 和 k = (0100)2，

我们可以改变 n 的第一位和第四位。结果整数为 n = (**0**10**0**)2 = k。

示例 2：

输入： n = 21, k = 21

输出： 0

解释：
n 和 k 已经相等，因此不需要更改。

示例 3：

输入： n = 14, k = 13

输出： -1

解释：
无法使 n 等于 k。

提示：

• 1 <= n, k <= 106

地址

https://leetcode.cn/contest/weekly-contest-407/problems/number-of-bit-changes-to-make-two-integers-equal/

题意

模拟

思路

1. 统计 $n$ 与 $k$ 两个数中数位不同的个数即可。
2. 复杂度分析：

• 时间复杂度：$O(1)$。
• 空间复杂度：$O(1)$。

代码

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

3227. 字符串元音游戏

小红和小明在玩一个字符串元音游戏。

给你一个字符串 s，小红和小明将轮流参与游戏，小红 先 开始：

• 在小红的回合，她必须移除 s 中包含 奇数 个元音的任意 非空 子字符串。
• 在小明的回合，他必须移除 s 中包含 偶数 个元音的任意 非空 子字符串。

第一个无法在其回合内进行移除操作的玩家输掉游戏。假设小红和小明都采取 最优策略 。

如果小红赢得游戏，返回 true，否则返回 false。

英文元音字母包括：a, e, i, o, 和 u。

示例 1：

输入： s = “leetcoder”

输出： true

解释：
小红可以执行如下移除操作来赢得游戏：

• 小红先手，她可以移除加下划线的子字符串 s = "**leetco**der"，其中包含 3 个元音。结果字符串为 s = "der"。
• 小明接着，他可以移除加下划线的子字符串 s = "**d**er"，其中包含 0 个元音。结果字符串为 s = "er"。
• 小红再次操作，她可以移除整个字符串 s = "**er**"，其中包含 1 个元音。
• 又轮到小明，由于字符串为空，无法执行移除操作，因此小红赢得游戏。

示例 2：

输入： s = “bbcd”

输出： false

解释：
小红在她的第一回合无法执行移除操作，因此小红输掉了游戏。

提示：

• 1 <= s.length <= 105
• s 仅由小写英文字母组成。

地址

https://leetcode.cn/contest/weekly-contest-407/problems/vowels-game-in-a-string/

题意

模拟

思路

1. 本质即为统计字符串出现元音字符的数目，假设字符串中出现元音字符的个数为 $x$ 且满足 $x > 0$，则此时最多经过两次即可取玩：
   • 如果 $x$ 为奇数，则小红先手可以一次把字符串全部取完，此时小明会输；
   • 如果 $x$ 为偶数，则小红可以先取奇数个字符，然后剩余的元音字符也为奇数个，此时小明只能取偶数个，因此无论如何取，小红在下一回去取得时候一定可以把所有得字符全部取完；
2. 复杂度分析：

• 时间复杂度：$O(n)$，其中 $n$ 表示给定字符串得长度。
• 空间复杂度：$O(1)$；

代码

class Solution:
    def doesAliceWin(self, s: str) -> bool:
        return sum(1 if c in ['a', 'o','e', 'i', 'u'] else 0 for c in s) > 0

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

给你一个 二进制字符串 s。

你可以对这个字符串执行 任意次 下述操作：

• 选择字符串中的任一下标 i（ i + 1 < s.length ），该下标满足 s[i] == '1' 且 s[i + 1] == '0'。
• 将字符 s[i] 向 右移 直到它到达字符串的末端或另一个 '1'。例如，对于 s = "010010"，如果我们选择 i = 1，结果字符串将会是 s = "0**001**10"。

返回你能执行的 最大 操作次数。

示例 1：

输入： s = “1001101”

输出： 4

解释：

可以执行以下操作：

• 选择下标 i = 0。结果字符串为 s = "**001**1101"。
• 选择下标 i = 4。结果字符串为 s = "0011**01**1"。
• 选择下标 i = 3。结果字符串为 s = "001**01**11"。
• 选择下标 i = 2。结果字符串为 s = "00**01**111"。

示例 2：

输入： s = “00111”

输出： 0

提示：

• 1 <= s.length <= 105
• s[i] 为 '0' 或 '1'。

地址

https://leetcode.cn/contest/weekly-contest-406/problems/minimum-cost-for-cutting-cake-i/

题意

直接模拟

思路

1. 我们可以观察到，假设字符得末尾全部是 $1$ 则一定无法移动，我们从左到右遍历字符串，此时假设当前已经有 $x$ 个 $1$，此时遇到下一次 $01$ 交替时，我们一定可以移动 $x$ 次，此时接着连续有 $y$ 个 $1$，则此时遇到下一个 $01$，则一定可以移动 $x+ y$ 次，我们按照上诉方式模拟即可。

2. 复杂度分析：

• 时间复杂度：$O(n)$，其中 $n$ 表示给定字符串的长度;
• 空间复杂度：$O(1)$;

代码

class Solution:
    def maxOperations(self, s: str) -> int:
        ans, cnt = 0, 0
        for i, c in enumerate(s):
            if c == '1':
                cnt += 1
            elif i and s[i - 1] == '1':
                ans += cnt
        
        return ans

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

给你两个长度相同的正整数数组 nums 和 target。

在一次操作中，你可以选择 nums 的任何子数组，并将该子数组内的每个元素的值增加或减少 1。

返回使 nums 数组变为 target 数组所需的 最少 操作次数。

示例 1：

输入： nums = [3,5,1,2], target = [4,6,2,4]

输出： 2

解释：

执行以下操作可以使 nums 等于 target：
- nums[0..3] 增加 1，nums = [4,6,2,3]。
- nums[3..3] 增加 1，nums = [4,6,2,4]。

示例 2：

输入： nums = [1,3,2], target = [2,1,4]

输出： 5

解释：

执行以下操作可以使 nums 等于 target：
- nums[0..0] 增加 1，nums = [2,3,2]。
- nums[1..1] 减少 1，nums = [2,2,2]。
- nums[1..1] 减少 1，nums = [2,1,2]。
- nums[2..2] 增加 1，nums = [2,1,3]。
- nums[2..2] 增加 1，nums = [2,1,4]。

提示：

• 1 <= nums.length == target.length <= 105
• 1 <= nums[i], target[i] <= 108

地址

https://leetcode.cn/contest/weekly-contest-407/problems/minimum-operations-to-make-array-equal-to-target/

题意

模拟，差分数组

思路

1. 假设将两个数组变为相同，此时我们分别统计哪些数据需要递增，哪些数据需要递减，此时形成一些波峰，由于每次操作只能加$1$ 或者 减 $1$ ，此时我们尽可能使得数 $x$ 变为数 $y$ 的操作次数均为 $|x-y|$, 这个贪心算法证明还是挺难的，但是我们很容易计算出来。只需要计算上升沿的所有数字之和即可。
2. 差分数组的思想比较难想，但是整体思路还是可以的。
3. 复杂度分析：

• 时间复杂度：$O((m + n) \log (m + n)$，其中 $m,n$ 表示给的数；
• 空间复杂度：$O(m + n)$，其中 $m,n$ 表示给的数；

代码

class Solution:
    def minimumOperations(self, nums: List[int], target: List[int]) -> int:
        diff = [x - y for x, y in zip(nums, target)]
        def get(arr : List[int]) -> int:
            pre = 0
            ret = 0
            for x in arr:
                if x >= pre:
                    ret += x - pre
                pre = x
                
            return ret 

        res, i = 0, 0
        while i < len(nums):
            arr = []
            while i < len(nums) and diff[i] > 0:
                arr.append(diff[i])
                i += 1
            res += get(arr)
            arr = []
            while i < len(nums) and diff[i] <= 0:
                arr.append(-diff[i])
                i += 1
            res += get(arr)
        
        return res

欢迎关注和打赏，感谢支持！

• 关注我的博客: https://mike-box.github.io/

• 关注我的知乎：https://www.zhihu.com/people/da-hua-niu

• 关注我的微信公众号: 哪些奋斗者