Leetcode 第 374 场周赛题解
Leetcode 第 374 场周赛题解
题目1：2951. 找出峰值
思路
遍历。
代码
/*
* @lc app=leetcode.cn id=2951 lang=cpp
*
* [2951] 找出峰值
*/
// @lc code=start
class Solution
{
public:
vector<int> findPeaks(vector<int> &mountain)
{
vector<int> peaks;
for (int i = 1; i < mountain.size() - 1; i++)
if (mountain[i] > mountain[i - 1] && mountain[i] > mountain[i + 1])
peaks.push_back(i);
return peaks;
}
};
// @lc code=end
复杂度分析
时间复杂度：O(n)，其中 n 是数组 mountain 的长度。
空间复杂度：O(1)。
题目2：2952. 需要添加的硬币的最小数量
思路
贪心。
为方便处理，首先将数组 coins 按升序排序，然后计算需要添加的硬币的最小数量。
关键结论：对于正整数 x，如果区间 [1,x−1] 内的所有金额都可取得，且 x 在数组中，则区间 [1,2x−1] 内的所有金额也都可取得。
假设金额 x 不可取得，则至少需要在数组中添加一个小于或等于 x 的数，才能取得 x，否则无法取得 x。
如果区间 [1,x−1] 内的所有金额都可取得，则从贪心的角度考虑，添加 x 之后即可取得 x，且满足添加的金额个数最少。在添加 x 之后，区间 [1,2x−1] 内的所有金额都可取得，下一个不可取得的金额一定不会小于 2x。
由此可以提出一个贪心的方案。每次找到不可取得的最小的金额 x，在数组中添加 x，然后寻找下一个不可取得的最小的整数，重复上述步骤直到区间 [1,target] 中的所有金额都可取得。
代码
/*
* @lc app=leetcode.cn id=2952 lang=cpp
*
* [2952] 需要添加的硬币的最小数量
*/
// @lc code=start
class Solution
{
public:
int minimumAddedCoins(vector<int> &coins, int target)
{
sort(coins.begin(), coins.end());
int x = 1, index = 0;
int ans = 0;
while (x <= target)
{
if (index < coins.size() && coins[index] <= x)
{
// 可取得的区间从 [1, x−1] 扩展到 [1, x+coins[index]−1]
x += coins[index];
index++;
}
else
{
// 可取得的区间从 [1, x−1] 扩展到 [1, 2x-1]
x = 2 * x;
ans++;
}
}
return ans;
}
};
// @lc code=end
复杂度分析
时间复杂度：O(nlogn+log(target))，其中 n 是数组 coins 的长度，target 是给定的正整数。将数组 coins 排序需要 O(nlogn) 的时间，排序后需要遍历数组中的 n 个元素，以及更新 x 的值，由于 x 的值上限为 target，因此对 x 的值乘以 2 的操作不会超过 log(target) 次，故时间复杂度是 O(n+log(target))。
空间复杂度：O(logn)，其中 n 是数组 coins 的长度。主要为排序的递归调用栈空间。
题目3：2953. 统计完全子字符串
思路
分组循环 + 滑动窗口。
「相邻字母相差至多为 2」这个约束把 word 划分成了多个子串 s，每个子串分别处理。可以用分组循环找到每个子串 s。
对于每个子串，由于每个字符恰好出现 k 次，我们可以枚举有 m 种字符，这样问题就变成了：
长度固定为 m*k 的滑动窗口，判断每种字符是否都出现了恰好 k 次。
代码
/*
* @lc app=leetcode.cn id=2953 lang=cpp
*
* [2953] 统计完全子字符串
*/
// @lc code=start
class Solution
{
public:
int countCompleteSubstrings(string word, int k)
{
int n = word.size();
int ans = 0;
for (int i = 0; i < n;)
{
int start = i;
i++;
while (i < n && abs(int(word[i]) - int(word[i - 1])) <= 2)
i++;
ans += countCompleteStrings(word.substr(start, i - start), k);
}
return ans;
}
// 辅函数 - 计算字符串 s 中完全子字符串的个数
int countCompleteStrings(string s, int k)
{
int count = 0;
for (int m = 1; m <= 26 && m * k <= s.length(); m++)
{
vector<int> alphaCount(26, 0);
// 判断每种字符是否都出现了恰好 k 次
auto check = [&]() -> bool
{
for (int i = 0; i < 26; i++)
{
if (alphaCount[i] && alphaCount[i] != k)
return false;
}
return true;
};
// 滑动窗口
// for (int right = 0; right < s.length(); right++)
// {
// alphaCount[s[right] - 'a']++;
// int left = right + 1 - m * k;
// if (left >= 0)
// {
// if (check())
// count++;
// alphaCount[s[left] - 'a']--;
// }
// }
for (int i = 0; i < m * k; i++)
alphaCount[s[i] - 'a']++;
if (check())
count++;
for (int right = m * k; right < s.length(); right++)
{
alphaCount[s[right] - 'a']++;
alphaCount[s[right - m * k] - 'a']--;
if (check())
count++;
}
}
return count;
}
};
// @lc code=end
复杂度分析
时间复杂度：O(n∣Σ∣2)，其中 n 为字符串 word 的长度，∣Σ∣ 为字符集合的大小，本题中字符均为小写英文字母，所以 ∣Σ∣=26。
空间复杂度：O(∣Σ∣)。忽略切片开销。
题目4：2954. 统计感冒序列的数目
思路
题解：组合数学题，附模板（Python/Java/C++/Go）
代码
/*
* @lc app=leetcode.cn id=2954 lang=cpp
*
* [2954] 统计感冒序列的数目
*/
// @lc code=start
const static int MOD = 1e9 + 7;
const static int MX = 1e5;
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)
{
int m = sick.size();
int total = n - m;
long long ans = comb(total, sick[0]) * comb(total - sick[0], n - sick.back() - 1) % MOD;
total -= sick[0] + n - sick.back() - 1;
int e = 0;
for (int i = 0; i < m - 1; i++)
{
int k = sick[i + 1] - sick[i] - 1;
if (k)
{
e += k - 1;
ans = ans * comb(total, k) % MOD;
total -= k;
}
}
return ans * q_pow(2, e) % MOD;
}
};
// @lc code=end
复杂度分析
时间复杂度：O(m)，其中 m 为数组 sick 的长度。预处理的时间忽略不计。
空间复杂度：O(1)。预处理的空间忽略不计。
