LeetCode-375

比较简单的一场，最高rating不到2000

Q1 统计已测试设备

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

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

    • 如果

      1
      batteryPercentages[i]

      大于

      1
      0

      ：

      • 增加 已测试设备的计数。
      • 将下标在 [i + 1, n - 1] 的所有设备的电池百分比减少 1，确保它们的电池百分比 不会低于 0 ，即 batteryPercentages[j] = max(0, batteryPercentages[j] - 1)。
      • 移动到下一个设备。

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

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

    示例 1：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    输入：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：

    1
    2
    3
    4
    5
    6
    7
    输入：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

简单题，由于数据范围只有100，双重for循环即可，数据范围如果变大可以使用前缀和优化，假设s[i]表示小于i的下标的和(大于1都看做1)，若nums[i] > s[i]则可以测试。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    fun countTestedDevices(batteryPercentages: IntArray): Int {
        val n = batteryPercentages.size
        var ans = 0
        for (i in 0..<n) {
            if (batteryPercentages[i] > 0) {
                ans++
                for (j in i + 1..<n) {
                    batteryPercentages[j] = max(0, batteryPercentages[j] - 1)
                }
            }
        }
        return ans
    }
}

Q2 双模幂运算

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

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

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

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

示例 1：

1
2
3
4
5
6
7
输入：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：

1
2
3
4
5
输入：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

观察数据范围，不可以暴力，那就快速幂了，需要注意到括号内的都是同余的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    fun getGoodIndices(variables: Array<IntArray>, target: Int): List<Int> {
        val filter = variables.indices.filter { i ->
            val (a, b, c, m) = variables[i]
            qmi(qmi(a, b, 10), c, m) == target
        }
        return filter
    }


    private fun qmi(a: Int, b: Int, mod: Int): Int {
        var ans = 1
        var bb = b
        var aa = a
        while (bb != 0) {
            if ((bb and 1) == 1) {
                ans = ans.times(aa).rem(mod)
            }
            aa = aa.times(aa).rem(mod)
            bb = bb shr 1
        }
        return ans.rem(mod)
    }
}

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

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

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

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

    示例 1：

    1
    2
    3
    输入：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：

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

    提示：

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

滑窗(双指针)，二分都可以做，需要一点小小的灵性。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//滑窗
class Solution {
    fun countSubarrays(nums: IntArray, k: Int): Long {
        val max = nums.max()
        var l = 0
        var ans: Long = 0
        var cnt = 0
        for (x in nums) {
            if (x == max) cnt++
            while (cnt == k) {
                if (nums[l++] == max) cnt--  
            }
            ans += l  //反过来想使用滑窗就很好写了
        }
        return ans
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
//二分
class Solution {
    public long countSubarrays(int[] nums, int k) {
        int max = Arrays.stream(nums).max().getAsInt();
        int n = nums.length;
        int[] f = new int[n];
        f[0] = nums[0] == max ? 1 : 0;
        for (int i = 1; i < n; i++) {
            f[i] = f[i - 1] + (nums[i] == max ? 1 : 0);
        }
        long ans = 0L;
        for (int i = 0; i < n; i++) {
            int l = i, r = n - 1;
            while (l < r) {
                int mid = l + r >> 1;
                if (check(i, mid, f, k)) r = mid;
                else l = mid + 1;
            }
            if (check(i, l, f, k)) ans += n - l;  //其实从二分的过程种很容易联想到双指针
        }
        return ans;
    }

    boolean check(int l, int r, int[] f, int k) {
        if (l == 0) return f[r] >= k;
        return f[r] - f[l - 1] >= k;
    }
}

Q4 统计好分割方案的数目

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

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

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

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

    示例 1：

    1
    2
    3
    输入：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：

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

    示例 3：

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

    提示：

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

本题是一道不怎么难的困难题，对于这种题，首先想到区间DP，但看了看数据范围，就可以排除这个做法了。对于本题，我们可以将整个数组分成若干个子数组，子数组中的所有数当且仅当在该数组中出现，分割的方法就是使用一个map记录所有数最后出现的下标，然后遍历就可以分割了。假设分割成n块，那答案是多少呢?

假设数组 nums 包含 n 个元素，则我们可以通过以下步骤来证明好分割方案数量为 2n−12^n-1：

  1. 当 n=1 时，只有一个元素，只有一种好分割方案：([1])。这时 21−1=12^1-1=1，符合结论。

  2. 假设当 n=k 时结论成立，即 nums 包含 k 个元素时好分割方案数量为 2k−12^k-1。

  3. 考虑 n=k+1 的情况，我们可以将 nums 划分为两部分：左侧包含前 k 个元素，右侧包含最后一个元素。那么好分割方案要么只在左侧，要么包含右侧的最后一个元素。

    • 只在左侧的好分割方案数量为 2k−12^k-1（根据假设）。
    • 包含右侧的最后一个元素的好分割方案数量也为 2k−12^k-1（因为对于左侧的每种好分割方案，都可以选择是否包含右侧的最后一个元素）。

    因此，n=k+1n=k+1 时好分割方案的数量为 2∗(2k−1)=2(k+1)−12*(2^k-1)=2^(k+1)-1，符合结论。

根据上述归纳法证明，我们可以得出结论：对于包含 n 个元素的数组 nums，它的好分割方案数量为 2n−12^n-1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {

    val mod: Long = (1e9 + 7).toLong()

    fun numberOfGoodPartitions(nums: IntArray): Int {
        val map = hashMapOf<Int, Int>()
        val n = nums.size
        for (i in 0..<n) map[nums[i]] = i
        var ans = 0L
        var i = 0
        while (i < n) {
            var idx = map[nums[i]] ?: 0
            while (i < idx) {
                i++
                idx = maxOf(idx, map[nums[i]]!!)
            }
            ans++
            i = idx + 1
        }
        return qmi((ans - 1).toLong()).toInt()
    }

    private fun qmi(b: Long): Long {
        var ans = 1L
        var a = 2L
        var bb = b
        while (bb != 0L) {
            if (bb and 1L == 1L) {
                ans = ans * a % mod
            }
            a = a * a % mod
            bb = bb shr 1
        }
        return ans % mod
    }
}
算法
#leetcode
LeetCode-375
http://example.com/2023/12/31/LeetCode-375/
作者
ykexc
发布于
2023年12月31日
许可协议