6406. Maximum Sum With Exactly K Elements
给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。你需要执行以下操作 恰好 k 次，最大化你的得分：
- 从 nums 中选择一个元素 m 。
- 将选中的元素 m 从数组中删除。
- 将新元素 m + 1 添加到数组中。
- 你的得分增加 m 。
请你返回执行以上操作恰好 k 次后的最大得分。
测试样例
输入：nums = [1,2,3,4,5], k = 3
输出：18
解释：我们需要从 nums 中恰好选择 3 个元素并最大化得分。第一次选择 5 。和为 5 ，nums = [1,2,3,4,6] 。第二次选择 6 。和为 6 ，nums = [1,2,3,4,7] 。第三次选择 7 。和为 5 + 6 + 7 = 18 ，nums = [1,2,3,4,8] 。所以我们返回 18 。18 是可以得到的最大答案。
解答：感觉这道题目就是在寻找最大值。。。
class Solution {
public int maximizeSum(int[] nums, int k) {
int max = 0;
for (int i : nums) {
max = Math.max(max, i);
}
int res = 0;
for (int i = 0; i < k; ++i) {
res += max;
++max;
}
return res;
}
}6405. Find the Prefix Common Array of Two Arrays
给你两个下标从 0 开始长度为 n 的整数排列 A 和 B 。
A 和 B 的 前缀公共数组 定义为数组 C ，其中 C[i] 是数组 A 和 B 到下标为 i 之前公共元素的数目。
请你返回 A 和 B 的 前缀公共数组 。
如果一个长度为 n 的数组包含 1 到 n 的元素恰好一次，我们称这个数组是一个长度为 n 的 排列 。
测试样例：
输入：A = [1,3,2,4], B = [3,1,2,4]
输出：[0,2,3,4]
解释：
- i = 0：没有公共元素，所以 C[0] = 0 。
- i = 1：1 和 3 是两个数组的前缀公共元素，所以 C[1] = 2 。
- i = 2：1，2 和 3 是两个数组的前缀公共元素，所以 C[2] = 3 。
- i = 3：1，2，3 和 4 是两个数组的前缀公共元素，所以 C[3] = 4 。
解答: 这道题目范围：1 <= A.length == B.length == n <= 50。这个范围相当小，直接暴力遍历就行了
class Solution {
public int[] findThePrefixCommonArray(int[] A, int[] B) {
int len = A.length;
int[] res = new int[len];
HashMap<Integer, Integer> left = new HashMap<>(), right = new HashMap<>();
for (int i = 0; i < len; ++i) {
left.put(A[i], left.getOrDefault(A[i], 0) + 1);
right.put(B[i], right.getOrDefault(B[i], 0) + 1);
for (Map.Entry<Integer, Integer> kv : left.entrySet()) {
res[i] += Math.min(kv.getValue(), right.getOrDefault(kv.getKey(), 0));
}
}
return res;
}
}6403. Maximum Number of Fish in a Grid
给你一个下标从 0 开始大小为 m x n 的二维整数数组 grid ，其中下标在 (r, c) 处的整数表示：
- 如果 grid[r][c] = 0 ，那么它是一块 陆地 。
- 如果 grid[r][c] > 0 ，那么它是一块 水域 ，且包含 grid[r][c] 条鱼。
一位渔夫可以从任意 水域 格子 (r, c) 出发，然后执行以下操作任意次：
- 捕捞格子 (r, c) 处所有的鱼，或者
- 移动到相邻的 水域 格子。
请你返回渔夫最优策略下， 最多 可以捕捞多少条鱼。如果没有水域格子，请你返回 0 。
格子 (r, c) 相邻 的格子为 (r, c + 1) ，(r, c - 1) ，(r + 1, c) 和 (r - 1, c) ，前提是相邻格子在网格图内。
测试样例：
输入：grid = [[0,2,1,0],[4,0,0,3],[1,0,0,4],[0,3,2,0]]
输出：7
解答: 这道题目的范围也相当小。可以暴力BFS遍历或者用并查集寻找最大可联通的水域和水域对应能捕捉到的鱼。
class Solution {
private class DSU{
int[] parent;
public DSU(int N) {
parent = new int[N];
for (int i = 0; i < N; ++i) {
parent[i] = i;
}
}
public int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
public void union(int x, int y) {
parent[find(x)] = find(y);
}
}
private static final int[] moves = {1,0,-1,0,1};
public int findMaxFish(int[][] grid) {
int m = grid.length, n = grid[0].length;
DSU uf = new DSU(m * n);
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] != 0) {
for (int k = 0; k < 4; ++k) {
int xt = i + moves[k], yt = j + moves[k + 1];
if (xt >= 0 && xt < m && yt >= 0 && yt < n && grid[xt][yt] != 0) {
uf.union(xt * n + yt, i * n + j);
}
}
}
}
}
int res = 0;
HashMap<Integer, Integer> mem = new HashMap<>();
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] != 0) {
int key = uf.find(i * n + j);
int total = mem.getOrDefault(key, 0) + grid[i][j];
res = Math.max(res, total);
mem.put(key, total);
}
}
}
return res;
}
}6404. Make Array Empty
给你一个包含若干 互不相同 整数的数组 nums ，你需要执行以下操作 直到数组为空 ：
- 如果数组中第一个元素是当前数组中的 最小值 ，则删除它。
- 否则，将第一个元素移动到数组的 末尾 。
请你返回需要多少个操作使 nums 为空。
测试样例：
输入：nums = [3,4,-1]
输出：5
解答：这道题目，首先考的是排序，利用排序可以知道当前位置和下一个位置。然后按照题意，如果元素满足会被移除，所以需要了解当前位置和下一个位置之间还存在的元素数。这个利用树状态数组可以轻松计算。有这两部分的准备，就可以直接计算了。
class Solution {
class SegmentTree {
int[] tree;
int n;
public SegmentTree(int len) {
n = len;
tree = new int[n * 2];
for (int i = n, j = 0; i < 2 * n; i++, j++)
tree[i] = 1;
for (int i = n - 1; i > 0; --i)
tree[i] = 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;
}
// parent is updated after child is updated
tree[pos / 2] = tree[left] + tree[right];
pos /= 2;
}
}
public int sumRange(int l, int r) {
// get leaf with value 'l'
l += n;
// get leaf with value 'r'
r += n;
int sum = 0;
while (l <= r) {
if ((l % 2) == 1) {
sum += tree[l];
l++;
}
if ((r % 2) == 0) {
sum += tree[r];
r--;
}
l /= 2;
r /= 2;
}
return sum;
}
}
public long countOperationsToEmptyArray(int[] nums) {
int len = nums.length;
Integer[] sort = new Integer[len];
for (int i = 0; i < sort.length; ++i) {
sort[i] = i;
}
Arrays.sort(sort, (a, b) -> (nums[a] - nums[b]));
SegmentTree tree = new SegmentTree(len);
int cur = 0;
long res = 0;
for (int s : sort) {
if (s >= cur) {
res += tree.sumRange(cur, s);
} else {
res = res + tree.sumRange(cur, len - 1) + tree.sumRange(0, s);
}
tree.update(s, 0);
cur = (s + 1) % len;
}
return res;
}
}今年第一次，在究极手速场中获得不错的排名。还有，祝大家五一节快乐！