5328. 方阵中战斗力最弱的 K 行
给你一个大小为 m * n 的方阵 mat，方阵由若干军人和平民组成，分别用 0 和 1 表示。
请你返回方阵中战斗力最弱的 k 行的索引，按从最弱到最强排序。
如果第 i 行的军人数量少于第 j 行，或者两行军人数量相同但 i 小于 j，那么我们认为第 i 行的战斗力比第 j 行弱。
军人 总是 排在一行中的靠前位置，也就是说 1 总是出现在 0 之前。
示例 1：
输入：mat =
[[1,1,0,0,0],
[1,1,1,1,0],
[1,0,0,0,0],
[1,1,0,0,0],
[1,1,1,1,1]],
k = 3
输出：[2,0,3]
解释：
每行中的军人数目：
行 0 -> 2
行 1 -> 4
行 2 -> 1
行 3 -> 2
行 4 -> 5
从最弱到最强对这些行排序后得到 [2,0,3,1,4]
示例 2：
输入：mat =
[[1,0,0,0],
[1,1,1,1],
[1,0,0,0],
[1,0,0,0]],
k = 2
输出：[0,2]
解释：
每行中的军人数目：
行 0 -> 1
行 1 -> 4
行 2 -> 1
行 3 -> 1
从最弱到最强对这些行排序后得到 [0,2,3,1]
提示：
m == mat.length
n == mat[i].length
2 <= n, m <= 100
1 <= k <= m
matrix[i][j] 不是 0 就是 1
思路
代码中可以进行的优化（比赛时间紧张因此没有在代码的时间复杂度上做优化）：
- 在方阵的一行求军人个数可以用二分查找求最后一个军人的位置
- 用长度为k的最大堆或长度为n的最小堆，求最小的k个行：如果用长度为k的最大堆，则复杂度为O(nlogk)；如果用长度为n的最小堆，则复杂度为O(n + klogn)
代码
class Solution {
private class Row implements Comparable<Row> {
public int row, armies;
public Row(int row, int armies) {
this.row = row;
this.armies = armies;
}
@Override
public int compareTo(Row other) {
if (this.armies == other.armies) {
return this.row - other.row;
} else {
return this.armies - other.armies;
}
}
}
public int[] kWeakestRows(int[][] mat, int k) {
int n = mat.length, m = mat[0].length, i = 0, j = 0;
Row[] rows = new Row[n];
int[] ans = new int[k];
for (i=0; i<n; ++i) {
rows[i] = new Row(i, m);
for (j=0; j<m; ++j) {
if (mat[i][j] == 0) {
rows[i] = new Row(i, j);
break;
}
}
}
Arrays.sort(rows);
for (i=0; i<k; ++i) {
ans[i] = rows[i].row;
}
return ans;
}
}
5329. 数组大小减半
给你一个整数数组 arr。你可以从中选出一个整数集合，并删除这些整数在数组中的每次出现。
返回 至少 能删除数组中的一半整数的整数集合的最小大小。
示例 1：
输入：arr = [3,3,3,3,5,5,5,2,2,7]
输出：2
解释：选择 {3,7} 使得结果数组为 [5,5,5,2,2]、长度为 5（原数组长度的一半）。
大小为 2 的可行集合有 {3,5},{3,2},{5,2}。
选择 {2,7} 是不可行的，它的结果数组为 [3,3,3,3,5,5,5]，新数组长度大于原数组的二分之一。
示例 2：
输入：arr = [7,7,7,7,7,7]
输出：1
解释：我们只能选择集合 {7}，结果数组为空。
示例 3：
输入：arr = [1,9]
输出：1
示例 4：
输入：arr = [1000,1000,3,7]
输出：1
示例 5：
输入：arr = [1,2,3,4,5,6,7,8,9,10]
输出：5
提示：
1 <= arr.length <= 10^5
arr.length 为偶数
1 <= arr[i] <= 10^5
思路
用HashMap统计所有数字出现的次数，然后按次数sort，从出现次数大的开始找
代码
class Solution {
private class Number implements Comparable<Number> {
public int val, cnt;
public Number(int val, int cnt) {
this.val = val;
this.cnt = cnt;
}
@Override
public int compareTo(Number other) {
return other.cnt - this.cnt;
}
}
public int minSetSize(int[] arr) {
int len = arr.length, half = len % 2 == 0? (len / 2): (len/2 + 1);
HashMap<Integer, Integer> cnts = new HashMap<>();
for (int a: arr) {
if (cnts.containsKey(a)) {
cnts.put(a, cnts.get(a) + 1);
} else {
cnts.put(a, 1);
}
}
int n = cnts.size(), counter = 0, i = 0;
Number[] nums = new Number[n];
for (Map.Entry<Integer, Integer> entry: cnts.entrySet()) {
nums[counter++] = new Number(entry.getKey(), entry.getValue());
}
Arrays.sort(nums);
counter = 0;
for (i=0; i<n; ++i) {
counter += nums[i].cnt;
if (counter >= half) {
return i+1;
}
}
return n;
}
}
5330. 分裂二叉树的最大乘积
给你一棵二叉树，它的根为 root 。请你删除 1 条边，使二叉树分裂成两棵子树，且它们子树和的乘积尽可能大。
由于答案可能会很大，请你将结果对 10^9 + 7 取模后再返回。
示例 1：
输入：root = [1,2,3,4,5,6]
输出：110
解释：删除红色的边，得到 2 棵子树，和分别为 11 和 10 。它们的乘积是 110 （11*10）
示例 2：
输入：root = [1,null,2,3,4,null,null,5,6]
输出：90
解释：移除红色的边，得到 2 棵子树，和分别是 15 和 6 。它们的乘积为 90 （15*6）
示例 3：
输入：root = [2,3,9,10,7,8,6,5,4,11,1]
输出：1025
示例 4：
输入：root = [1,1]
输出：1
提示：
每棵树最多有 50000 个节点，且至少有 2 个节点。
每个节点的值在 [1, 10000] 之间。
思路
树的总和是固定的，要使乘积最大，问题转化为求子树和，使得该子树和最接近总和的一半。具体做法是将所有子树和放在一个数组中，顺序查找。
注意最后的long和int之间的类型转换。
代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private static final long mod = 1000000007L;
private ArrayList<Integer> sums = new ArrayList<>();
private int sumTree(TreeNode root) {
if (root == null) {
return 0;
}
int ans = root.val + sumTree(root.left) + sumTree(root.right);
sums.add(ans);
return ans;
}
/**
* If same distance, pick the larger one
*/
private int getNearest(ArrayList<Integer> arr, int target) {
int minDis = Integer.MAX_VALUE, nearestVal = 0;
for (int a: arr) {
int tmp = Math.abs(a - target);
if (tmp < minDis) {
minDis = tmp;
nearestVal = a;
} else if (tmp == minDis) {
if (a > target) {
nearestVal = a;
}
}
}
return nearestVal;
}
public int maxProduct(TreeNode root) {
int total = sumTree(root), half = total/2, nearest = getNearest(sums, half);
return (int)((((long)nearest) % mod) * (((long)(total - nearest)) % mod) % mod);
}
}
5331. 跳跃游戏 V
给你一个整数数组 arr 和一个整数 d 。每一步你可以从下标 i 跳到：
i + x ，其中 i + x < arr.length 且 0 < x <= d 。
i - x ，其中 i - x >= 0 且 0 < x <= d 。
除此以外，你从下标 i 跳到下标 j 需要满足：arr[i] > arr[j] 且 arr[i] > arr[k] ，其中下标 k 是所有 i 到 j 之间的数字（更正式的，min(i, j) < k < max(i, j)）。
你可以选择数组的任意下标开始跳跃。请你返回你 最多 可以访问多少个下标。
请注意，任何时刻你都不能跳到数组的外面。
示例 1：
输入：arr = [6,4,14,6,8,13,9,7,10,6,12], d = 2
输出：4
解释：你可以从下标 10 出发，然后如上图依次经过 10 --> 8 --> 6 --> 7 。
注意，如果你从下标 6 开始，你只能跳到下标 7 处。你不能跳到下标 5 处因为 13 > 9 。你也不能跳到下标 4 处，因为下标 5 在下标 4 和 6 之间且 13 > 9 。
类似的，你不能从下标 3 处跳到下标 2 或者下标 1 处。
示例 2：
输入：arr = [3,3,3,3,3], d = 3
输出：1
解释：你可以从任意下标处开始且你永远无法跳到任何其他坐标。
示例 3：
输入：arr = [7,6,5,4,3,2,1], d = 1
输出：7
解释：从下标 0 处开始，你可以按照数值从大到小，访问所有的下标。
示例 4：
输入：arr = [7,1,7,1,7,1], d = 2
输出：2
示例 5：
输入：arr = [66], d = 1
输出：1
提示：
1 <= arr.length <= 1000
1 <= arr[i] <= 10^5
1 <= d <= arr.length
思路
记忆化搜索。搜索之前计算每一个点出发可以跳到的左边界
left
和右边界
right
代码
class Solution {
private void jump(int[] dp, int[] left, int[] right, boolean[] vis, int n, int d, int cur) {
if (vis[cur]) {
return;
}
int addi = 0;
vis[cur] = true;
for (int i=left[cur]; i<=right[cur]; ++i) {
if (i == cur) {
continue;
}
if (vis[i]) {
addi = Math.max(addi, dp[i]);
} else {
jump(dp, left, right, vis, n, d, i);
addi = Math.max(addi, dp[i]);
}
}
dp[cur] += addi;
}
private void calBounds(int[] arr, int[] left, int[] right, int d) {
int n = arr.length, i = 0, j = 0;
for (i=0; i<n; ++i) {
int begin = Math.max(0, i - d), end = Math.min(n - 1, i + d);
left[i] = begin;
right[i] = end;
for (j=i+1; j<=end; ++j) {
if (arr[i] <= arr[j]) {
right[i] = j - 1;
break;
}
}
for (j=i-1; j>=begin; --j) {
if (arr[i] <= arr[j]) {
left[i] = j + 1;
break;
}
}
}
}
public int maxJumps(int[] arr, int d) {
int n = arr.length;
int[] dp = new int[n], left = new int[n], right = new int[n];
calBounds(arr, left, right, d);
boolean[] vis = new boolean[n];
Arrays.fill(dp, 1);
for (int i=0; i<n; ++i) {
jump(dp, left, right, vis, n, d, i);
}
int maxVal = 1;
for (int val: dp) {
if (val > maxVal) {
maxVal = val;
}
}
return maxVal;
}
}