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;
}
}