某网站注册需要邮箱是怎么弄,网站培训,10000ip网站怎么做,东莞保安公司有多少家目录
一#xff0c;3318. 计算子数组的 x-sum I
二#xff0c;3319. 第 K 大的完美二叉子树的大小
三#xff0c;3320. 统计能获胜的出招序列数
四#xff0c;3321. 计算子数组的 x-sum II 一#xff0c;3318. 计算子数组的 x-sum I 本题数据范围较小#xff0c;可以…目录
一3318. 计算子数组的 x-sum I
二3319. 第 K 大的完美二叉子树的大小
三3320. 统计能获胜的出招序列数
四3321. 计算子数组的 x-sum II 一3318. 计算子数组的 x-sum I 本题数据范围较小可以使用滑动窗口计算子数组nums[iik-1]中每个数字出现的次数然后使用堆计算出现次数最多的前x个元素计算出当前的x - sum代码如下
class Solution {public int[] findXSum(int[] nums, int k, int x) {int n nums.length;int[] ans new int[n-k1];int[] cnt new int[51];for(int l0,r0; rn; r){cnt[nums[r]];while(r-l1 k){cnt[nums[l]]--;l;}if(r-l1 k){PriorityQueueint[] que new PriorityQueue((a,b)-a[1]b[1]?a[0]-b[0]:a[1]-b[1]);for(int i0; i51; 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 {ListInteger 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 {ListInteger 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每一种出招顺序然后判断得分能否大于Alicedfs枚举需要知道当前是第几回合(i)Bob前一次召唤的生物(k)以及两者的得分之差(j)。dfs(ijk)前 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*n1][4];for(int i0; in; i){for(int j0; j2*n1; 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][jn][k] ! -1) return memo[i][jn][k];//防止越界将所有jnint res 0;for(int x0; x3; 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(i1, jcnt, x, s))%MOD;}return memo[i][jn][k] res;}
}
四3321. 计算子数组的 x-sum II 本题就是使用两个有序集合分别维护nums[iik-1]的中的出现次数最多的前 x 个元素{出现次数数字}和剩下的其他元素然后使用滑动窗口不断模拟元素进出时两个有序集合如何操作同时维护前一个有序集合的元素总和。
代码如下
class Solution {TreeSetint[] L new TreeSet((a, b) - a[0] ! b[0] ? a[0] - b[0] : a[1] - b[1]);TreeSetint[] R new TreeSet(L.comparator());MapInteger, 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-k1];//出现次数最大、数最大this.x x;for(int l0,r0; rn; r){remove(nums[r]);//将{key, val}排出cnt.merge(nums[r], 1, Integer::sum);add(nums[r]);//将{key1, val}输入if(r-l1 k){remove(nums[l]);//将{key, val}排出cnt.merge(nums[l], -1, Integer::sum);add(nums[l]);//将{key-1, val}输入l;}if(r-l1 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);}}
}
