Leetcode 第 419 场周赛题解
Leetcode 第 419 场周赛题解
- Leetcode 第 419 场周赛题解
- 题目1：3318. 计算子数组的 x-sum I
- 思路
- 代码
- 复杂度分析
- 题目2：3319. 第 K 大的完美二叉子树的大小
- 思路
- 代码
- 复杂度分析
- 题目3：
- 思路
- 代码
- 复杂度分析
- 题目4：3321. 计算子数组的 x-sum II
- 思路
- 代码
- 复杂度分析
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;
else
return 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 的完美二叉树的大小是 2h−1，因此可以首先寻找二叉树中的所有完美二叉子树的高度，然后根据第 k 大的完美二叉子树的高度计算其大小。
由于一个二叉树的高度取决于其子树的高度，因此可以使用 DFS 计算每个子树的高度，同时判断每个子树是否为完美二叉子树，使用列表记录所有完美二叉子树的高度。为了实现判断完美二叉子树，规定不是完美二叉子树的子树的高度为 −1。
DFS 结束之后，执行如下操作。
-
如果记录所有完美二叉子树的高度的列表中的元素个数小于 k，则不存在第 k 大的完美二叉子树，返回 −1。
-
如果记录所有完美二叉子树的高度的列表中的元素个数大于等于 k，则将记录所有完美二叉子树的高度的列表按降序排序，排序后返回第 k 大的元素，假设值为 h，则大小是 2h−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-1
return (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 个回合，每个回合在两个可以召唤的生物中随意选择，所以方案数为 2i+1。
代码
#
# @lc app=leetcode.cn id=3320 lang=python3
#
# [3320] 统计能获胜的出招序列数
#
# @lc code=start
class Solution:
def countWinningSequences(self, s: str) -> int:
MOD = 1_000_000_007
def getScore(a: str, b: str) -> int:
if a == "F" and b == "W":
return 1
if b == "F" and a == "W":
return -1
if a == "W" and b == "E":
return 1
if b == "W" and a == "E":
return -1
if a == "E" and b == "F":
return 1
if b == "E" and a == "F":
return -1
return 0
@cache
def dfs(i: int, j: int, ban: int) -> int:
if -j > i: # 必败
return 0
if j > i + 1: # 必胜
return pow(2, i + 1, MOD)
res = 0
for cur in "FWE":
if cur == ban:
continue
score = getScore(s[i], cur)
res += dfs(i - 1, j + score, cur)
return res % MOD
return dfs(len(s) - 1, 0, -1)
# @lc code=end
复杂度分析
时间复杂度：O(n2K2)，其中 n 为字符串 s 的长度，K=3。
空间复杂度：O(n2K)，其中 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);
}
else
R.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);
}
else
R.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++)
{
// 添加 in
int 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;
// 移除 out
int out = nums[l];
del(out);
cnt[out]--;
add(out);
}
return ans;
}
};
// @lc code=end
复杂度分析
时间复杂度：O(nlogk)，其中 n 是数组 nums 的长度。
空间复杂度：O(n)，其中 n 是数组 nums 的长度。