第 374 场 LeetCode 周赛题解

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

A 找出峰值

枚举

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

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

贪心：对 $co in s$ 升序排序，枚举 $co in s [i]$ ，设当前已经可获得 $[0, re a c h]$ 范围内的任意整数金额，若 $\le reach + 1$ ，则由 $co in s [0, i]$ 的子序列可得到 $[0, re a c h + co in s [i]]$ 范围内的任意整数金额度，否则需要添加一个尽可能大的硬币 $re a c h + 1$

class Solution {
public:int minimumAddedCoins(vector<int> &coins, int target) {sort(coins.begin(), coins.end());int res = 0;int e, i, reach;for (e = 1, i = 0, reach = 0; reach < target && i < coins.size();) {if (coins[i] <= reach + 1) {reach += coins[i++];} else {res++;reach += reach + 1;}}for (; reach < target;) {res++;reach += reach + 1;}return res;}
};

C 统计完全子字符串

枚举 + 前缀和：首先用条件2将 $w or d$ 划分成若干满足子字符串，使得各子字符串内部任意相邻字符满足条件2，然后只需在各个子字符串中找满足条件1的子字符串，这样的字符串的长度只能是 $k,2k,\cdots,26k$ 其中之一，枚举子字符串可能的长度 $l e n$ ，然后滑动窗口枚举场长为 $l e n$ 的子字符串，用前缀和判断在该子串中的字符数量是否为 $k$

class Solution {
public:int cmp(const string &s, int k) {int n = s.size();int pre[n + 1][26];//前缀和for (int j = 0; j < 26; j++)pre[0][j] = 0;for (int i = 0; i < n; i++)for (int j = 0; j < 26; j++)pre[i + 1][j] = pre[i][j] + (s[i] - 'a' == j ? 1 : 0);int res = 0;for (int len = k; len <= s.size() && len <= 26 * k; len += k) {for (int l = 0, r = len - 1; r < n; l++, r++) {//子串s[l,r]int can = 1;for (int i = 0; i < 26; i++) {if (pre[r + 1][i] - pre[l][i] != 0 && pre[r + 1][i] - pre[l][i] != k) {can = 0;break;}}if (can)res++;}}return res;}int countCompleteSubstrings(string word, int k) {int res = 0;for (int i = 0, j = 0, n = word.size(); i < n;) {while (j + 1 < n && abs(word[j + 1] - word[j]) <= 2)j++;res += cmp(word.substr(i, j - i + 1), k);i = ++j;}return res;}
};

D 统计感冒序列的数目

计数 + 逆元：设以感冒的人为间隔，未感冒的人可以划分成若干人数为 $a_i$ 的组： $a_1,\cdots,a_k$ ，总序列数为： $\frac {(\sum a_i)!} {\prod a_i!} \times \prod f(a_i)$ ，其中当 $a_i$ 不是与边界相邻的组时 $f(a_i)=2^{a_i-1}$ ，否则 $f(a_i)=1$

class Solution {
public:using ll = long long;ll mod = 1e9 + 7;ll fpow(ll x, ll n) {//快速幂 x^nll res = 1;for (ll e = x; n; e = e * e % mod, n >>= 1)if (n & 1)res = res * e % mod;return res;}ll inv(ll x) {//x 在 mod 下的匿元 return fpow(x, mod - 2);}int numberOfSequence(int n, vector<int> &sick) {vector<ll> fact(n + 1, 1), f2(n + 1, 1);for (int i = 1; i <= n; i++) {fact[i] = fact[i - 1] * i % mod;f2[i] = f2[i - 1] * 2 % mod;}int res = 1;int m = sick.size();int s = 0;if (sick[0] != 0) {//与左边界相邻的组s += sick[0];res = res * inv(fact[sick[0]]) % mod;}if (sick[m - 1] != n - 1) {//与右边界相邻的组s += n - 1 - sick[m - 1];res = res * inv(fact[n - 1 - sick[m - 1]]) % mod;}for (int i = 0; i < m - 1; i++)//枚举中间的各个分组if (sick[i + 1] != sick[i] + 1) {int t = sick[i + 1] - sick[i] - 1;s += t;res = res * inv(fact[t]) % mod;res = res * f2[t - 1] % mod;}res = res * fact[s] % mod;return (res + mod) % mod;}
};