leetcode contest 375

本周周赛全部都是比较水的题目，基本上都是简单题目。

100143. 统计已测试设备

给你一个长度为 n 、下标从 0 开始的整数数组 batteryPercentages ，表示 n 个设备的电池百分比。

你的任务是按照顺序测试每个设备 i，执行以下测试操作：

• 增加 已测试设备的计数。

• 将下标在 [i + 1, n - 1] 的所有设备的电池百分比减少 1，确保它们的电池百分比 不会低于 0 ，即 batteryPercentages[j] = max(0, batteryPercentages[j] - 1)。

• 移动到下一个设备。

• 否则，移动到下一个设备而不执行任何测试。

返回一个整数，表示按顺序执行测试操作后 已测试设备 的数量。

示例 1：

输入：batteryPercentages = [1,1,2,1,3]
输出：3
解释：按顺序从设备 0 开始执行测试操作：
在设备 0 上，batteryPercentages[0] > 0 ，现在有 1 个已测试设备，batteryPercentages 变为 [1,0,1,0,2] 。
在设备 1 上，batteryPercentages[1] == 0 ，移动到下一个设备而不进行测试。
在设备 2 上，batteryPercentages[2] > 0 ，现在有 2 个已测试设备，batteryPercentages 变为 [1,0,1,0,1] 。
在设备 3 上，batteryPercentages[3] == 0 ，移动到下一个设备而不进行测试。
在设备 4 上，batteryPercentages[4] > 0 ，现在有 3 个已测试设备，batteryPercentages 保持不变。
因此，答案是 3 。

示例 2：

输入：batteryPercentages = [0,1,2]
输出：2
解释：按顺序从设备 0 开始执行测试操作：
在设备 0 上，batteryPercentages[0] == 0 ，移动到下一个设备而不进行测试。
在设备 1 上，batteryPercentages[1] > 0 ，现在有 1 个已测试设备，batteryPercentages 变为 [0,1,1] 。
在设备 2 上，batteryPercentages[2] > 0 ，现在有 2 个已测试设备，batteryPercentages 保持不变。
因此，答案是 2 。

提示：

• 1 <= n == batteryPercentages.length <= 100
• 0 <= batteryPercentages[i] <= 100

地址

https://leetcode.cn/contest/weekly-contest-375/problems/count-tested-devices-after-test-operations/

题意

模拟

思路

1. 直接模拟即可， $del$ 表示需要删除的次数，如果 $x$ 小于等于当前需要删除的次数，则次数 $x$ 已经变为 $0$ ,不需要再删除，否则后续的数组还需要再删除一次。
2. 复杂度分析：

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

代码

class Solution:
    def countTestedDevices(self, batteryPercentages: List[int]) -> int:
        dec = 0
        for x in batteryPercentages:
            if x > dec:
                dec += 1
        return dec

100155. 双模幂运算

给你一个下标从 0 开始的二维数组 variables ，其中 variables[i] = [ai, bi, ci, mi]，以及一个整数 target 。

如果满足以下公式，则下标 i 是 好下标：

• 0 <= i < variables.length
• ((aibi % 10)ci) % mi == target

返回一个由 好下标 组成的数组，顺序不限 。

示例 1：

输入：variables = [[2,3,3,10],[3,3,3,1],[6,1,1,4]], target = 2
输出：[0,2]
解释：对于 variables 数组中的每个下标 i ：
1) 对于下标 0 ，variables[0] = [2,3,3,10] ，(23 % 10)3 % 10 = 2 。
2) 对于下标 1 ，variables[1] = [3,3,3,1] ，(33 % 10)3 % 1 = 0 。
3) 对于下标 2 ，variables[2] = [6,1,1,4] ，(61 % 10)1 % 4 = 2 。
因此，返回 [0,2] 作为答案。

示例 2：

输入：variables = [[39,3,1000,1000]], target = 17
输出：[]
解释：对于 variables 数组中的每个下标 i ：
1) 对于下标 0 ，variables[0] = [39,3,1000,1000] ，(393 % 10)1000 % 1000 = 1 。
因此，返回 [] 作为答案。

提示：

• 1 <= variables.length <= 100
• variables[i] == [ai, bi, ci, mi]
• 1 <= ai, bi, ci, mi <= 103
• 0 <= target <= 103

地址

https://leetcode.cn/contest/weekly-contest-375/problems/double-modular-exponentiation/

题意

二分快速幂

思路

1. 题目本身比较简单，主要是掌握二分快速幂的方法即可，题目就非常简单。
2. 复杂度分析：

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

代码

class Solution:
    def getGoodIndices(self, variables: List[List[int]], target: int) -> List[int]:
        res = []
        for i, (a, b, c, m) in enumerate(variables):
            if pow(pow(a, b, 10), c, m) == target:
                res.append(i)
        return res

100137. 统计最大元素出现至少 K 次的子数组

给你一个整数数组 nums 和一个 正整数 k 。

请你统计有多少满足 「 nums 中的 最大 元素」至少出现 k 次的子数组，并返回满足这一条件的子数组的数目。

子数组是数组中的一个连续元素序列。

示例 1：

输入：nums = [1,3,2,3,3], k = 2
输出：6
解释：包含元素 3 至少 2 次的子数组为：[1,3,2,3]、[1,3,2,3,3]、[3,2,3]、[3,2,3,3]、[2,3,3] 和 [3,3] 。

示例 2：

输入：nums = [1,4,2,1], k = 3
输出：0
解释：没有子数组包含元素 4 至少 3 次。

提示：

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

地址

https://leetcode.cn/contest/weekly-contest-375/problems/count-subarrays-where-max-element-appears-at-least-k-times/

题意

动态规划

思路

1. 题目要求数组中最大的元素出现的次数不多于 $k$，统计以当前 $i$ 为结尾的元素构成合法的数组的数目，此时我们只需要统计当前所有构成合法的最大长度为 $l$ ，则此时可以构成的合法的字符串的数目为 $l$ 个，我们依次统计即可。

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

代码

class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        val, res = max(nums), 0
        arr = []
        for i, x in enumerate(nums):
            if x == val:
                arr.append(i)
            if len(arr) >= k:
                res += arr[len(arr) - k] + 1
        return res

100136. 统计好分割方案的数目

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

将数组分割成一个或多个 连续 子数组，如果不存在包含了相同数字的两个子数组，则认为是一种 好分割方案 。

返回 nums 的 好分割方案 的 数目。

由于答案可能很大，请返回答案对 109 + 7 取余 的结果。

示例 1：

输入：nums = [1,2,3,4]
输出：8
解释：有 8 种 好分割方案 ：([1], [2], [3], [4]), ([1], [2], [3,4]), ([1], [2,3], [4]), ([1], [2,3,4]), ([1,2], [3], [4]), ([1,2], [3,4]), ([1,2,3], [4]) 和 ([1,2,3,4]) 。

示例 2：

输入：nums = [1,1,1,1]
输出：1
解释：唯一的 好分割方案 是：([1,1,1,1]) 。

示例 3：

输入：nums = [1,2,1,3]
输出：2
解释：有 2 种 好分割方案 ：([1,2,1], [3]) 和 ([1,2,1,3]) 。

提示：

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

地址

https://leetcode.cn/contest/weekly-contest-375/problems/count-the-number-of-good-partitions/

题意

滑动窗口

思路

1. 根据题目可以知道，所有相同的元素必须要要在同一个分组内，假设当前的分组中的元素为 $[a_0,a_1,a_2, \cdots,a_{i}]$, 则此时所有相同的 $a_0$ 都必须在数组中，$a_1$ 都必须在数组中，因此我们依次尝试将所有含有相同元素放在同一个分组中，此时我们枚举所有合法的分组为 $x$ 个，此时根据组合数学中的隔板法，在 $x-1$ 个位置中放置 $m$ 个隔板，此时可以构成的方法数为 $2^{x-1}$ 个。
2. 复杂度分析:

• 时间复杂度：$O(n \log n)$，其中 $n$ 表示数组的长度;
• 空间复杂度：$O(n)$，其中 $n$ 表示数组的长度;

代码

class Solution:
    def numberOfGoodPartitions(self, nums: List[int]) -> int:
        n = len(nums)
        cnt = Counter()
        for i, x in enumerate(nums):
            cnt[x] = i
        i, count = 0, 0
        while i < n:
            last = cnt[nums[i]]
            j = i
            while j < last:
                last = max(last, cnt[nums[j]]);
                j += 1
            count += 1
            i = j + 1
        return pow(2, count - 1, 10**9 + 7)

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

• 关注我的博客: http://whistle-wind.com/
• 关注我的知乎：https://www.zhihu.com/people/da-hua-niu
• 关注我的微信公众号: 公务程序猿