【LeetCode周赛】LeetCode第374场周赛

本文主要是介绍【LeetCode周赛】LeetCode第374场周赛，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

找出峰值(简单模拟题)

找出峰值
分析:
这是一个很简单的模拟题，直接遍历整个数组，判断每个元素是不是严格大于其相邻元素即可。

代码:

class Solution {
public:vector<int> findPeaks(vector<int>& mountain) {vector<int> ans;for(int i = 1; i < mountain.size() - 1; i ++){if(mountain[i] > mountain[i - 1] && mountain[i] > mountain[i + 1]) ans.push_back(i);}return ans;}
};

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

需要添加的硬币的最小数量
分析:
不妨定义当前能够表示的硬币的右边界为s，则一开始什么硬币都没有的情况下，能够表示的金额范围是 $[0, s - 1], s = 1$ ，如果此时有一个新的硬币x，加入后，可以得到 $[x, x + s - 1]$ 范围内的所有数。
那么分类讨论一下：

$\le s$ ，则加入x之后，合并这两个区间，能够得到 $[0, x + s - 1]$ 的所有整数；
$\gt s$ ，合并区间后，在 $[s, x - 1]$ 之间的数是没有的。那怎么办呢，从贪心的思路出发，s是肯定要加入进来的(加比s小的数不如加s好)，那么这样可以得到 $[0, 2 s - 1]$ 之间的所有数，然后再继续判断x和s的大小，重复上述两个操作。

我们考虑一个一个地将数组coins的面值加入这个区间中，先对coins数组排序。
代码:

class Solution {
public:int minimumAddedCoins(vector<int>& coins, int target) {int n = coins.size();int ans = 0, s = 1, i = 0;sort(coins.begin(), coins.end());while(s <= target){//如果当前coins[i]<=s,那么将coins[i]加入之后，范围从[0,s-1]到[0,coins[i]+s-1]if(i < n && coins[i] <= s){s += coins[i++];}//如果当前coins[i]>s,那么肯定要把s加入区间，范围从[0,s-1]到[0,2s-1]else{s <<= 1;ans++;}}return ans;}
};

时间复杂度: $\log n+ \log target)$
空间复杂度: $O (1)$

统计完全子字符串(枚举分组+滑动窗口)

统计完全子字符串

分析:
首先，根据完美字符串中所述，相邻字符在字母表中的顺序至多相差2。根据这一点要求，就可以将字符串word划分为多个组，每个组中是符合这个条件的字符串s。
再对每一个字符串s进行判断，符合条件的子串需要满足每个字符恰好出现k 次，一共只有26个字符，所以我们可以枚举一共有m种字符 $\le m \le 26$ ，这样，这个问题就变成了，有一个大小为 $\times k$ 的窗口，判断这个窗口种每个字符是否都只出现了 $k$ 次。

代码:

class Solution {int cal(string s, int k){//判断这个子串中有多少个每个字符出现k次的子串int len = s.size(), res = 0;for(int m = 1; m <= 26; m++){//假设有m个出现k次的字符int sub_len = m * k;if(sub_len > len)break;int i = 0, j = 0;int cnt[26] = {0};//统计字符数量function <bool()> check = [&] () -> bool{for(int i = 0; i < 26; i++){if(cnt[i] != k && cnt[i] != 0)return false;}return true;};while(j < sub_len)++cnt[s[j++] - 'a'];if(check())++res;while(j < len){--cnt[s[i++] - 'a'];++cnt[s[j++] - 'a'];if(check())++res;}}return res;}
public:int countCompleteSubstrings(string word, int k){int n = word.size();int l, r = 0, ans = 0;while(r < n){l = r++;//考虑多个符合第二个条件的子串，[l,r)while(r < n && abs(word[r] - word[r - 1]) <= 2)r++;ans += cal(word.substr(l, r - l), k);}return ans;}
};

时间复杂度: $\times 26 \times 26)$
空间复杂度: $O (26)$

其次，还可以进一步进行优化，如果能够在cal函数中把check函数优化掉，那么可以变得更快，其实每一次统计一个窗口中的字符，是否满足都是出现k次，可以再定义一个哈希表，这个哈希表的用途是来维护出现次数的次数，只有出现次数为k的次数是m，其实意思就是所有的字符都是出现了k次，因为窗口大小为 $\times m$ 。

class Solution {int cal(string s, int k){//判断这个子串中有多少个每个字符出现k次的子串int len = s.size(), res = 0;for(int m = 1; m <= 26; m++){//假设有m个出现k次的字符int sub_len = m * k;if(sub_len > len)break;int i = 0, j = 0;//维护一个出现次数的出现次数，可以变成O(1)来判断是否满足完美子字符串的条件int cc[100005] = {0};int cnt[26] = {0};//统计字符数量while(j < sub_len){cc[cnt[s[j] - 'a']]--;cc[++cnt[s[j++] - 'a']]++;}if(cc[k] == m)++res;while(j < len){cc[cnt[s[i] - 'a']] -= 1;cc[--cnt[s[i++] - 'a']] += 1;cc[cnt[s[j] - 'a']] -= 1;cc[++cnt[s[j++] - 'a']] += 1;if(cc[k] == m)++res;}}return res;}
public:int countCompleteSubstrings(string word, int k){int n = word.size();int l, r = 0, ans = 0;while(r < n){l = r++;//考虑多个符合第二个条件的子串，[l,r)while(r < n && abs(word[r] - word[r - 1]) <= 2)r++;ans += cal(word.substr(l, r - l), k);}return ans;}
};

时间复杂度: $\times 26)$
空间复杂度: $O (26)$

统计感冒序列的数目(组合数学)

统计感冒序列的数目
根据题意我们可以有如下讨论的情况。

首先，对于每个小朋友是如何感染的，只可能是从其左边的小朋友传染或者是右边的小朋友传染，那么就是相当于得到一个由L,R组成的序列，意思就是当前操作是往左边感染还是往右边感染。
考虑例一： $n = 5, s i c k = [0, 4]$
[0,1,2,3,4]，那么中间这三个位置可以填入的顺序是什么呢？
- L,L,L/R
- L,R,L,R
- R,R,L/R
- R,L,L/R
不难发现，因为最后一个小朋友，不管是其左边的小朋友感染的还是右边的小朋友感染的，都是没有区别的，所以对于一个这样的序列，感染的方式是 $2^{m-1}$ ， $m$ 是这个序列的长度。
对于每一段(即左右端点都是感冒小朋友的序列)，其可以填入的L/R的方案是 $2^(m-1)$ ，每一段相互独立，互不影响填入L/R的方式， $m$ 为这一段的长度，所以最后的答案肯定是需要 $2^{m_1} \times 2 ^{m_2} \times 2^{m_3} \times ......$ ，即 $2^{m_1+m_2+m_3+...}$ 。
上面所述的都没有考虑感染的时间点，因为题目要求每一秒中， 至多一位还没感冒的小朋友会被传染。所以，对于很多段来说，我们还要考虑的就是每一个时间点，哪个地方会被感染，假设有 $n - m$ 个没被感染的人，就有 $t = n - m$ 个时刻，从 $t$ 时刻中任意选择 $m_1$ 个时刻给第一段感染， $C (t, m 1)$ ，剩下 $t-m_1$ 个时刻选 $m_2$ 个时刻给第二段感染， $C (t - m 1, m 2)$ ，依次类推…
对于最左边的感染者再左边的小朋友，最右边感染者再右边的小朋友，其只能填入LLLL和RRRR，所以可填入的方案是1，仅需要考虑填入的时刻。

根据上面所述，本题就变成了一个简单的组合数学问题，因为要取模，所以计算组合数除法时会用到逆元。

const int MOD = 1'000'000'007;
const int MX = 100'000;long long q_pow(long long x, int n) {long long res = 1;for (; n > 0; n /= 2) {if (n % 2) {res = res * x % MOD;}x = x * x % MOD;}return res;
}// 组合数模板
long long fac[MX], inv_fac[MX];auto init = [] {fac[0] = 1;for (int i = 1; i < MX; i++) {fac[i] = fac[i - 1] * i % MOD;}inv_fac[MX - 1] = q_pow(fac[MX - 1], MOD - 2);for (int i = MX - 1; i > 0; i--) {inv_fac[i - 1] = inv_fac[i] * i % MOD;}return 0;
}();long long comb(int n, int k) {return fac[n] * inv_fac[k] % MOD * inv_fac[n - k] % MOD;
}class Solution {
public:int numberOfSequence(int n, vector<int>& sick) {/*一个数学问题——排列组合1.相当于得到一个由L,R组成的序列2.对于每一段(即左右端点都是感冒小朋友的序列),其可以填入的L/R的方案是2^(m-1)，每一段相互独立，互不影响填入L/R的方式  m为这一段的长度3.对于很多段来说，我们要考虑的就是每一个时间点，哪个地方会被感染，假设有n-m个没被感染的人，就有t=n-m个时刻，从t时刻中任意选择m1个时刻给第一段感染，C(t,m1)，剩下t-m1个时刻选m2个时刻给第二段感染,C(t-m1,m2)，依次类推......4.对于最左边的感染者再左边的小朋友，最右边感染者再右边的小朋友，其只能填入LLLL和RRRR，所以可填入的方案是1，仅需要考虑填入的时刻*/int m = sick.size();int total = n - m;//剩下t时刻相当于long long ans = comb(total, sick[0]) * comb(total - sick[0], n - sick.back() - 1) % MOD;//先考虑上述第四种情况total -= sick[0] + n - sick.back() - 1;int exp = 0;//维护一下第二点所述的指数一共有多少for(int i = 0; i < m - 1; i++){int k = sick[i + 1] - sick[i] - 1;//每一段的小朋友数量if(k){exp += k - 1;ans = ans * comb(total, k) % MOD;total -= k;}}return ans * q_pow(2, exp) % MOD;}
};