周赛374（枚举、思维题、分组循环+枚举、组合数学）

本文主要是介绍周赛374（枚举、思维题、分组循环+枚举、组合数学），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

周赛374
- [2951. 找出峰值](https://leetcode.cn/problems/find-the-peaks/)
- - 枚举
- [2952. 需要添加的硬币的最小数量](https://leetcode.cn/problems/minimum-number-of-coins-to-be-added/)
- - 思维题
- [2953. 统计完全子字符串](https://leetcode.cn/problems/count-complete-substrings/)
- - 分组循环 + 枚举
- [2954. 统计感冒序列的数目](https://leetcode.cn/problems/count-the-number-of-infection-sequences/)
- - 组合数学

周赛374

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

枚举

class Solution {public List<Integer> findPeaks(int[] mountain) {List<Integer> res = new ArrayList<>();for(int i = 1; i < mountain.length-1; i++){if(mountain[i] > mountain[i-1] && mountain[i] > mountain[i+1])res.add(i);}return res;}
}

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

思维题

class Solution {/**假设现在得到了[0,s-1]内的所有整数，此时新发现了一个整数x，把x加到已获得的数字中，就得到了[x, s+x-1]内的所有整数分类讨论如果 x<=s，那么合并区间，可以得到[0, s+x-1]的所有整数如果 x>s，这意味着无法得到s，就一定要把s加到数组中，这样可以得到[s,2s-1]内的整数与[0,s-1]合并，得到[0,2s-1]的所有整数，再继续分类讨论*/public int minimumAddedCoins(int[] coins, int target) {Arrays.sort(coins);int ans = 0, s = 1, i = 0;while(s <= target){if(i < coins.length && coins[i] <= s){s += coins[i];i++;}else{s *= 2; // 必须添加sans++;}}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/problems/count-complete-substrings/solutions/2551743/bao-li-hua-chuang-mei-ju-chuang-kou-nei-31j5m/

class Solution {/**b ad **固定条件2：「相邻字母相差至多为 2」 这个约束把 word 划分成了多个子串 s，每个字串分别处理。可以用 分组循环 找到每个子串 s。讨论条件1：对于每个字串，由于每个字符恰好出现k次，那么我们可以枚举m种字符问题就变成了：长度固定为m*k的滑动窗口，判断每种字符是否都出现了恰好k次*/public int countCompleteSubstrings(String word, int k) {int n = word.length();int ans = 0;int i = 0;while(i < n){int start = i;i++;while(i < n && Math.abs(word.charAt(i) - word.charAt(i-1)) <= 2)i++;// 此时 [start, i) 是「相邻字母相差至多为 2」 的字串ans += f(word.substring(start, i), k);}return ans;}public int f(String S, int k){// 判断字串s中，每种字符是否都出现了恰好k次// 枚举字串有多少种字母，长度一定是k的整数倍（m个字符==>mk长度）// 问题变成了，长度恰好为m*k的窗口内，是否满足个字母恰好出现k次char[] s = S.toCharArray();int res = 0;// m是窗口内的元素个数 mk窗口长度for(int m = 1; m <= 26 && k * m <= s.length; m++){int[] cnt = new int[26];for(int right = 0; right < s.length; right++){cnt[s[right] - 'a']++;int left = right + 1 - k*m;if(left >= 0){// 判断窗口内是否每个字母恰好出现k次boolean ok = true;for(int i = 0; i < 26; i++){if(cnt[i] > 0 && cnt[i] != k){ok = false;break;}}if(ok) res++;cnt[s[left] - 'a']--;}}}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/solutions/2551734/zu-he-shu-xue-ti-by-endlesscheng-5fjp/

class Solution {private static final int MOD = 1_000_000_007;private static final int MX = 100_000;// 组合数模板private static final long[] FAC = new long[MX];private static final long[] INV_FAC = new long[MX];static {FAC[0] = 1;for (int i = 1; i < MX; i++) {FAC[i] = FAC[i - 1] * i % MOD;}INV_FAC[MX - 1] = pow(FAC[MX - 1], MOD - 2);for (int i = MX - 1; i > 0; i--) {INV_FAC[i - 1] = INV_FAC[i] * i % MOD;}}private static long comb(int n, int k) {return FAC[n] * INV_FAC[k] % MOD * INV_FAC[n - k] % MOD;}public int numberOfSequence(int n, int[] a) {int m = a.length;int total = n - m;long ans = comb(total, a[0]) * comb(total - a[0], n - a[m - 1] - 1) % MOD;total -= a[0] + n - a[m - 1] - 1;int e = 0;for (int i = 1; i < m; i++) {int k = a[i] - a[i - 1] - 1;if (k > 0) {e += k - 1;ans = ans * comb(total, k) % MOD;total -= k;}}return (int) (ans * pow(2, e) % MOD);}private static long pow(long x, int n) {long res = 1;for (; n > 0; n /= 2) {if (n % 2 > 0) {res = res * x % MOD;}x = x * x % MOD;}return res;}
}