欢迎大家加QQ群：623375442，可以方便群里面交流。人不会做第四题，然后赛后试了AI的答案 prompt几次就能过。AI也太强了。
100571. Choose K Elements With Maximum Sum
给你两个整数数组，nums1 和 nums2，长度均为 n，以及一个正整数 k 。
对从 0 到 n - 1 每个下标 i ，执行下述操作：
- 找出所有满足 nums1[j] 小于 nums1[i] 的下标 j 。
- 从这些下标对应的 nums2[j] 中选出 至多 k 个，并 最大化 这些值的总和作为结果。
返回一个长度为 n 的数组 answer ，其中 answer[i] 表示对应下标 i 的结果。
测试样例：
输入：nums1 = [4,2,1,5,3], nums2 = [10,20,30,40,50], k = 2
输出：[80,30,0,80,50]
解释：
- 对于 i = 0 ：满足 nums1[j] < nums1[0] 的下标为 [1, 2, 4] ，选出其中值最大的两个，结果为 50 + 30 = 80 。
- 对于 i = 1 ：满足 nums1[j] < nums1[1] 的下标为 [2] ，只能选择这个值，结果为 30 。
- 对于 i = 2 ：不存在满足 nums1[j] < nums1[2] 的下标，结果为 0 。
- 对于 i = 3 ：满足 nums1[j] < nums1[3] 的下标为 [0, 1, 2, 4] ，选出其中值最大的两个，结果为 50 + 30 = 80 。
- 对于 i = 4 ：满足 nums1[j] < nums1[4] 的下标为 [1, 2] ，选出其中值最大的两个，结果为 30 + 20 = 50 。
解答：这题排序一下，从小到大遍历数组即可。用优先队列记录一下过程。
class Solution {
public long[] findMaxSum(int[] nums1, int[] nums2, int k) {
Integer[] sort = new Integer[nums1.length];
for (int i = 0; i < nums1.length; ++i) {
sort[i] = i;
}
Arrays.sort(sort, (a, b) -> (Integer.compare(nums1[a], nums1[b])));
PriorityQueue<Integer> queue = new PriorityQueue<>();
List<Integer> buffer = new ArrayList<>();
int last = -1;
long sum = 0;
long[] res = new long[nums1.length];
for (int i : sort) {
if (nums1[i] != last) {
for (int n : buffer) {
queue.add(nums2[n]);
sum += nums2[n];
if (queue.size() > k) {
sum -= queue.poll();
}
}
buffer = new ArrayList<>();
}
res[i] = sum;
last = nums1[i];
buffer.add(i);
}
return res;
}
}
100601. Fruits Into Baskets III
给你两个长度为 n 的整数数组，fruits 和 baskets，其中 fruits[i] 表示第 i 种水果的 数量，baskets[j] 表示第 j 个篮子的 容量。
你需要对 fruits 数组从左到右按照以下规则放置水果：
- 每种水果必须放入第一个 容量大于等于 该水果数量的 最左侧可用篮子 中。
- 每个篮子只能装 一种 水果。
- 如果一种水果 无法放入 任何篮子，它将保持 未放置。
返回所有可能分配完成后，剩余未放置的水果种类的数量。
测试样例：
输入：fruits = [4,2,5], baskets = [3,5,4]
输出：1
解释:
- fruits[0] = 4 放入 baskets[1] = 5。
- fruits[1] = 2 放入 baskets[0] = 3。
- fruits[2] = 5 无法放入 baskets[2] = 4。
由于有一种水果未放置，我们返回 1。
解答：线段树的板子题。利用折半搜索可以寻找第一个位置。
class Solution {
public int numOfUnplacedFruits(int[] fruits, int[] baskets) {
SegmentTree tree = new SegmentTree(baskets);
int res = 0;
for (int f : fruits) {
int largest = tree.maxRange(0, baskets.length - 1);
if (largest >= f) {
int st = 0, ed = baskets.length;
while (st < ed) {
int mid = (st + ed) / 2;
int tmp = tree.maxRange(0, mid);
if (tmp >= f) {
ed = mid;
} else {
st = mid + 1;
}
}
tree.update(st, 0);
++res;
}
}
return fruits.length - res;
}
}
class SegmentTree {
int[] tree;
int n;
public SegmentTree(int[] nums) {
if (nums.length > 0) {
n = nums.length;
tree = new int[n * 2];
buildTree(nums);
}
}
private void buildTree(int[] nums) {
for (int i = n, j = 0; i < 2 * n; i++, j++)
tree[i] = nums[j];
for (int i = n - 1; i > 0; --i)
tree[i] = Math.max(tree[i * 2], tree[i * 2 + 1]);
}
void update(int pos, int val) {
pos += n;
tree[pos] = val;
while (pos > 0) {
int left = pos;
int right = pos;
if (pos % 2 == 0) {
right = pos + 1;
} else {
left = pos - 1;
}
tree[pos / 2] = Math.max(tree[left], tree[right]);
pos /= 2;
}
}
public int maxRange(int l, int r) {
l += n;
r += n;
int sum = Integer.MIN_VALUE;
while (l <= r) {
if ((l % 2) == 1) {
sum = Math.max(sum, tree[l]);
l++;
}
if ((r % 2) == 0) {
sum = Math.max(sum, tree[r]);
r--;
}
l /= 2;
r /= 2;
}
return sum;
}
}100599. Maximize Subarrays After Removing One Conflicting Pair
给你一个整数 n，表示一个包含从 1 到 n 按顺序排列的整数数组 nums。此外，给你一个二维数组 conflictingPairs，其中 conflictingPairs[i] = [a, b] 表示 a 和 b 形成一个冲突对。
从 conflictingPairs 中删除 恰好 一个元素。然后，计算数组 nums 中的非空子数组数量，这些子数组都不能同时包含任何剩余冲突对 [a, b] 中的 a 和 b。
返回删除 恰好 一个冲突对后可能得到的 最大 子数组数量。
子数组 是数组中一个连续的 非空 元素序列。
测试样例：
输入：n = 4, conflictingPairs = [[2,3],[1,4]]
输出：9
解释:
- 从 conflictingPairs 中删除 [2, 3]。现在，conflictingPairs = [[1, 4]]。
- 在 nums 中，存在 9 个子数组，其中 [1, 4] 不会一起出现。它们分别是 [1]，[2]，[3]，[4]，[1, 2]，[2, 3]，[3, 4]，[1, 2, 3] 和 [2, 3, 4]。
- 删除 conflictingPairs 中一个元素后，能够得到的最大子数组数量是 9。
解答：不会做，赛后用AI做了一下。AI能过。。。顺便贴一个AI的解释。
预处理：
- 我们初始化数组，使得如果一个索引没有冲突的配对，它的候选值被设置为
n+1。 - 对于每一对
[a, b](其中a < b)，我们更新candidate[a](以及candidate2[a]作为第二个选项)，并记录频率。
计算 f 和 Contributor：
- 后缀最小值数组
f被计算，使得f[i]是从i到n的最小候选值。 contributor数组记录，对于每个起始索引，提供f[i]的索引。
分组：
- 我们将起始索引按照它们的
contributor进行分组。 - 对于
group[a]中的每个起始索引i，最初f[i] = candidate[a]。
模拟移除：
- 对于在索引
a处的候选值移除 (当candidate[a]是唯一的)，我们将它的新候选值设置为candidate2[a]，并且令r = (a < n ? min(candidate2[a], f[a+1]) : candidate2[a])。 - 然后，对于与
a对应的组 (按照起始索引递增的顺序)，我们重新计算新的运行最小值m(它代表移除后这些索引的新f)。 - 改进值是
(m[j] – candidate[a])在该组上的总和。
class Solution {
public long maxSubarrays(int n, int[][] conflictingPairs) {
// total number of subarrays = n*(n+1)/2.
long totalSubarrays = (long) n * (n + 1) / 2;
// Use 1-indexed arrays; allocate size n+2.
int[] candidate = new int[n+1]; // candidate[a] = smallest b among pairs with first element a.
int[] candidate2 = new int[n+1]; // second-best candidate for a.
int[] freq = new int[n+1]; // frequency of candidate value for a.
for (int i = 1; i <= n; i++) {
candidate[i] = n + 1;
candidate2[i] = n + 1;
}
// Process each conflicting pair, ensuring a < b.
for (int[] pair : conflictingPairs) {
int a = pair[0], b = pair[1];
if(a > b) {
int temp = a; a = b; b = temp;
}
if(b < candidate[a]){
candidate2[a] = candidate[a]; // previous best becomes second best.
candidate[a] = b;
freq[a] = 1;
} else if(b == candidate[a]) {
freq[a]++;
} else {
candidate2[a] = Math.min(candidate2[a], b);
}
}
// Build the suffix–minimum array f:
// f[i] = min(candidate[i], candidate[i+1], ..., candidate[n]).
int[] f = new int[n+2];
f[n] = candidate[n];
for (int i = n - 1; i >= 1; i--) {
f[i] = Math.min(candidate[i], f[i+1]);
}
f[n+1] = n + 1;
// Build contributor array:
// contributor[i] = the first index j in [i, n] with candidate[j] = f[i].
int[] contributor = new int[n+1];
contributor[n] = n;
for (int i = n - 1; i >= 1; i--) {
if(candidate[i] <= f[i+1]) {
contributor[i] = i;
} else {
contributor[i] = contributor[i+1];
}
}
// Compute the original union area (i.e. total invalid subarrays):
long unionArea = 0;
for (int i = 1; i <= n; i++) {
if(f[i] <= n) {
unionArea += (n - f[i] + 1);
}
}
long originalValid = totalSubarrays - unionArea;
// Group starting indices by their contributor.
List<Integer>[] groups = new ArrayList[n+1];
for (int i = 1; i <= n; i++) {
groups[i] = new ArrayList<>();
}
for (int i = 1; i <= n; i++) {
groups[contributor[i]].add(i);
}
long maxImprovement = 0;
// Try candidate removals. Removal is only possible if candidate[a] <= n and is unique.
for (int a = 1; a <= n; a++) {
if(candidate[a] <= n && freq[a] == 1) {
// Removal at a changes candidate[a] to candidate2[a].
int newCandidate = candidate2[a]; // if no second candidate, equals n+1.
int r = (a < n ? Math.min(newCandidate, f[a+1]) : newCandidate);
// For all starting indices i with contributor a, originally f[i] = candidate[a].
// After removal, we recompute the new running minimum along the group.
List<Integer> groupList = groups[a];
if(groupList.isEmpty()) continue;
int k = groupList.size();
int[] X = new int[k];
// X[j] will be candidate[ i ] for i in the group.
for (int j = 0; j < k; j++) {
int idx = groupList.get(j);
X[j] = candidate[idx];
}
// Compute new running minimum array m:
int[] m = new int[k];
m[k-1] = r; // the contributor's new candidate becomes r.
for (int j = k - 2; j >= 0; j--) {
m[j] = Math.min(X[j], m[j+1]);
}
long sumM = 0;
for (int j = 0; j < k; j++) {
sumM += m[j];
}
// Originally, each starting index in this group had f = candidate[a].
long improvement = sumM - (long) k * candidate[a];
maxImprovement = Math.max(maxImprovement, improvement);
}
}
return originalValid + maxImprovement;
}
}