Leetcode - 周赛419
目录
一，3318. 计算子数组的 x-sum I
二，3319. 第 K 大的完美二叉子树的大小
三，3320. 统计能获胜的出招序列数
四，3321. 计算子数组的 x-sum II
一，3318. 计算子数组的 x-sum I
本题数据范围较小，可以使用滑动窗口计算子数组nums[i，i+k-1]中每个数字出现的次数，然后使用堆计算出现次数最多的前x个元素，计算出当前的x - sum，代码如下：
class Solution {public int[] findXSum(int[] nums, int k, int x) {int n = nums.length;int[] ans = new int[n-k+1];int[] cnt = new int[51];for(int l=0,r=0; r<n; r++){cnt[nums[r]]++;while(r-l+1 > k){cnt[nums[l]]--;l++;}if(r-l+1 == k){PriorityQueue<int[]> que = new PriorityQueue<>((a,b)->a[1]==b[1]?a[0]-b[0]:a[1]-b[1]);for(int i=0; i<51; i++){if(cnt[i] > 0)que.offer(new int[]{i, cnt[i]});if(que.size() > x){que.poll();}}while(!que.isEmpty()){int[] t = que.poll();ans[l] += t[0] * t[1];}} }return ans;}
}二，3319. 第 K 大的完美二叉子树的大小
本题是一道二叉树问题，主要就是如何判断该树/子树是一颗完全二叉树？如果一个树它的左右两颗子树都是完全二叉树，那么它一定是完全二叉树吗？不一定拿示例一来说，对于节点3/6来说，它们的子树都是完全二叉树，但是以节点3/6为根节点的树不是完全二叉树，因为它们左右子树的节点数量不同（也可以说是它们的高度不同，因为完全二叉树的形状是固定的），所以在判断它是否是完全二叉树时，有两个条件：1、它的左右子树是完全二叉树；2、它的左右子树的节点数量相同/高度相同。
代码如下：
class Solution {List<Integer> ans = new ArrayList<>();public int kthLargestPerfectSubtree(TreeNode root, int k) {dfs(root);Collections.sort(ans);int n = ans.size();return n >= k?ans.get(n-k):-1;}//左右子树节点数相同的写法int dfs(TreeNode root){if(root == null) return 0;int left = dfs(root.left) + 1;int right = dfs(root.right) + 1;if(left > 0 && left == right){ans.add(left*2-1);}else{return -1;}return left + right - 1;}
}class Solution {List<Integer> ans = new ArrayList<>();public int kthLargestPerfectSubtree(TreeNode root, int k) {dfs(root);Collections.sort(ans);int n = ans.size();if(k > n) return -1;return (1 << ans.get(n-k)) - 1;}//左右子树高度相同的写法int dfs(TreeNode root){if(root == null) return 0;int left = dfs(root.left);int right = dfs(root.right);if(left < 0 || right < 0 || left != right) return -1;ans.add(left + 1);return left + 1;}
}三，3320. 统计能获胜的出招序列数
本题就是一道dfs记忆化的题，将 FWE 分别使用 012 表示（方便记忆化），简单来说就是枚举Bob每一种出招顺序，然后判断得分能否大于Alice，dfs枚举需要知道当前是第几回合(i)，Bob前一次召唤的生物(k)，以及两者的得分之差(j)。dfs(i，j，k)：前 i 个回合两者等分之差为 j，且前一回合Bob出招为 k 时的战胜对手的数量。
代码如下：
class Solution {//f w e : 0 1 2//f > e : 0 > 2//w > f : 1 > 0//e > w : 2 > 1public int countWinningSequences(String s) {int n = s.length();memo = new int[n][2*n+1][4];for(int i=0; i<n; i++){for(int j=0; j<2*n+1; j++)Arrays.fill(memo[i][j], -1);}return dfs(0, 0, 3, s.toCharArray());}int MOD = 1_000_000_007;int[][][] memo;int dfs(int i, int j, int k, char[] s){int n = s.length;if(-j > n - i - 1) return 0;if(i == n) return 1;if(memo[i][j+n][k] != -1) return memo[i][j+n][k];//防止越界，将所有j+nint res = 0;for(int x=0; x<3; x++){if(x == k) continue;int y = s[i]=='F'?0:s[i]=='W'?1:2;int cnt = x - y;if(Math.abs(cnt)==2) cnt = -cnt/2;res = (res + dfs(i+1, j+cnt, x, s))%MOD;}return memo[i][j+n][k] = res;}
}四，3321. 计算子数组的 x-sum II
本题就是使用两个有序集合分别维护nums[i，i+k-1]的中的出现次数最多的前 x 个元素（{出现次数，数字}）和剩下的其他元素，然后使用滑动窗口不断模拟元素进出时，两个有序集合如何操作，同时维护前一个有序集合的元素总和。
代码如下：
class Solution {TreeSet<int[]> L = new TreeSet<>((a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);TreeSet<int[]> R = new TreeSet<>(L.comparator());Map<Integer, Integer> cnt = new HashMap<>();long sumL = 0L;int x;public long[] findXSum(int[] nums, int k, int x) {int n = nums.length;long[] ans = new long[n-k+1];//出现次数最大、数最大this.x = x;for(int l=0,r=0; r<n; r++){remove(nums[r]);//将{key, val}排出cnt.merge(nums[r], 1, Integer::sum);add(nums[r]);//将{key+1, val}输入if(r-l+1 > k){remove(nums[l]);//将{key, val}排出cnt.merge(nums[l], -1, Integer::sum);add(nums[l]);//将{key-1, val}输入l++;}if(r-l+1 == k){ans[l] = sumL;} }return ans;}void add(int val){if(L.size() < x){L.add(new int[]{cnt.get(val), val});sumL += 1L * cnt.get(val) * val;return;}R.add(new int[]{cnt.get(val), val});int[] mx = R.getLast();int[] mn = L.getFirst();if(mx[0] > mn[0] || (mx[0]==mn[0] && mx[1] > mn[1])){sumL -= 1L * mn[0] * mn[1];sumL += 1L * mx[0] * mx[1];R.add(mn);L.remove(mn);L.add(mx);R.remove(mx);}}void remove(int val){if(cnt.getOrDefault(val, 0) == 0) return;int[] rem = new int[]{cnt.get(val), val};if(R.contains(rem)){R.remove(rem);return;}sumL -= 1L * rem[0] * rem[1];L.remove(rem);if(R.size() > 0){int[] res = R.getLast();L.add(res);sumL += 1L * res[0] * res[1];R.remove(res);}}
}