👨‍🎓作者简介：爱好技术和算法的研究生
🌌上期文章：力扣周赛：第415场周赛
📚订阅专栏：力扣周赛
希望文章对你们有所帮助

因为一些特殊原因，这场比赛就打了1h，所以只AC了前面两题。第三题后面补题自己AC了，第三个居然是个hard题，居然暴力+记忆化就AC了。第四题不会做，面试机试也不会考这么难的，第四题就不补了。

计算子数组的 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;}
}