leetcode contest 374

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/

题意

模拟

思路

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

• 时间复杂度：$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/

题意

贪心

思路

1. 题目带一点技巧，但是也不是很难，首选我们需要对数组按照从小到达进行排序，我们假设前 $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$ 即可。
2. 复杂度分析：

• 时间复杂度：$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/

题意

滑动窗口

思路

1. 不太明白这个题目也标 $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$, 我们可以利用前缀和求出相同字符的数目；
2. 时间复杂度：

• 时间复杂度：$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/

题意

组合数学

思路

1. 题目本身还是比较难的，我们首先假设两个感冒的小朋友为 $(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}$ 可能较大，此时需要进行乘法逆元运算，我们可以利用线性的乘法逆元计算即可，直接用快速幂求每个逆元的话会超时。

2. 复杂度分析:

• 时间复杂度：$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
• 关注我的微信公众号: 公务程序猿