力扣周赛：第419场周赛
👨🎓作者简介：爱好技术和算法的研究生
🌌上期文章：力扣周赛：第415场周赛
📚订阅专栏：力扣周赛
希望文章对你们有所帮助
因为一些特殊原因，这场比赛就打了1h，所以只AC了前面两题。第三题后面补题自己AC了，第三个居然是个hard题，居然暴力+记忆化就AC了。第四题不会做，面试机试也不会考这么难的，第四题就不补了。
力扣周赛：第419场周赛
- 计算子数组的 x-sum I
- 第 K 大的完美二叉子树的大小
- 统计能获胜的出招序列数
计算子数组的 x-sum I
题目描述
给你一个由 n 个整数组成的数组 nums，以及两个整数 k 和 x。
数组的 x-sum 计算按照以下步骤进行：
统计数组中所有元素的出现次数。
仅保留出现次数最多的前 x 个元素的每次出现。如果两个元素的出现次数相同，则数值 较大 的元素被认为出现次数更多。
计算结果数组的和。
注意，如果数组中的不同元素少于 x 个，则其 x-sum 是数组的元素总和。
返回一个长度为 n - k + 1 的整数数组 answer，其中 answer[i] 是 子数组 nums[i..i + k - 1] 的 x-sum。
子数组 是数组内的一个连续 非空 的元素序列。
示例1
输入：nums = [1,1,2,2,3,4,2,3], k = 6, x = 2
输出：[6,10,12]
解释：
对于子数组 [1, 1, 2, 2, 3, 4]，只保留元素 1 和 2。因此，answer[0] = 1 + 1 + 2 + 2。
对于子数组 [1, 2, 2, 3, 4, 2]，只保留元素 2 和 4。因此，answer[1] = 2 + 2 + 2 + 4。注意 4 被保留是因为其数值大于出现其他出现次数相同的元素（3 和 1）。
对于子数组 [2, 2, 3, 4, 2, 3]，只保留元素 2 和 3。因此，answer[2] = 2 + 2 + 2 + 3 + 3。
示例2
输入：nums = [3,8,7,8,7,5], k = 2, x = 2
输出：[11,15,15,15,12]
解释：
由于 k == x，answer[i] 等于子数组 nums[i…i + k - 1] 的总和。
提示
- 1 <= n == nums.length <= 50
- 1 <= nums[i] <= 50
- 1 <= x <= k <= nums.length
这种数据量直接暴力就行了，在循环中用数组来记录子数组中各个元素的出现次数。
class Solution {
public int[] findXSum(int[] nums, int k, int x) {
int n = nums.length, pos = 0;
int[] ans = new int[n - k + 1];
for(int i = 0; i <= n - k; ++i){
int[] count1 = new int[55];
int[] count2 = new int[55];
int[] vis = new int[55];
int sum = 0;
for(int j = i; j < i + k; ++j){
count1[nums[j]]++; count2[nums[j]]++;
}
Arrays.sort(count1);
for(int j = 0; j < x; ++j){
int count = count1[54 - j];
//System.out.println(count);
for(int l = 50; l >= 1; --l){
if(count2[l] == count && vis[l] == 0){
vis[l] = 1;
sum += l * count;
break;
}
}
}
ans[pos++] = sum;
}
return ans;
}
}
第 K 大的完美二叉子树的大小
题目描述
给你一棵 二叉树 的根节点 root 和一个整数k。
返回第 k 大的 完美二叉
子树
的大小，如果不存在则返回 -1。
完美二叉树 是指所有叶子节点都在同一层级的树，且每个父节点恰有两个子节点。
子树 是指树中的某一个节点及其所有后代形成的树。
示例1
输入： root = [5,3,6,5,2,5,7,1,8,null,null,6,8], k = 2
输出： 3
解释：
完美二叉子树的根节点在图中以黑色突出显示。它们的大小按降序排列为 [3, 3, 1, 1, 1, 1, 1, 1]。
第 2 大的完美二叉子树的大小是 3。
示例2
输入： root = [1,2,3,4,5,6,7], k = 1
输出： 7
解释：
完美二叉子树的大小按降序排列为 [7, 3, 3, 1, 1, 1, 1]。最大的完美二叉子树的大小是 7。
示例3
输入： root = [1,2,3,null,4], k = 3
输出： -1
解释：
完美二叉子树的大小按降序排列为 [1, 1]。完美二叉子树的数量少于 3。
提示
- 树中的节点数目在 [1, 2000] 范围内。
- 1 <= Node.val <= 2000
- 1 <= k <= 1024
显然就是个dfs题，另外可以发现，只要是一个完美二叉树，那么它的节点数量为
2^h - 1，其中h为树高，所以我们只需要dfs并且维护这个树高，最后对树高从大到小进行排序后计算即可。
需要考虑的点是，不符合完美二叉树的那些情况，有如下2点情况：
（1）左右子树中有任意一个子树不是完美二叉树。
（2）左右子树虽然都是完美二叉树，但是树高不同。
所以思路很明确，我们只需要用一个可变长度的数组来记录完美二叉树的树高，并且递归遍历，如果不符合完美二叉树则直接返回-1。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int kthLargestPerfectSubtree(TreeNode root, int k) {
List<Integer> h = new ArrayList<>();
dfs(root, h);
if(k > h.size()){
return -1;
}
Collections.sort(h, (o1, o2) -> o2.compareTo(o1));//用了lambda表达式
//System.out.println(h);
return (1 << h.get(k - 1)) - 1;
}
public int dfs(TreeNode root, List<Integer> h){
if(root == null){
return 0;
}
int l = dfs(root.left, h), r = dfs(root.right, h);
if(l == -1 || r == -1 || l != r){
//左右子树中存在非完美二叉树，或者左右的完美二叉树的树高不同，那么以该结点为父节点的树就不是完美二叉树
return -1;
}
h.add(l + 1);//是完美二叉树就记录树高
return l + 1;
}
}
统计能获胜的出招序列数
题目描述
Alice 和 Bob 正在玩一个幻想战斗游戏，游戏共有 n 回合，每回合双方各自都会召唤一个魔法生物：火龙（F）、水蛇（W）或地精（E）。每回合中，双方 同时 召唤魔法生物，并根据以下规则得分：
-
如果一方召唤火龙而另一方召唤地精，召唤 火龙 的玩家将获得一分。
-
如果一方召唤水蛇而另一方召唤火龙，召唤 水蛇 的玩家将获得一分。
-
如果一方召唤地精而另一方召唤水蛇，召唤 地精 的玩家将获得一分。
-
如果双方召唤相同的生物，那么两个玩家都不会获得分数。
给你一个字符串 s，包含 n 个字符 ‘F’、‘W’ 和 ‘E’，代表 Alice 每回合召唤的生物序列： -
如果 s[i] == ‘F’，Alice 召唤火龙。
-
如果 s[i] == ‘W’，Alice 召唤水蛇。
-
如果 s[i] == ‘E’，Alice 召唤地精。
Bob 的出招序列未知，但保证 Bob 不会在连续两个回合中召唤相同的生物。如果在 n 轮后 Bob 获得的总分 严格大于 Alice 的总分，则 Bob 战胜 Alice。
返回 Bob 可以用来战胜 Alice 的不同出招序列的数量。
由于答案可能非常大，请返回答案对 10^9 + 7 取余 后的结果。
示例1
输入： s = “FFF”
输出： 3
解释：
Bob 可以通过以下 3 种出招序列战胜 Alice：“WFW”、“FWF” 或 “WEW”。注意，其他如 “WWE” 或 “EWW” 的出招序列是无效的，因为 Bob 不能在连续两个回合中使用相同的生物。
示例2
输入： s = “FWEFW”
输出： 18
解释：
Bob 可以通过以下出招序列战胜 Alice：“FWFWF”、“FWFWE”、“FWEFE”、“FWEWE”、“FEFWF”、“FEFWE”、“FEFEW”、“FEWFE”、“WFEFE”、“WFEWE”、“WEFWF”、“WEFWE”、“WEFEF”、“WEFEW”、“WEWFW”、“WEWFE”、“EWFWE” 或 “EWEWE”。
提示
- 1 <= s.length <= 1000
- s[i] 是 ‘F’、‘W’ 或 ‘E’ 中的一个。
这道题居然能是hard，难以想象，整得我还以为这题这题肯定是要DP优化的，结果数据量这么小的。不过需要注意的是f数组不要开始就定义，不然可能会爆了。
f[i][j][k]表示当前位置为i，Alice选用的魔法生物是j(0<=j<3)且此时的分差为k的时候，Bob赢Alice的方案数，但是需要注意的是，这个k可能是负数，所以记录的时候要小心，使用f[i][j][k + len]，防止数组越界。
class Solution {
int[][][] f;
public int countWinningSequences(String s) {
int len = s.length();
f = new int[len][3][2 * len + 1];
for(int i = 0; i < len; ++i){
for(int j = 0; j < 3; ++j){
Arrays.fill(f[i][j], -1);
}
}
return dfs(s, -1, -1, 0, len);
}
public int dfs(String s, int i, int j, int k, int len){
if(k < 0 && (len - i) < -1 * k) return 0;
if(i >= 0 && f[i][j][k + len] != -1) return f[i][j][k + len];
if(i == len - 1){
return k > 0 ? 1 : 0;
}
int res = 0;
for(int x = 0; x < 3; ++x){
if(x != j){
int sc = calculate(s, i + 1, x);
res = (res + dfs(s, i + 1, x, k + sc, len)) % (int)(1e9 + 7);
}
}
if(i > 0){
f[i][j][k + len] = res;
}
return res;
}
public int calculate(String s, int i, int x){
char c = s.charAt(i);
if(c == 'F' && x == 0 || c == 'W' && x == 1 || c == 'E' && x == 2)return 0;
if(c == 'F' && x == 1 || c == 'W' && x == 2 || c == 'E' && x == 0)return 1;
return -1;
}
}