leetcode contest 374

T4 确实是个好题目，总体来说本周周赛题目确实还算比较难，不过前三题难度还好，基本上不需要太多技巧。

2951. 找出峰值

给你一个下标从 0 开始的数组 mountain 。你的任务是找出数组 mountain 中的所有峰值。

以数组形式返回给定数组中峰值的下标，顺序不限 。

注意：

峰值是指一个严格大于其相邻元素的元素。
数组的第一个和最后一个元素不是峰值。

示例 1：

输入：mountain = [2,4,4]
输出：[]
解释：mountain[0] 和 mountain[2] 不可能是峰值，因为它们是数组的第一个和最后一个元素。
mountain[1] 也不可能是峰值，因为它不严格大于 mountain[2] 。
因此，答案为 [] 。

示例 2：

输入：mountain = [1,4,3,8,5]
输出：[1,3]
解释：mountain[0] 和 mountain[4] 不可能是峰值，因为它们是数组的第一个和最后一个元素。
mountain[2] 也不可能是峰值，因为它不严格大于 mountain[3] 和 mountain[1] 。
但是 mountain[1] 和 mountain[3] 严格大于它们的相邻元素。
因此，答案是 [1,3] 。

提示：

3 <= mountain.length <= 100
1 <= mountain[i] <= 100

地址

https://leetcode.cn/contest/weekly-contest-374/problems/find-the-peaks/

题意

模拟

思路

直接模拟即可，检测相邻元素的差值即可。
复杂度分析：

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

代码

class Solution:
    def findPeaks(self, mountain: List[int]) -> List[int]:
        return [i for i in range(1, len(mountain) - 1) if mountain[i] > mountain[i - 1] and mountain[i] > mountain[i + 1]]

2952. 需要添加的硬币的最小数量

给你一个下标从 0 开始的整数数组 coins，表示可用的硬币的面值，以及一个整数 target 。

如果存在某个 coins 的子序列总和为 x，那么整数 x 就是一个 可取得的金额 。

返回需要添加到数组中的 任意面值 硬币的 最小数量 ，使范围 [1, target] 内的每个整数都属于 可取得的金额 。

数组的 子序列 是通过删除原始数组的一些（可能不删除）元素而形成的新的非空数组，删除过程不会改变剩余元素的相对位置。

示例 1：

输入：coins = [1,4,10], target = 19
输出：2
解释：需要添加面值为 2 和 8 的硬币各一枚，得到硬币数组 [1,2,4,8,10] 。
可以证明从 1 到 19 的所有整数都可由数组中的硬币组合得到，且需要添加到数组中的硬币数目最小为 2 。

示例 2：

输入：coins = [1,4,10,5,7,19], target = 19
输出：1
解释：只需要添加一枚面值为 2 的硬币，得到硬币数组 [1,2,4,5,7,10,19] 。
可以证明从 1 到 19 的所有整数都可由数组中的硬币组合得到，且需要添加到数组中的硬币数目最小为 1 。

示例 3：

输入：coins = [1,1,1], target = 20
输出：3
解释：
需要添加面值为 4 、8 和 16 的硬币各一枚，得到硬币数组 [1,1,1,4,8,16] 。 
可以证明从 1 到 20 的所有整数都可由数组中的硬币组合得到，且需要添加到数组中的硬币数目最小为 3 。

提示：

1 <= target <= 105
1 <= coins.length <= 105
1 <= coins[i] <= target

地址

https://leetcode.cn/contest/weekly-contest-374/problems/minimum-number-of-coins-to-be-added/

题意

贪心

思路

题目带一点技巧，但是也不是很难，首选我们需要对数组按照从小到达进行排序，我们假设前 $i-1$ 个元素组成的数字之和的最大值 $x$, 此时的元素为 $y = coins[i]$，此时可以知道：
- $[1,2,3,4,\cdots,x]$ 都已经全部构成，此时我们知道加入加上 $coins[i]$ 后，此时可以构成 $[y,1 + y, 2 + y, 3 + y, 4 + y, \cdots,x + y]$；
- 如何保证上述两部分数组连续，此时只需要满足 $y \le x + 1$ 即可，此时我们知道可以构成的最大元素即为 $x + y$, 我们更新 $x$ 即可；
- 根据以上推论，我们只需检测到当前数目可以累加到 $target$ 即可。
复杂度分析：

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

代码

class Solution:
    def minimumAddedCoins(self, coins: List[int], target: int) -> int:
        coins.sort()
        cur = 0
        ans = 0
        for x in coins:
            if x - cur <= 1:
                cur += x
            else:
                while cur < target and x - cur > 1:
                    cur += cur + 1
                    ans += 1
                cur += x
            if cur >= target:
                break
        while cur < target:
            cur += cur + 1
            ans += 1
        return ans

2953. 统计完全子字符串

给你一个字符串 word 和一个整数 k 。

如果 word 的一个子字符串 s 满足以下条件，我们称它是 完全字符串：

s 中每个字符恰好出现 k 次。
相邻字符在字母表中的顺序至多相差 2 。也就是说，s 中两个相邻字符 c1 和 c2 ，它们在字母表中的位置相差至多为 2 。

请你返回 word 中完全子字符串的数目。

子字符串 指的是一个字符串中一段连续非空的字符序列。

示例 1：

输入：word = "igigee", k = 2
输出：3
解释：完全子字符串需要满足每个字符恰好出现 2 次，且相邻字符相差至多为 2 ：igigee, igigee, igigee 。

示例 2：

输入：word = "aaabbbccc", k = 3
输出：6
解释：完全子字符串需要满足每个字符恰好出现 3 次，且相邻字符相差至多为 2 ：aaabbbccc, aaabbbccc, aaabbbccc, aaabbbccc, aaabbbccc, aaabbbccc 。

提示：

1 <= word.length <= 105
word 只包含小写英文字母。
1 <= k <= word.length

地址

https://leetcode.cn/contest/weekly-contest-374/problems/count-complete-substrings/

题意

滑动窗口

思路

不太明白这个题目也标 $hard$，题目本身不是很难，涉及一个核心问题，$s$ 中每个字符恰好出现 $k$ 次，此时 $s$ 的长度一共有 $26$ 可能，$len(s) \in[k,2k, \cdots, 26k]$，我们枚举 $s$ 的长度 $l$：
- 设以 $i$ 为结尾构成满足相邻字符差距小于等于 $2$ 的长度为 $dp[i]$, 此时 $l \le dp[i]$;
- $s[i-l+1:i]$ 之内的字符串均满足相同字符的数目均为 $k$, 我们可以利用前缀和求出相同字符的数目；
时间复杂度：

时间复杂度：$O(n\times |\Sigma|^2)$，其中$n$ 表示给定数组的长度；

空间复杂度：$O(n \times |\Sigma|)$，其中$n$ 表示给定数组的长度；

代码

class Solution {
public:
    int countCompleteSubstrings(string word, int k) {
        int n = word.size();
        int res = 0;
        vector<int> dp(n, 1);
        vector<vector<int>> cnt(n + 1, vector<int>(26));
        for (int i = 1; i < n; i++) {
            if (abs(word[i] - word[i - 1]) <= 2) {
                dp[i] = dp[i - 1] + 1;
            } else {
                dp[i] = 1;
            }
        }
        for (int i = 0; i < n; i++) {
            cnt[i + 1] = cnt[i];
            cnt[i + 1][word[i] - 'a']++;
        }
        for (int i = k - 1; i < n; i++) {
            for (int j = 1; j <= 26 && dp[i] >= k * j && i + 1 - k * j >= 0; j++) {
                bool valid = true;
                for (int l = 0; l < 26; l++) {
                    int x = cnt[i + 1][l] - cnt[i + 1 - k * j][l];
                    if (x != 0 && x != k) {
                        valid = false;
                        break;
                    }
                }
                if (valid) {
                    res++;
                }
            }
        }
        return res;
    }
};

2954. 统计感冒序列的数目

给你一个整数 n 和一个下标从 0 开始的整数数组 sick ，数组按升序排序。

有 n 位小朋友站成一排，按顺序编号为 0 到 n - 1 。数组 sick 包含一开始得了感冒的小朋友的位置。如果位置为 i 的小朋友得了感冒，他会传染给下标为 i - 1 或者 i + 1 的小朋友，前提是被传染的小朋友存在且还没有得感冒。每一秒中，至多一位还没感冒的小朋友会被传染。

经过有限的秒数后，队列中所有小朋友都会感冒。感冒序列指的是所有一开始没有感冒的小朋友最后得感冒的顺序序列。请你返回所有感冒序列的数目。

由于答案可能很大，请你将答案对 109 + 7 取余后返回。

注意，感冒序列不包含一开始就得了感冒的小朋友的下标。

示例 1：

输入：n = 5, sick = [0,4]
输出：4
解释：一开始，下标为 1 ，2 和 3 的小朋友没有感冒。总共有 4 个可能的感冒序列：
- 一开始，下标为 1 和 3 的小朋友可以被传染，因为他们分别挨着有感冒的小朋友 0 和 4 ，令下标为 1 的小朋友先被传染。
然后，下标为 2 的小朋友挨着感冒的小朋友 1 ，下标为 3 的小朋友挨着感冒的小朋友 4 ，两位小朋友都可以被传染，令下标为 2 的小朋友被传染。
最后，下标为 3 的小朋友被传染，因为他挨着感冒的小朋友 2 和 4 ，感冒序列为 [1,2,3] 。
- 一开始，下标为 1 和 3 的小朋友可以被传染，因为他们分别挨着感冒的小朋友 0 和 4 ，令下标为 1 的小朋友先被传染。
然后，下标为 2 的小朋友挨着感冒的小朋友 1 ，下标为 3 的小朋友挨着感冒的小朋友 4 ，两位小朋友都可以被传染，令下标为 3 的小朋友被传染。
最后，下标为 2 的小朋友被传染，因为他挨着感冒的小朋友 1 和 3 ，感冒序列为  [1,3,2] 。
- 感冒序列 [3,1,2] ，被传染的顺序：[0,1,2,3,4] => [0,1,2,3,4] => [0,1,2,3,4] => [0,1,2,3,4] 。
- 感冒序列 [3,2,1] ，被传染的顺序：[0,1,2,3,4] => [0,1,2,3,4] => [0,1,2,3,4] => [0,1,2,3,4] 。

示例 2：

输入：n = 4, sick = [1]
输出：3
解释：一开始，下标为 0 ，2 和 3 的小朋友没有感冒。总共有 3 个可能的感冒序列：
- 感冒序列 [0,2,3] ，被传染的顺序：[0,1,2,3] => [0,1,2,3] => [0,1,2,3] => [0,1,2,3] 。
- 感冒序列 [2,0,3] ，被传染的顺序：[0,1,2,3] => [0,1,2,3] => [0,1,2,3] => [0,1,2,3] 。
- 感冒序列 [2,3,0] ，被传染的顺序：[0,1,2,3] => [0,1,2,3] => [0,1,2,3] => [0,1,2,3] 。

提示：

2 <= n <= 105
1 <= sick.length <= n - 1
0 <= sick[i] <= n - 1
sick 按升序排列。

地址

https://leetcode.cn/problems/count-the-number-of-infection-sequences/description/

题意

组合数学

思路

题目本身还是比较难的，我们首先假设两个感冒的小朋友为 $(x,y)$，他们之间的距离为 $k$ 个位置时，有多少种感冒序列：

此时我们可以知道第一个小朋友可以感染 $[0,1,2,3,4, \cdots, k]$ 个人，同时第二个小朋友可以感染 $[k, k - 1, k - 2, \cdots, 0]$ 个人；
此时假设第一个小朋友感染右边的 $i$, 则右边的小朋友会感染左边的 $k-i$ 个人。此时左边的感染序列是 $[0, 1,2, 3,4,\cdots, i]$, 右边的感染序列是$[0, 1, 2, 3,4, \cdots, n - i]$；我们可以看到产生的序列可能如下：
$$
[1,0,0,\cdots, 0, 0] \
[1,1,0,\cdots, 0, 0] \
[1,1,0,\cdots, 0, 1] \
\cdots \
[1,1,1,\cdots, 1, 1]
$$
上述序列的长度一共是 $k$ 个，我们可以看到无论 $i$ 为何值，此时最后一个序列总是相同的，此时我们只需要在前 $k-1$ 个序列中选择 $i-1$ 个序列分配给第一个小朋友的感染序列，此时第二个小朋友的感染序列即可确定，此时可能的选择方法数目为 $C_{k-1}^{i-1}$，此时我们知道 $i \in [0,k]$个，则此时可以知道总共可能的选择序列数目有 $C_{k-1}^{0} + C_{K-1}^{1} + \cdots + C_{k-1}^{k-1} = 2^{k-1}$个；
假设存在现在存在多个感冒序列，长度分别为 $l_0,l_1,l_3 \cdots$,则此时可以选择的方法数目为 $s = C_{l1+l2+l3 + \cdots}$ 中选择 $l_1$ 个位置存在 $l_1$ 的感冒序列，$l_2$ 个位置存在 $l_2$ 的感冒序列，此时总共的方法数目为 $C_s^{l_1} \times C_{s-l_1}^{l2} \times C_{s-l_1-l_2}^{l_3}$；
根据以上分析我们直接模拟即可，由于 $C_M^{N}$ 可能较大，此时需要进行乘法逆元运算，我们可以利用线性的乘法逆元计算即可，直接用快速幂求每个逆元的话会超时。

复杂度分析:

时间复杂度：$O(n \log U)$，其中 $n$ 表示数组的长度，$U$ 表示数组中元素的最大值；
空间复杂度：$O(n)$，其中 $n$ 表示数组的长度；

代码

[sol1-python]

class Solution:
    def numberOfSequence(self, n: int, sick: List[int]) -> int:
        def fastPow(x, n, mod):
            res = 1
            while n != 0:
                if n & 1:
                    res = res * x % mod
                x = x * x % mod
            return res

        def comb(a, b):
            return A[a] * invs[a - b] % mod * invs[b] % mod

        m = len(sick)
        mod = 10**9 + 7
        A = [1] * (n + 1)
        invs = [1] * (n + 1)
        for i in range(1, n + 1):
            A[i] = i * A[i - 1] % mod
            invs[i] = fastPow(A[i], mod - 2, mod)
        tot = n - m
        start, end = sick[0], n - sick[-1] - 1
        ans = comb(tot, start) * comb(tot - start, end) % mod
        tot -= start + end
        cnt = 0
        for i in range(1, len(sick)):
            k = sick[i] - sick[i - 1] - 1
            if k > 0:
                ans = ans * comb(tot, k) % mod
                cnt += k - 1
                tot -= k
   
        return ans * fastPow(2, cnt, mod) % mod

[sol1-C++]

class Solution {
public:
    long long fastPow(long long x, int n, long long mod) {
        long long res = 1;
        for (int i = n; i != 0; i >>= 1) {
            if (i & 1) {
                res = res * x % mod;
            }
            x = x * x % mod;
        }
        return res;
    }

    int numberOfSequence(int n, vector<int>& sick) {
        int m = sick.size();
        long long mod = 1e9 + 7;
        vector<long long> A(n + 1, 1);
        vector<long long> invs(n + 1, 1);
        for (int i = 1; i <= n; i++) {
            A[i] = i * A[i - 1] % mod;
        }
        invs[n] = fastPow(A[n], mod - 2, mod);
        for (int i = n; i > 1; i--) {
            invs[i - 1] = invs[i] * i % mod;
        }

        auto comb = [&](int a, int b) {
            return A[a] * invs[a - b] % mod * invs[b] % mod;
        };

        int tot = n - m;
        int start = sick[0], end = n - sick.back() - 1;
        long long ans = comb(tot, start) * comb(tot - start, end) % mod;
        tot -= start + end;

        int cnt = 0;     
        for (int i = 1; i < sick.size(); i++) {
            int k = sick[i] - sick[i - 1] - 1;
            if (k > 0) {
                ans = ans * comb(tot, k) % mod;
                cnt += k - 1;
                tot -= k;
            }
        }
        
        return ans * fastPow(2, cnt, mod) % mod;
    }
};

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

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

Tags: 题解力扣周赛赛

← leetcode biweekly contest 119 leetcode biweekly contes 118 →

扫描二维码，分享此文章