网站推广公司兴田德润在哪儿,wordpress get_query_var,专门做设计的网站有哪些,房地产推广策略Leetcode 第 374 场周赛题解 Leetcode 第 374 场周赛题解题目1#xff1a;2951. 找出峰值思路代码复杂度分析 题目2#xff1a;2952. 需要添加的硬币的最小数量思路代码复杂度分析 题目3#xff1a;2953. 统计完全子字符串思路代码复杂度分析 题目4#xff1a;2954. 统计感… Leetcode 第 374 场周赛题解 Leetcode 第 374 场周赛题解题目12951. 找出峰值思路代码复杂度分析 题目22952. 需要添加的硬币的最小数量思路代码复杂度分析 题目32953. 统计完全子字符串思路代码复杂度分析 题目42954. 统计感冒序列的数目思路代码复杂度分析 Leetcode 第 374 场周赛题解
题目12951. 找出峰值
思路
遍历。
代码
/** lc appleetcode.cn id2951 langcpp** [2951] 找出峰值*/// lc codestart
class Solution
{
public:vectorint findPeaks(vectorint mountain){vectorint 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 codeend复杂度分析
时间复杂度O(n)其中 n 是数组 mountain 的长度。
空间复杂度O(1)。
题目22952. 需要添加的硬币的最小数量
思路
贪心。
为方便处理首先将数组 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 appleetcode.cn id2952 langcpp** [2952] 需要添加的硬币的最小数量*/// lc codestart
class Solution
{
public:int minimumAddedCoins(vectorint 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, xcoins[index]−1]x coins[index];index;}else{// 可取得的区间从 [1, x−1] 扩展到 [1, 2x-1]x 2 * x;ans;}}return ans;}
};
// lc codeend
复杂度分析
时间复杂度O(nlognlog(target))其中 n 是数组 coins 的长度target 是给定的正整数。将数组 coins 排序需要 O(nlogn) 的时间排序后需要遍历数组中的 n 个元素以及更新 x 的值由于 x 的值上限为 target因此对 x 的值乘以 2 的操作不会超过 log(target) 次故时间复杂度是 O(nlog(target))。
空间复杂度O(logn)其中 n 是数组 coins 的长度。主要为排序的递归调用栈空间。
题目32953. 统计完全子字符串
思路
分组循环 滑动窗口。
「相邻字母相差至多为 2」这个约束把 word 划分成了多个子串 s每个子串分别处理。可以用分组循环找到每个子串 s。
对于每个子串由于每个字符恰好出现 k 次我们可以枚举有 m 种字符这样问题就变成了
长度固定为 m*k 的滑动窗口判断每种字符是否都出现了恰好 k 次。
代码
/** lc appleetcode.cn id2953 langcpp** [2953] 统计完全子字符串*/// lc codestart
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){vectorint 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 codeend复杂度分析
时间复杂度O(n∣Σ∣2)其中 n 为字符串 word 的长度∣Σ∣ 为字符集合的大小本题中字符均为小写英文字母所以 ∣Σ∣26。
空间复杂度O(∣Σ∣)。忽略切片开销。
题目42954. 统计感冒序列的数目
思路
题解组合数学题附模板Python/Java/C/Go
代码
/** lc appleetcode.cn id2954 langcpp** [2954] 统计感冒序列的数目*/// lc codestartconst 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, vectorint 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 codeend复杂度分析
时间复杂度O(m)其中 m 为数组 sick 的长度。预处理的时间忽略不计。
空间复杂度O(1)。预处理的空间忽略不计。
