Leetcode 第 419 场周赛题解

Leetcode 第 419 场周赛题解

题目1：3318. 计算子数组的 x-sum I

思路

枚举每一个长度为 k 的子数组：

• 用一个哈希表 cnt 统计数组中所有元素的出现次数。
• 排序得到次数最多的前 x 个元素（如果两个元素的出现次数相同，则数值较大的元素被认为出现次数更多）。
• 计算结果数组的和，保存在答案里。

注意，如果数组中的不同元素少于 x 个，则其 x-sum 是数组的元素总和。

最后返回答案数组。

代码

/** @lc app=leetcode.cn id=3318 lang=cpp** [3318] 计算子数组的 x-sum I*/// @lc code=start
class Solution
{
public:vector<int> findXSum(vector<int> &nums, int k, int x){int n = nums.size();vector<int> ans(n - k + 1);auto cal_x_sum = [&](int start) -> int{unordered_map<int, int> cnt;for (int i = start; i < start + k; i++)cnt[nums[i]]++;if (cnt.size() < x)return accumulate(nums.begin() + start, nums.begin() + start + k, 0);vector<pair<int, int>> vp;for (auto &[x, c] : cnt)vp.push_back(make_pair(x, c));sort(vp.begin(), vp.end(),[&](const pair<int, int> &p1, const pair<int, int> &p2){if (p1.second != p2.second)return p1.second > p2.second;elsereturn p1.first > p2.first;});int sum = 0;for (int i = 0; i < x; i++)sum += vp[i].first * vp[i].second;return sum;};for (int i = 0; i < ans.size(); i++)ans[i] = cal_x_sum(i);return ans;}
};
// @lc code=end

复杂度分析

时间复杂度：O((n-k+1) * (k + klogk + x))，其中 n 是数组 nums 的长度。

空间复杂度：O((n-k+1) * k)，其中 n 是数组 nums 的长度。

题目2：3319. 第 K 大的完美二叉子树的大小

思路

定义二叉树的高度等于所有结点所在的不同层的数量，空二叉树的高度为 0，只有根结点的二叉树的高度为 1。根据完美二叉树的定义，高度为 h 的完美二叉树的大小是 2^h−1，因此可以首先寻找二叉树中的所有完美二叉子树的高度，然后根据第 k 大的完美二叉子树的高度计算其大小。

由于一个二叉树的高度取决于其子树的高度，因此可以使用 DFS 计算每个子树的高度，同时判断每个子树是否为完美二叉子树，使用列表记录所有完美二叉子树的高度。为了实现判断完美二叉子树，规定不是完美二叉子树的子树的高度为 −1。

DFS 结束之后，执行如下操作。

• 如果记录所有完美二叉子树的高度的列表中的元素个数小于 k，则不存在第 k 大的完美二叉子树，返回 −1。

• 如果记录所有完美二叉子树的高度的列表中的元素个数大于等于 k，则将记录所有完美二叉子树的高度的列表按降序排序，排序后返回第 k 大的元素，假设值为 h，则大小是 2^h−1。

代码

/** @lc app=leetcode.cn id=3319 lang=cpp** [3319] 第 K 大的完美二叉子树的大小*/// @lc code=start
/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution
{
public:int kthLargestPerfectSubtree(TreeNode *root, int k){// 完美二叉子树的高度vector<int> heights;function<int(TreeNode *)> dfs = [&](TreeNode *root){if (root == nullptr)return 0;int leftHeight = dfs(root->left);int rightHeight = dfs(root->right);if (leftHeight < 0 || rightHeight < 0 || leftHeight != rightHeight)return -1;int height = leftHeight + 1;heights.push_back(height);return height;};dfs(root);if (heights.size() < k)return -1;sort(heights.begin(), heights.end(), greater<int>());// 设完美二叉树的高度为 h，其大小为 2^h-1return (1 << heights[k - 1]) - 1;}
};
// @lc code=end

复杂度分析

时间复杂度：O(n)，其中 n 是二叉树的结点数。每个结点都被访问一次。

空间复杂度：O(n)，其中 n 是二叉树的结点数。空间复杂度主要是递归调用的栈空间，取决于二叉树的高度，最差情况下二叉树的高度是 O(n)。

题目3：

思路

定义状态为 dfs(i,j,ban)，表示从 i 到 0，在我们与对手的得分之差为 j 且第 i 回合我们无法召唤的生物为 ban 的前提下，战胜对手的不同出招序列的数量。

递归边界：

• 如果 −j>i，即使后面全胜，也无法战胜对手，返回 0。
• 如果 j>i+1，即使后面全败，也一定能战胜对手。由于剩余 i+1 个回合，每个回合在两个可以召唤的生物中随意选择，所以方案数为 2ⁱ⁺¹。

代码

#
# @lc app=leetcode.cn id=3320 lang=python3
#
# [3320] 统计能获胜的出招序列数
## @lc code=start
class Solution:def countWinningSequences(self, s: str) -> int:MOD = 1_000_000_007def getScore(a: str, b: str) -> int:if a == "F" and b == "W":return 1if b == "F" and a == "W":return -1if a == "W" and b == "E":return 1if b == "W" and a == "E":return -1if a == "E" and b == "F":return 1if b == "E" and a == "F":return -1return 0@cachedef dfs(i: int, j: int, ban: int) -> int:if -j > i:  # 必败return 0if j > i + 1:  # 必胜return pow(2, i + 1, MOD)res = 0for cur in "FWE":if cur == ban:continuescore = getScore(s[i], cur)res += dfs(i - 1, j + score, cur)return res % MODreturn dfs(len(s) - 1, 0, -1)# @lc code=end

复杂度分析

时间复杂度：O(n²K²)，其中 n 为字符串 s 的长度，K=3。

空间复杂度：O(n²K)，其中 n 为字符串 s 的长度，K=3。

题目4：3321. 计算子数组的 x-sum II

思路

题解：https://leetcode.cn/problems/find-x-sum-of-all-k-long-subarrays-ii/solutions/2948867/liang-ge-you-xu-ji-he-wei-hu-qian-x-da-p-2rcz/

代码

/** @lc app=leetcode.cn id=3321 lang=cpp** [3321] 计算子数组的 x-sum II*/// @lc code=start
class Solution
{
private:using pii = pair<int, int>; // 出现次数，元素值public:vector<long long> findXSum(const vector<int> &nums, int k, int x){int n = nums.size();set<pii> L, R;long long sum_l = 0; // L 的元素和unordered_map<int, int> cnt;auto add = [&](int x){pii p = {cnt[x], x};if (p.first == 0){return;}if (!L.empty() && p > *L.begin()){ // p 比 L 中最小的还大sum_l += (long long)p.first * p.second;L.insert(p);}elseR.insert(p);};auto del = [&](int x){pii p = {cnt[x], x};if (p.first == 0){return;}auto it = L.find(p);if (it != L.end()){sum_l -= (long long)p.first * p.second;L.erase(it);}elseR.erase(p);};auto l2r = [&](){pii p = *L.begin();sum_l -= (long long)p.first * p.second;L.erase(p);R.insert(p);};auto r2l = [&](){pii p = *R.rbegin();sum_l += (long long)p.first * p.second;R.erase(p);L.insert(p);};vector<long long> ans(n - k + 1);for (int r = 0; r < n; r++){// 添加 inint in = nums[r];del(in);cnt[in]++;add(in);int l = r + 1 - k;if (l < 0)continue;// 维护大小while (!R.empty() && L.size() < x)r2l();while (L.size() > x)l2r();ans[l] = sum_l;// 移除 outint out = nums[l];del(out);cnt[out]--;add(out);}return ans;}
};
// @lc code=end

复杂度分析

时间复杂度：O(nlogk)，其中 n 是数组 nums 的长度。

空间复杂度：O(n)，其中 n 是数组 nums 的长度。