题目列表
3318. 计算子数组的 x-sum I
3319. 第 K 大的完美二叉子树的大小
3320. 统计能获胜的出招序列数
3321. 计算子数组的 x-sum II
一、第 K 大的完美二叉子树的大小
求第 k 大的子树的大小，本质就是统计树中的完美二叉子树的大小，排序后返回第 k 个即可，关键是如何判断一棵树是完美二叉树？从递归的角度来思考：如果一棵树的左子树和右子树都是完美二叉树，那么它是完美二叉树吗？显然不是，我们还需要让它们的高度相同(即结点个数相同)，所以我们需要用pair返回两个值，一个表示树的高度(或者节点数)，一个表示是否是完美二叉树，代码如下
class Solution {
vector<int> ans;
pair<int,bool> dfs(TreeNode* root){
if(root == nullptr)
return {0, true};
auto [hl, isl] = dfs(root->left);
auto [hr, isr] = dfs(root->right);
bool flag = hl == hr && isl && isr;
if(flag){
ans.push_back((1<<(hl+1))-1); // 完美二叉树的大小为2^h-1
}
return {max(hl, hr) + 1, flag};
}
public:
int kthLargestPerfectSubtree(TreeNode* root, int k) {
dfs(root);
int n = ans.size();
ranges::sort(ans, greater<>());
return n < k ? -1 : ans[k-1];
}
};
// 当然也可以对状态进行压缩，用-1表示不是完美二叉树，这样只要返回一个值即可
class Solution {
vector<int> ans;
int dfs(TreeNode* root){
if(root == nullptr) // 预防空树的情况
return 0;
int hl = dfs(root->left);
int hr = dfs(root->right);
bool flag = hl == hr && hl >= 0 && hr >= 0;
if(flag){
ans.push_back((1<<(hl+1))-1); // 完美二叉树的大小为2^h-1
}
return flag ? hl + 1 : -1;
}
public:
int kthLargestPerfectSubtree(TreeNode* root, int k) {
dfs(root);
int n = ans.size();
ranges::sort(ans, greater<>());
return n < k ? -1 : ans[k-1];
}
};二、统计能获胜的出招序列数
上面的游戏规则，可以套用剪刀石头布去理解，现在给你Alice的出招序列，让你去查找Bob有多少种出招序列能赢，并且Bob不能连续两次出一样的。
这题很明显是个dp问题，我们令dfs(i, j, k)表示前 i 次战斗后，Alice和Bob的分值之差为 j 的所有可能排列数，其中 k 表示Bob第i-1次的出招（注意：这里我们只关注Alice和Bob的分差即可，因为我们只需要知道输赢，而不关注他们各自得了多少分），代码如下
class Solution {
const string t = "FWE";
const int MOD = 1e9 + 7;
public:
int countWinningSequences(string s) {
int n = s.size();
int memo[n][2001][4];
memset(memo, -1, sizeof(memo));
// 还能通过提前判断Bob必赢/必输来进行减枝，有兴趣可以试试
function<int(int,int,int)> dfs = [&](int i, int j, int k)->int{
if(i < 0) return j > 1000;// 为了让记忆化的下标不为负数，给了个1000作为偏移量
if(memo[i][j][k]!=-1) return memo[i][j][k];
int pos = t.find(s[i]);
int res = 0;
if(k != pos)
res = (res + dfs(i - 1, j, pos))%MOD; // 平局
if(k != (pos + 1) % 3)
res = (res + dfs(i - 1, j + 1, (pos + 1)%3))%MOD; // Bob赢
if(k != (pos + 2) % 3)
res = (res + dfs(i - 1, j - 1, (pos + 2)%3))%MOD; // Alice赢
return memo[i][j][k] = res;
};
return dfs(n - 1, 1000, 3);
}
};三、计算子数组的 x-sum I & II
本题的关键在于如何维护长度为 k 的子数组中出现次数最多的前 x 个元素，及它们的和。
这里提供一个思路：同时维护子数组中出现次数最多的前 x 个元素，和随着子数组的移动可能出现在前 x 个元素中的数字，简而言之，就是维护一个当前状态的前x个元素集合，和一个备用元素集合，这样只要当前状态的前x个元素集合缺少元素，就从备用元素集合中拿就行。
满足上诉要求的数据结构就是对顶堆，用大堆和小堆模拟上诉行为即可，但是库中的堆不支持任意的删除元素(该问题可以结合懒删除进行解决)，这里我们用 set 来代替堆实现，代码如下
class Solution {
public:
vector<long long> findXSum(vector<int>& nums, int k, int x) {
int n = nums.size();
unordered_map<int,int>mp;
set<pair<int, int>> stL, stR; // stL --- "现任" stR --- "备胎"
long long s = 0;
auto remove = [&](int i){
auto it = stR.find({mp[i], i});
if(it != stR.end()){
stR.erase(it);
return;
}
it = stL.find({mp[i], i});
if(it == stL.end()) return;
s -= 1LL*(it->first)*(it->second);
stL.erase(it);
if(stR.size()){
it = prev(stR.end());
stL.insert(*it);
s += 1LL*(it->first)*(it->second);
stR.erase(it);
}
};
auto add = [&](int i){
if(stL.size() < x){
stL.insert({mp[i], i});
s += 1LL * mp[i] * i;
return;
}
stR.insert({mp[i], i});
auto mx = prev(stR.end());
auto mn = stL.begin();
if(*mx > *mn){
s += 1LL*(mx->first)*(mx->second);
s -= 1LL*(mn->first)*(mn->second);
stR.insert(*mn);
stL.erase(mn);
stL.insert(*mx);
stR.erase(mx);
}
};
vector<long long> ans(n - k + 1);
for(int l = 0, r = 0; r < n; r++){
remove(nums[r]);
++mp[nums[r]];
add(nums[r]);
if(r - l + 1 > k){
remove(nums[l]);
--mp[nums[l]];
add(nums[l]);
l++;
}
if(r - l + 1 == k) ans[l] = s;
}
return ans;
}
};