leetcode第375场周赛

  |  

摘要: 本文是 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++)

代码中 mergequickpower_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