leetcode biweekly contest 121

参加了一半就睡觉了，初步看了下基本上都是模版题目，实在太困，直接就休息了。

100157. 大于等于顺序前缀和的最小缺失整数

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

如果一个前缀 nums[0..i] 满足对于 1 <= j <= i 的所有元素都有 nums[j] = nums[j - 1] + 1 ，那么我们称这个前缀是一个 顺序前缀 。特殊情况是，只包含 nums[0] 的前缀也是一个 顺序前缀 。

请你返回 nums 中没有出现过的 最小 整数 x ，满足 x 大于等于 最长 顺序前缀的和。

示例 1：

输入：nums = [1,2,3,2,5]
输出：6
解释：nums 的最长顺序前缀是 [1,2,3] ，和为 6 ，6 不在数组中，所以 6 是大于等于最长顺序前缀和的最小整数。

示例 2：

输入：nums = [3,4,5,1,12,14,13]
输出：15
解释：nums 的最长顺序前缀是 [3,4,5] ，和为 12 ，12、13 和 14 都在数组中，但 15 不在，所以 15 是大于等于最长顺序前缀和的最小整数。

提示：

• 1 <= nums.length <= 50
• 1 <= nums[i] <= 50

地址

https://leetcode.cn/contest/biweekly-contest-121/problems/smallest-missing-integer-greater-than-sequential-prefix-sum/

题意

直接模拟即可

思路

1. 直接找数组中最长的顺序前缀，并求和。然后在数组中查找是否存在第一个大于 $sum$ 且不在数组中的元素
2. 复杂度分析：

• 时间复杂度：$O(n)$，其中 $n$ 表示给定数组的长度。
• 空间复杂度：$O(n)$。

代码

class Solution:
    def missingInteger(self, nums: List[int]) -> int:
        cnt = set(nums)
        psum = nums[0]
        for i in range(1, len(nums)):
            if nums[i] - nums[i - 1] == 1:
                psum += nums[i]
            else:
                break
        
        x = psum
        while x in nums:
            x += 1
        return x

100168. 使数组异或和等于 K 的最少操作次数

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

你可以对数组执行以下操作 任意次 ：

• 选择数组里的 任意 一个元素，并将它的 二进制 表示 翻转 一个数位，翻转数位表示将 0 变成 1 或者将 1 变成 0 。

你的目标是让数组里 所有 元素的按位异或和得到 k ，请你返回达成这一目标的 最少 操作次数。

注意，你也可以将一个数的前导 0 翻转。比方说，数字 (101)2 翻转第四个数位，得到 (1101)2 。

示例 1：

输入：nums = [2,1,3,4], k = 1
输出：2
解释：我们可以执行以下操作：
- 选择下标为 2 的元素，也就是 3 == (011)2 ，我们翻转第一个数位得到 (010)2 == 2 。数组变为 [2,1,2,4] 。
- 选择下标为 0 的元素，也就是 2 == (010)2 ，我们翻转第三个数位得到 (110)2 == 6 。数组变为 [6,1,2,4] 。
最终数组的所有元素异或和为 (6 XOR 1 XOR 2 XOR 4) == 1 == k 。
无法用少于 2 次操作得到异或和等于 k 。

示例 2：

输入：nums = [2,0,2,0], k = 0
输出：0
解释：数组所有元素的异或和为 (2 XOR 0 XOR 2 XOR 0) == 0 == k 。所以不需要进行任何操作。

提示：

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

地址

https://leetcode.cn/contest/biweekly-contest-121/problems/minimum-number-of-operations-to-make-array-xor-equal-to-k/

题意

二进制位运算

思路

1. 根据题目可以分析，我们需要将数组中所有元素进行位异或后与给定的数相同，此时我们分别计算每一位即可：
   • 第 $i$ 位上的数字为 $0$:
   • 第 $i$ 位上的数字为 $1$:
2. 复杂度分析：

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

代码

class Solution:
    def minOperations(self, nums: List[int], k: int) -> int:
        n = len(nums)
        ans = 0
        for i in range(21):
            cnt = sum(1 for x in nums if x & (1 << i) != 0)
            if k & (1 << i) != 0:
                if cnt & 1 == 0:
                    ans += 1
            else:
                if cnt & 1 != 0:
                    ans += 1
        return ans

100159. 使 X 和 Y 相等的最少操作次数

给你两个正整数 x 和 y 。

一次操作中，你可以执行以下四种操作之一：

1. 如果 x 是 11 的倍数，将 x 除以 11 。
2. 如果 x 是 5 的倍数，将 x 除以 5 。
3. 将 x 减 1 。
4. 将 x 加 1 。

请你返回让 x 和 y 相等的 最少 操作次数。

示例 1：

输入：x = 26, y = 1
输出：3
解释：我们可以通过以下操作将 26 变为 1 ：
1. 将 x 减 1
2. 将 x 除以 5
3. 将 x 除以 5
将 26 变为 1 最少需要 3 次操作。

示例 2：

输入：x = 54, y = 2
输出：4
解释：我们可以通过以下操作将 54 变为 2 ：
1. 将 x 加 1
2. 将 x 除以 11
3. 将 x 除以 5
4. 将 x 加 1
将 54 变为 2 最少需要 4 次操作。

示例 3：

输入：x = 25, y = 30
输出：5
解释：我们可以通过以下操作将 25 变为 30 ：
1. 将 x 加 1
2. 将 x 加 1
3. 将 x 加 1
4. 将 x 加 1
5. 将 x 加 1
将 25 变为 30 最少需要 5 次操作。

提示：

• 1 <= x, y <= 104

地址

https://leetcode.cn/contest/biweekly-contest-121/problems/minimum-number-of-operations-to-make-x-and-y-equal/

题意

动态规划 或 BFS

思路

1. 首先我们知道变换次数的限制即为 $x - y$，由于 $x$ 每次除以 $5$ 或者 $11$ 时都会缩小，因此当 $x < y$ 时，我们只能增加 $x$，此时需要的次数为 $y - x$；
   • 当 $x > y$ 时,由于变换次数最多为 $x - y$ 次，因此我们可以采用 $BFS$ 遍历所有可能的状态与次数直接暴力遍历所有可能即可；
2. 记忆化搜索，由于根据结论可以知道 $x < y$ 时直接返回 $y - x$，因此我们无论变大或者变小，总是优先往 $5$ 或者 $11$ 的倍数上凑齐，因此每次变换时可以有以下四种走向：
   • 向上加法直到 $x$ 是 $5$ 或者 $11$ 的倍数；
   • 向下减法直到 $x$ 是 $5$ 或者 $11$ 的倍数；
   • 每次只能在这四种走向中选择一种即可；
3. 复杂度分析：

• 时间复杂度：$O(\log^2\frac{x}{y})$，其中 $x,y$ 表示给定的数字。
• 空间复杂度：$O(\log^2\frac{x}{y})$，其中 $x,y$ 表示给定的数字。

代码

class Solution:
    def minimumOperationsToMakeEqual(self, x: int, y: int) -> int:
        @cache
        def dp(x):
            if x <= y:
                return y - x
            res = x - y
            res = min(res, dp(x // 11) + x % 11 + 1)
            res = min(res, dp(x // 11 + 1) + 11 - x % 11 + 1)
            res = min(res, dp(x // 5) + x % 5 + 1)
            res = min(res, dp(x // 5 + 1)  + 5 - x % 5 + 1)
            return res
        return dp(x)
    
    
class Solution:
    def minimumOperationsToMakeEqual(self, x: int, y: int) -> int:
        if x <= y:
            return y - x

        vis = set()
        q = []
        q.append(x)
        vis.add(x)
        step = 0

        while len(q) > 0:
            tmp = []
            for x in q:
                if x == y:
                    return step
                if x % 5 == 0 and x // 5 not in vis:
                    tmp.append(x // 5)
                    vis.add(x // 5)
                if x % 11 == 0 and x // 11 not in vis:
                    tmp.append(x // 11)
                    vis.add(x // 11)
                if x - 1 not in vis:
                    tmp.append(x - 1)
                    vis.add(x - 1)
                if x + 1 not in vis:
                    tmp.append(x + 1)
                    vis.add(x + 1)
            q = tmp
            step += 1
        return -1

100163. 统计强大整数的数目

给你三个整数 start ，finish 和 limit 。同时给你一个下标从 0 开始的字符串 s ，表示一个 正 整数。

如果一个 正 整数 x 末尾部分是 s （换句话说，s 是 x 的 后缀），且 x 中的每个数位至多是 limit ，那么我们称 x 是 强大的 。

请你返回区间 [start..finish] 内强大整数的 总数目 。

如果一个字符串 x 是 y 中某个下标开始（包括 0 ），到下标为 y.length - 1 结束的子字符串，那么我们称 x 是 y 的一个后缀。比方说，25 是 5125 的一个后缀，但不是 512 的后缀。

示例 1：

输入：start = 1, finish = 6000, limit = 4, s = "124"
输出：5
解释：区间 [1..6000] 内的强大数字为 124 ，1124 ，2124 ，3124 和 4124 。这些整数的各个数位都 <= 4 且 "124" 是它们的后缀。注意 5124 不是强大整数，因为第一个数位 5 大于 4 。
这个区间内总共只有这 5 个强大整数。

示例 2：

输入：start = 15, finish = 215, limit = 6, s = "10"
输出：2
解释：区间 [15..215] 内的强大整数为 110 和 210 。这些整数的各个数位都 <= 6 且 "10" 是它们的后缀。
这个区间总共只有这 2 个强大整数。

示例 3：

输入：start = 1000, finish = 2000, limit = 4, s = "3000"
输出：0
解释：区间 [1000..2000] 内的整数都小于 3000 ，所以 "3000" 不可能是这个区间内任何整数的后缀。

提示：

• 1 <= start <= finish <= 1015
• 1 <= limit <= 9
• 1 <= s.length <= floor(log10(finish)) + 1
• s 数位中每个数字都小于等于 limit 。
• s 不包含任何前导 0 。

地址

https://leetcode.cn/contest/biweekly-contest-121/problems/count-the-number-of-powerful-integers/

题意

数位 dp

思路

1. 典型的数位 $dp$, 感觉没什么新意的题目，但是确实不太好写的数位 dp,非常容易出错。由于存在固定后缀，所以计算最后几位时，需要注意到最后几位与后缀保持不变，不过太过于模板化的题目，没有什么意思。

2. 复杂度分析:

• 时间复杂度：$O(n \times D)$，其中 $n = \log finish$;
• 空间复杂度：$O(n \times D)$，其中 $n = \log finish$;

代码

class Solution:
    def numberOfPowerfulInt(self, start: int, finish: int, limit: int, s: str) -> int:
        @cache
        def dfs(i, is_limit, upper):
            if upper < int(s):
                return 0
            if i == len(str(upper)):
                return 1
            t = str(upper)
            diff = len(t) - len(s)
            up = 9
            if is_limit:
                up = int(t[i])
            res = 0
            if i < diff:
                for d in range(min(up, limit) + 1):
                    res += dfs(i + 1, is_limit and d == up, upper)
            else:
                x = int(s[i - diff])
                if x <= min(limit, up):
                    res = dfs(i + 1, is_limit and x == up, upper)
            return res
        return dfs(0, True, finish) - dfs(0, True, start - 1)

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

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

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