算法leetcode

leetcode第375场周赛：模下快速幂专场

字数统计: 3.2k字   |   阅读时长: 14分
,

摘要: 本文是 leetcode 第 375 周赛的记录。主要涉及的算法包括惰性更新、模下快速幂、组合数学、区间合并

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

总览

本周进行了 leetcode 第 375 场周赛，本场比赛没有赞助公司，奖品力扣周边，具体如下：

  • 排名第 1 - 10 名可获力扣 BigO 笔记本 x1 。
  • 排名第 75、137、375、1024、1337、2048 名可获盲盒奖励 x1 。

本次比赛的发挥自我感觉还是不错的，1 个小时整 4 个题都过了，不过排名还是比较一般 (460/3518)，说明本场比赛的题难度不算大。不过需要一些推导以及问题规约的思想，把问题转化为已经解决过的经典问题，如果此前写过代码模板，则可以直接复制过来用。

其中第一题是比较简单的惰性更新；第二题是模下快速幂，只要把答案推导清楚了，可以复制模板解决；第三题是组合数学的问题，本题需要一些推导，把计数的对象推导清楚，实现上不难；

第四题是本场第二个可以直接套模板的题，而且套了两个，不过需要一些问题规约，首先规约到区间合并问题，可以直接套模板，然后要在合并后的若干区间上计数，计数结果经过推导后为 2 的高次幂的形式，继续调用模下快速幂即可解决。

各个题目涉及到的知识点汇总如下：

往期参加比赛的记录如下：

【连载】leetcode周赛

A 题

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

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

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

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

提示：

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

示例 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 。

算法：惰性更新

对于 batteryPercentages[i]，首先将此前积累的减一操作执行完，然后与零对比，如果大于 0，则减一操作次数加一。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int countTestedDevices(vector<int>& batteryPercentages) {
        int n = batteryPercentages.size();
        int diff = 0;
        int ans = 0;
        for(int i = 0; i < n; ++i)
        {
            if(batteryPercentages - ans > 0)
            {
                ans++;
            }
        }
        return ans;
    }
};

B 题

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

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

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

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

提示：

1
2
3
4
1 <= variables.length <= 100
variables[i] == [ai, bi, ci, mi]
1 <= ai, bi, ci, mi <= 1e3
0 <= target <= 1e3

示例 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 。
因此，返回 [] 作为答案。

算法：模下快速幂

对于每一组 $a_{i}, b_{i}, c_{i}, m_{i}$，我们首先求 $t = a_{i}^{b_{i}} \mod 10$，然后求 $t^{c_{i}} \mod m_{i}$，将结果与 $target$ 对比。

因此本题需要用到模下快速幂，函数接口如下：

1
int quickpower_mod(int a, int n, int mod)

如果有代码模板的话，则可以直接复制使用。

代码 (C++)

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
using ll = long long;

int quickpower_mod(int a, int n, int mod) // 处理不了n是负数
{
    int ans = 1;
    while(n)
    {
        if(n & 1)
            ans = ((ll)ans * a) % mod;
        a = (ll)a * a % mod;
        n >>= 1;
    }
    return ans % mod;
}

class Solution {
public:
    vector<int> getGoodIndices(vector<vector<int>>& variables, int target) {
        int n = variables.size();
        vector<int> result;
        for(int i = 0; i < n; ++i)
        {
            int ai = variables[i][0];
            int bi = variables[i][1];
            int ci = variables[i][2];
            int mi = variables[i][3];

            int t = quickpower_mod(ai, bi, 10);
            t = quickpower_mod(t, ci, mi);
            if(t == target)
                result.push_back(i);
        }
        return result;
    }
};

C 题

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

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

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

提示：

1
2
3
1 <= nums.length <= 1e5
1 <= nums[i] <= 1e6
1 <= k <= 1e5

示例 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 次。

算法：组合数学

首先遍历 $nums$，得到最大值 $MAX$，最大值的次数 $CNT$，并预处理出一个数组 $f$，$f[i]$ 表示第 $i$ 个 $MAX$ 在 $nums$ 中的下标。

因为子区间至少要包含 $k$ 个 $MAX$，因此子区间右端点肯定在 $f[k - 1]$ 及其右边。

因此在 $i = [k - 1, CNT - 1]$ 的范围枚举 $f[i]$，考察右端点为 $f[i] \sim f[i + 1] - 1$ 范围的合法子区间个数，也就是最右边的 $MAX$ 为 $nums[f[i]]$ 的合法子区间的个数，这里如果 $i + 1 = CNT$ 的话，那么右端点的范围是 $f[i] \sim n - 1$。将右端点的范围的长度记为 $left$。

而由于子区间至少包含 $k$ 个 $MAX$，所以只有 $0 \sim f[i - k + 1]$ 范围的左端点才是合法的，记该范围的长度为 $right$。因此 $f[i]$ 对答案的贡献为 $left \times right$。

代码 (C++)

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
using ll = long long;

class Solution {
public:
    ll countSubarrays(vector<int>& nums, int k) {
        int n = nums.size();
        int MAX = 0;
        for(int i = 0; i < n; ++i)
            MAX = max(MAX, nums[i]);
        vector<int> f;
        for(int i = 0; i < n; ++i)
            if(nums[i] == MAX)
                f.push_back(i);
        int CNT = f.size();
        ll ans = 0;
        for(int i = k - 1; i < CNT; ++i)
        {
            // 考察右端点为 f[i] ~ f[i + 1] - 1 的合法子区间个数，(若 i == CNT - 1 则右端点为 f[i] ~ n-1)
            // 0 ~ f[i - k + 1] 为起点合法
            // f[i - k + 1] + 1 ~ f[i + 1] - 1 为起点不合法
            ll right = (n - 1) - f[i] + 1;
            if(i < CNT - 1)
                right = f[i + 1] - f[i];
            ll left = f[i - k + 1] + 1;
            ans += left * right;
        }
        return ans;
    }
};

D 题

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

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

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

由于答案可能很大，请返回答案对 1e9 + 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
2
1 <= nums.length <= 1e5
1 <= nums[i] <= 1e9

算法：区间合并 + 模下快速幂

对于每个 $nums$ 中的数 $c$，记 $l$ 为 $nums$ 中最左边的 $c$ 的下标，$r$ 为 $nums$ 中最右边的 $c$ 的下标。这样 $c$ 就对应一个区间 $[l, r]$，分割区间的隔板不能放在该区间内。

而对于任意两个 $nums$ 中的数 $c_{1}, c_{2}$，其对应的区间为 $[l_{1}, r_{1}], [l_{2}, r_{2}]$，如果这两个区间有重叠，那么把这两个区间合并后的区间记为 $l, r$ 的话，在这个合并后的区间上，分割区间的隔板都是不能放的。

所以如果我们想考察隔板可以放在 $nums$ 的哪些位置上，首先需要将这些重叠的区间合并到一起，在合并后的若干区间之间是可以放隔板的范围。

因此问题第一步转化为了区间合并的问题，参考文章 区间合并，可以直接使用代码模板返回一个 vector<vector<int>> 形式的合并后的区间列表 merged，其长度 $k$ 就是合并后的区间个数，隔板可以在合并后的区间之间放，因此有 $k - 1$ 个放隔板的位置。

然后枚举隔板个数 $j = 0, 1, \cdots, k - 1$，分隔区间就是在 $k - 1$ 个隔板位中选出 $j$ 个隔板，将区间划分为 $j + 1$ 个子区间，方法数为 $\binom{k - 1}{j}$，因此最终答案为：

代码 (C++)

代码中 merge 和 quickpower_mod 分别为区间合并和模下快速幂的代码模板。

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
using ll = long long;
const int MOD = 1e9 + 7;

int quickpower_mod(int a, int n, int mod) // 处理不了n是负数
{
    int ans = 1;
    while(n)
    {
        if(n & 1)
            ans = ((ll)ans * a) % mod;
        a = (ll)a * a % mod;
        n >>= 1;
    }
    return ans % mod;
}

static bool compare(const vector<int>& interval1, const vector<int>& interval2)
{
    return interval1[0] < interval2[0];
}

vector<vector<int>> merge(vector<vector<int>>& intervals) {
    if(intervals.empty()) return vector<vector<int> >();
    int n = intervals.size();
    if(n == 1) return intervals;
    sort(intervals.begin(), intervals.end(), compare);
    vector<vector<int> > results;
    for(const auto& interval: intervals)
    {
        if(results.empty() || interval[0] > results.back()[1])
            results.push_back(interval);
        else
            results.back()[1] = max(results.back()[1], interval[1]);
    }
    return results;
}

class Solution {
public:
    int numberOfGoodPartitions(vector<int>& nums) {
        unordered_map<int, vector<int>> mapping;
        int n = nums.size();
        for(int i = 0; i < n; ++i)
        {
            int ci = nums[i];
            if(mapping.count(ci) == 0)
                mapping[ci] = {i, i};
            else
                mapping[ci][1] = i;
        }
        int m = mapping.size();
        vector<vector<int>> intervals(m, {-1, -1});
        int i = 0;
        for(auto &item: mapping)
        {
            int li = item.second[0];
            int ri = item.second[1];
            intervals[i][0] = li;
            intervals[i][1] = ri;
            i++;
        }
        vector<vector<int>> merged = merge(intervals);
        int k = merged.size();
        if(k == 1)
            return 1;
        // k > 1，k 个元素，k - 1 个隔板
        return quickpower_mod(2, k - 1, MOD);
    }
};
Share