且听疯吟

leetcode contest 382

2024-02-12

leetcode contest 382

t4 是个非常不错的题目，非常值得思考的题目。

3019. 按键变更的次数

给你一个下标从 0 开始的字符串 s ，该字符串由用户输入。按键变更的定义是：使用与上次使用的按键不同的键。例如 s = "ab" 表示按键变更一次，而 s = "bBBb" 不存在按键变更。

返回用户输入过程中按键变更的次数。

注意：shift 或 caps lock 等修饰键不计入按键变更，也就是说，如果用户先输入字母 'a' 然后输入字母 'A' ，不算作按键变更。

示例 1：

输入：s = "aAbBcC"
输出：2
解释： 
从 s[0] = 'a' 到 s[1] = 'A'，不存在按键变更，因为不计入 caps lock 或 shift 。
从 s[1] = 'A' 到 s[2] = 'b'，按键变更。
从 s[2] = 'b' 到 s[3] = 'B'，不存在按键变更，因为不计入 caps lock 或 shift 。
从 s[3] = 'B' 到 s[4] = 'c'，按键变更。
从 s[4] = 'c' 到 s[5] = 'C'，不存在按键变更，因为不计入 caps lock 或 shift 。

示例 2：

输入：s = "AaAaAaaA"
输出：0
解释： 不存在按键变更，因为这个过程中只按下字母 'a' 和 'A' ，不需要进行按键变更。

提示：

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

地址

https://leetcode.cn/contest/weekly-contest-382/problems/number-of-changing-keys/

题意

直接模拟即可

思路

  1. 直接检测相邻的两个字符的小写形式是否相等即可。
  2. 复杂度分析：
  • 时间复杂度：$O(n)$，其中 $n$ 表示给定字符串的长度。
  • 空间复杂度：$O(1)$。

代码

class Solution:
    def countKeyChanges(self, s: str) -> int:
        s = s.lower()
        res = 0
        for i in range(1, len(s)):
            if s[i] != s[i - 1]:
                res += 1
        return res

3020. 子集中元素的最大数量

给你一个 正整数 数组 nums 。

你需要从数组中选出一个满足下述条件的子集：

  • 你可以将选中的元素放置在一个下标从 0 开始的数组中，并使其遵循以下模式：[x, x2, x4, ..., xk/2, xk, xk/2, ..., x4, x2, x]（注意，k 可以是任何 非负 的 2 的幂）。例如，[2, 4, 16, 4, 2] 和 [3, 9, 3] 都符合这一模式，而 [2, 4, 8, 4, 2] 则不符合。

返回满足这些条件的子集中，元素数量的 最大值 。

示例 1：

输入：nums = [5,4,1,2,2]
输出：3
解释：选择子集 {4,2,2} ，将其放在数组 [2,4,2] 中，它遵循该模式，且 22 == 4 。因此答案是 3 。

示例 2：

输入：nums = [1,3,2,4]
输出：1
解释：选择子集 {1}，将其放在数组 [1] 中，它遵循该模式。因此答案是 1 。注意我们也可以选择子集 {2} 、{4} 或 {3} ，可能存在多个子集都能得到相同的答案。

提示：

  • 2 <= nums.length <= 105
  • 1 <= nums[i] <= 109

地址

https://leetcode.cn/contest/weekly-contest-382/problems/find-the-maximum-number-of-elements-in-subset/

题意

模拟，哈希表

思路

  1. 我们每次尝试以每个元素 $x$ 为起点，分别计算 $x^2,x^4,x^6,\cdots$ 是否在数组中即可，由于整数的最大值为 $2^{32}-1$，所以最多会尝试 $\log_x^U$ 。
  2. 复杂度分析：
  • 时间复杂度：$O(n \log U)$, $n$ 表示给定数组的长度，$U$ 表示整数的最大值；
  • 空间复杂度：$O(1)$；

代码

class Solution:
    def maximumLength(self, nums: List[int]) -> int:
        nums.sort()
        freq = Counter(nums)
        res = 1
        for k, v in freq.items():
            if k == 1:
                res = max(res, v - 1 + (v & 1))
            elif v > 1:
                cnt = 1
                now = k * k
                while now in freq:
                    cnt += 1
                    if freq[now] > 1:
                        now = now * now
                    else:
                        break
                res = max(res, 2 * cnt - 1)
        return res

3021. Alice 和 Bob 玩鲜花游戏

Alice 和 Bob 在一个长满鲜花的环形草地玩一个回合制游戏。环形的草地上有一些鲜花，Alice 到 Bob 之间顺时针有 x 朵鲜花，逆时针有 y 朵鲜花。

游戏过程如下：

  1. Alice 先行动。
  2. 每一次行动中，当前玩家必须选择顺时针或者逆时针，然后在这个方向上摘一朵鲜花。
  3. 一次行动结束后，如果所有鲜花都被摘完了，那么 当前 玩家抓住对手并赢得游戏的胜利。

给你两个整数 n 和 m ，你的任务是求出满足以下条件的所有 (x, y) 对：

  • 按照上述规则，Alice 必须赢得游戏。
  • Alice 顺时针方向上的鲜花数目 x 必须在区间 [1,n] 之间。
  • Alice 逆时针方向上的鲜花数目 y 必须在区间 [1,m] 之间。

请你返回满足题目描述的数对 (x, y) 的数目。

示例 1：

输入：n = 3, m = 2
输出：3
解释：以下数对满足题目要求：(1,2) ，(3,2) ，(2,1) 。

示例 2：

输入：n = 1, m = 1
输出：0
解释：没有数对满足题目要求。

提示：

  • 1 <= n, m <= 105

地址

https://leetcode.cn/contest/weekly-contest-382/problems/alice-and-bob-playing-flower-game/

题意

构造题目

思路

  1. 感觉就是个简单题目，特别没有意思，如果 $m+n$ 为奇数则后手的一定会输掉游戏，否则先手的输掉游戏，本质就是求有多少个组合的和为奇数。

  2. 复杂度分析：

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

代码

class Solution:
    def flowerGame(self, n: int, m: int) -> int:
        return m * n // 2

3022. 给定操作次数内使剩余元素的或值最小

给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。

一次操作中，你可以选择 nums 中满足 0 <= i < nums.length - 1 的一个下标 i ，并将 nums[i] 和 nums[i + 1] 替换为数字 nums[i] & nums[i + 1] ，其中 & 表示按位 AND 操作。

请你返回 至多 k 次操作以内，使 nums 中所有剩余元素按位 OR 结果的 最小值 。

示例 1：

输入：nums = [3,5,3,2,7], k = 2
输出：3
解释：执行以下操作：
1. 将 nums[0] 和 nums[1] 替换为 (nums[0] & nums[1]) ，得到 nums 为 [1,3,2,7] 。
2. 将 nums[2] 和 nums[3] 替换为 (nums[2] & nums[3]) ，得到 nums 为 [1,3,2] 。
最终数组的按位或值为 3 。
3 是 k 次操作以内，可以得到的剩余元素的最小按位或值。

示例 2：

输入：nums = [7,3,15,14,2,8], k = 4
输出：2
解释：执行以下操作：
1. 将 nums[0] 和 nums[1] 替换为 (nums[0] & nums[1]) ，得到 nums 为 [3,15,14,2,8] 。
2. 将 nums[0] 和 nums[1] 替换为 (nums[0] & nums[1]) ，得到 nums 为 [3,14,2,8] 。
3. 将 nums[0] 和 nums[1] 替换为 (nums[0] & nums[1]) ，得到 nums 为 [2,2,8] 。
4. 将 nums[1] 和 nums[2] 替换为 (nums[1] & nums[2]) ，得到 nums 为 [2,0] 。
最终数组的按位或值为 2 。
2 是 k 次操作以内，可以得到的剩余元素的最小按位或值。

示例 3：

输入：nums = [10,7,10,3,9,14,9,4], k = 1
输出：15
解释：不执行任何操作，nums 的按位或值为 15 。
15 是 k 次操作以内，可以得到的剩余元素的最小按位或值。

提示：

  • 1 <= nums.length <= 105
  • 0 <= nums[i] < 230
  • 0 <= k < nums.length

地址

https://leetcode.cn/contest/weekly-contest-382/problems/minimize-or-of-remaining-elements-using-operations/

题意

贪心

思路

  1. 确实是个难度比较大构造题目，关键在于如何理解贪心算法。需要遵循以下几个原则：
    • 由于合并的次数有限，首先我们应该尽可能的去掉最高位的 $1$，然后再考虑去掉低位 $1$；
    • 假设某一位上如果含有的 $1$ 的个数大于 $k$，此时无论我们如何合并都无法使得该位的 $1$ 全部变为 $0$，此时该位最后一定的为 $1$；
    • 我们在合并低位上，如果合并低位同时可以让高位也变为 $0$,则此时该位最后的结果也可以是 $0$;
    • 遵循上述的贪心规则，依次进行合并即可，还是蛮有思考性质的一个题目。
  2. 复杂度分析：
  • 时间复杂度：$O(n \log U)$, $n$ 表示给定的数组的长度, $U$ 表示给定数组的最大值；
  • 空间复杂度：$O(1)$；

代码

class Solution:
    def minOrAfterOperations(self, nums: List[int], k: int) -> int:
        ans = 0
        for i in range(29, -1, -1):
            cur = ans | (1 << i)
            val, cnt = -1, len(nums)
            for v in nums:
                val &= v & cur
                if val == 0:
                    cnt -= 1
                    val = -1
            if cnt <= k:
                ans = cur
        return (1 << 30) - 1 - ans

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

Tags: 题解 力扣周赛赛
← leetcode contest 381 leetcode contest 385 →

扫描二维码，分享此文章