网站流量怎么算的,网站建设分为多少模块,宝山网站建设公司,百度seo排名优化系统Leetcode 第 112 场双周赛题解 Leetcode 第 112 场双周赛题解题目1#xff1a;2839. 判断通过操作能否让字符串相等 I思路代码复杂度分析 题目2#xff1a;2840. 判断通过操作能否让字符串相等 II思路代码复杂度分析 题目3#xff1a;2841. 几乎唯一子数组的最大和思路代码复… Leetcode 第 112 场双周赛题解 Leetcode 第 112 场双周赛题解题目12839. 判断通过操作能否让字符串相等 I思路代码复杂度分析 题目22840. 判断通过操作能否让字符串相等 II思路代码复杂度分析 题目32841. 几乎唯一子数组的最大和思路代码复杂度分析 题目42842. 统计一个字符串的 k 子序列美丽值最大的数目思路代码复杂度分析 Leetcode 第 112 场双周赛题解
题目12839. 判断通过操作能否让字符串相等 I
思路
分两组
s1[0]s2[0] 和 s1[2]s2[2] 比较s1[1]s2[1] 和 s1[3]s2[3] 比较。
代码
/** lc appleetcode.cn id2839 langcpp** [2839] 判断通过操作能否让字符串相等 I*/// lc codestart
class Solution
{
public:bool canBeEqual(string s1, string s2){return ((s1[0] s2[0] s1[2] s2[2]) || (s1[0] s2[2] s1[2] s2[0])) ((s1[1] s2[1] s1[3] s2[3]) || (s1[1] s2[3] s1[3] s2[1]));}
};
// lc codeend复杂度分析
时间复杂度O(1)。
空间复杂度O(1)。
题目22840. 判断通过操作能否让字符串相等 II
思路
用两个哈希表 cnt1 和 cnt2 分别统计字符串 s1 和 s2 奇偶下标的字符的出现次数。
比较两个哈希表若相等说明通过操作可以让字符串 s1 和 s2 相等返回 true否则返回 false。
代码
/** lc appleetcode.cn id2840 langcpp** [2840] 判断通过操作能否让字符串相等 II*/// lc codestart// 哈希class Solution
{
public:bool checkStrings(string s1, string s2){int cnt1[2][26], cnt2[2][26];memset(cnt1, 0, sizeof(cnt1));memset(cnt2, 0, sizeof(cnt2));for (int i 0; i s1.length(); i){cnt1[i % 2][s1[i] - a];cnt2[i % 2][s2[i] - a];}return memcmp(cnt1, cnt2, sizeof(cnt1)) 0;}
};
// lc codeend复杂度分析
时间复杂度O(n∣Σ∣)其中 n 为字符串 s1 的长度。
空间复杂度O(∣Σ∣)其中 ∣Σ∣ 为字符集合的大小本题中字符均为小写字母所以 ∣Σ∣ 26。
题目32841. 几乎唯一子数组的最大和
思路
滑动窗口。
看到「长度固定的子数组」就要想到滑动窗口。
用一个哈希表 mp 维护窗口内的元素出现次数当窗口内的 mp.size()m 时更新子数组最大和。
代码
/** lc appleetcode.cn id2841 langcpp** [2841] 几乎唯一子数组的最大和*/// lc codestart// 滑动窗口class Solution
{
public:long long maxSum(vectorint nums, int m, int k){// 特判if (nums.empty() || m k)return 0LL;long long max_sum 0LL;vectorint window;unordered_mapint, int mp;long long sum 0LL;for (int i 0; i nums.size(); i){window.push_back(nums[i]);mp[nums[i]];sum nums[i];while (window.size() k){auto it window.begin();mp[*it]--;if (mp[*it] 0)mp.erase(*it);sum - *it;window.erase(it);}if (mp.size() m)max_sum max(max_sum, sum);}return max_sum;}
};
// lc codeend复杂度分析
时间复杂度O(n)其中 n 为数组 nums 的长度。
空间复杂度O(k)。哈希表的大小不会超过窗口长度即 k。
题目42842. 统计一个字符串的 k 子序列美丽值最大的数目
思路
哈希 组合数学。
提示 统计每个字符出现次数的个数然后从大到小遍历次数 c 及其个数 num。 所有方案数相乘即为答案。
如果 k 太大循环中没有出现 num≥k那么不存在合法子序列返回 0。
代码
/** lc appleetcode.cn id2842 langcpp** [2842] 统计一个字符串的 k 子序列美丽值最大的数目*/// lc codestart
class Solution
{
private:const int MOD 1e9 7;public:int countKSubsequencesWithMaxBeauty(string s, int k){vectorint cnt(26, 0);for (char c : s)cnt[c - a];// STL map 会自动按键从小到大排序mapint, int cc;for (int c : cnt)if (c)cc[-c];long long ans 1;for (auto [c, num] : cc){if (num k)return ans * pow(-c, k) % MOD * comb(num, k) % MOD;ans ans * pow(-c, num) % MOD;k - num;}return 0;}// 辅函数 - 快速幂long long pow(long long x, int n){long long res 1;for (; n; n / 2){if (n % 2)res res * x % MOD;x x * x % MOD;}return res;}// 辅函数 - 求组合数 C(n,k)long long comb(long long n, int k){long long res n;for (int i 2; i k; i){n--;// n, n-1, n-2,... 中的前 i 个数至少有一个因子 ires res * n / i;}return res % MOD;}
};
// lc codeend复杂度分析
时间复杂度O(n)其中 n 为字符串 s 的长度。
空间复杂度O(∣Σ∣)。其中 ∣Σ∣ 为字符集合的大小本题中字符均为小写字母所以 ∣Σ∣26。
