欢迎大家加QQ群：623375442，可以方便群里面交流。这周题目，难度不是很大。
100530. Zigzag Grid Traversal With Skip
给你一个 m x n 的二维数组 grid，数组由 正整数 组成。
你的任务是以 之字形 遍历 grid，同时跳过每个 交替 的单元格。
之字形遍历的定义如下：
- 从左上角的单元格 (0, 0) 开始。
- 在当前行中向 右 移动，直到到达该行的末尾。
- 下移到下一行，然后在该行中向 左 移动，直到到达该行的开头。
- 继续在行间交替向右和向左移动，直到所有行都被遍历完。
注意：在遍历过程中，必须跳过每个 交替 的单元格。
返回一个整数数组 result，其中包含按 顺序 记录的、且跳过交替单元格后的之字形遍历中访问到的单元格值。
测试样例：
输入：grid = [[1,2],[3,4]]
输出：[1,4]
解释：按照题意暴力计算。
解答：按照题意，暴力计算。
class Solution {
public List<Integer> zigzagTraversal(int[][] grid) {
List<Integer> res = new ArrayList<>();
int x = 0, y = 0;
int dir = 1;
while (x < grid.length) {
res.add(grid[x][y]);
int tmp = y + 2 * dir;
if (tmp >= 0 && tmp < grid[x].length) {
y = tmp;
} else {
++x;
if (x >= grid.length) break;
if (y == grid[x].length - 2 && dir == 1) {
y = grid[x].length - 1;
} else if (y == grid[x].length - 1 && dir == 1) {
y = grid[x].length - 2;
} else if (y == 0 && dir == -1) {
y = 1;
} else if (y == 1 && dir == -1) {
y = 0;
}
dir *= -1;
}
}
return res;
}
}100502. Maximum Amount of Money Robot Can Earn
给你一个 m x n 的网格。一个机器人从网格的左上角 (0, 0) 出发，目标是到达网格的右下角 (m - 1, n - 1)。在任意时刻，机器人只能向右或向下移动。
网格中的每个单元格包含一个值 coins[i][j]：
- 如果 coins[i][j] >= 0，机器人可以获得该单元格的金币。
- 如果 coins[i][j] < 0，机器人会遇到一个强盗，强盗会抢走该单元格数值的 绝对值 的金币。
机器人有一项特殊能力，可以在行程中 最多感化 2个单元格的强盗，从而防止这些单元格的金币被抢走。
注意：机器人的总金币数可以是负数。
返回机器人在路径上可以获得的 最大金币数 。
测试样例：
输入：coins = [[0,1,-1],[1,-2,3],[2,-3,4]]
输出：8
解释：一个获得最多金币的最优路径如下：
- 从 (0, 0) 出发，初始金币为 0（总金币 = 0）。
- 移动到 (0, 1)，获得 1 枚金币（总金币 = 0 + 1 = 1）。
- 移动到 (1, 1)，遇到强盗抢走 2 枚金币。机器人在此处使用一次感化能力，避免被抢（总金币 = 1）。
- 移动到 (1, 2)，获得 3 枚金币（总金币 = 1 + 3 = 4）。
- 移动到 (2, 2)，获得 4 枚金币（总金币 = 4 + 4 = 8）。
解答：经典DP。
class Solution {
public int maximumAmount(int[][] coins) {
int m = coins.length, n = coins[0].length;
int[][] dp = new int[n][3];
for (int i = 0; i < m; ++i) {
int[] coinRow = coins[i];
int[][] nextDp = new int[n][3];
Arrays.fill(nextDp[0], Integer.MIN_VALUE);
cal(nextDp[0], dp[0], coinRow[0]);
for (int j = 1; j < n; ++j) {
Arrays.fill(nextDp[j], Integer.MIN_VALUE);
cal(nextDp[j], nextDp[j - 1], coinRow[j]);
if (i != 0) {
cal(nextDp[j], dp[j], coinRow[j]);
}
}
dp = nextDp;
}
return Math.max(dp[n - 1][0], Math.max(dp[n - 1][1], dp[n - 1][2]));
}
private void cal(int[] cur, int[] last, int num) {
for (int i = 0; i < 3; ++i) {
if (i == 0) {
cur[0] = Math.max(cur[0], last[0] + num);
} else {
cur[i] = Math.max(cur[i], last[i] + num);
cur[i] = Math.max(cur[i], last[i - 1]);
}
}
}
}100538. Minimize the Maximum Edge Weight of Graph
给你两个整数 n 和 threshold ，同时给你一个 n 个节点的 有向 带权图，节点编号为 0 到 n - 1 。这个图用 二维 整数数组 edges 表示，其中 edges[i] = [Ai, Bi, Wi] 表示节点 Ai 到节点 Bi 之间有一条边权为 Wi的有向边。
你需要从这个图中删除一些边（也可能 不 删除任何边），使得这个图满足以下条件:
- 所有其他节点都可以到达节点 0 。
- 图中剩余边的 最大 边权值尽可能小。
每个节点都 至多 有 threshold 条出去的边。
请你返回删除必要的边后，最大 边权的 最小值 为多少。如果无法满足所有的条件，请你返回 -1 。
测试样例：
输入：n = 5, edges = [[1,0,1],[2,0,2],[3,0,1],[4,3,1],[2,1,1]], threshold = 2
输出：1
解释：删除边 2 -> 0 。剩余边中的最大值为 1 。
解答：没想到啥好办法。将edges按照大小排序之后，利用折半搜索寻找可行的子图。
class Solution {
public int minMaxWeight(int n, int[][] edges, int threshold) {
Arrays.sort(edges, (a, b) -> (Integer.compare(a[2], b[2])));
int st = 0, ed = edges.length;
List<Integer>[] map = new List[n];
for (int i = 0; i < n; ++i) {
map[i] = new ArrayList<>();
}
int[] count = new int[n];
int counter = 1;
while (st < ed) {
int mid = (st + ed) / 2;
if (!isValid(edges, mid, map, count, counter, n)) {
st = mid + 1;
} else {
ed = mid;
}
++counter;
}
return st < edges.length ? edges[st][2] : -1;
}
// 计算当前范围，所有点都能连向0
private boolean isValid(int[][] edges, int max, List<Integer>[] map, int[] count, int counter, int n) {
for (int i = 0; i <= max; ++i) {
// 其实只关心出度，反向利用入度来计算图的连通性。这样每个点最多出度为1
if (count[edges[i][1]] < counter) {
count[edges[i][1]] = counter;
map[edges[i][1]] = new ArrayList<>();
}
map[edges[i][1]].add(edges[i][0]);
}
boolean[] isMet = new boolean[n];
Queue<Integer> queue = new LinkedList<>();
isMet[0] = true;
queue.add(0);
--n;
while (!queue.isEmpty()) {
int tmp = queue.poll();
if (count[tmp] == counter) {
for (int ne : map[tmp]) {
if (!isMet[ne]) {
isMet[ne] = true;
--n;
queue.add(ne);
}
}
}
}
return n == 0;
}
}100499. Count Non-Decreasing Subarrays After K Operations
给你一个长度为 n 的数组 nums 和一个整数 k 。
对于 nums 中的每一个子数组，你可以对它进行 至多 k 次操作。每次操作中，你可以将子数组中的任意一个元素增加 1 。
注意 ，每个子数组都是独立的，也就是说你对一个子数组的修改不会保留到另一个子数组中。
请你返回最多 k 次操作以内，有多少个子数组可以变成 非递减 的。
如果一个数组中的每一个元素都大于等于前一个元素（如果前一个元素存在），那么我们称这个数组是 非递减 的。
测试样例：
输入：nums = [6,3,1,2,4,4], k = 7
输出：17
解释：nums 的所有 21 个子数组中，只有子数组 [6, 3, 1] ，[6, 3, 1, 2] ，[6, 3, 1, 2, 4] 和 [6, 3, 1, 2, 4, 4] 无法在 k = 7 次操作以内变为非递减的。所以非递减子数组的数目为 21 - 4 = 17 。
解答：从后向前利用类似单调栈的思路计算。
class Solution {
public long countNonDecreasingSubarrays(int[] nums, long k) {
long[] prefixSum = new long[nums.length + 1];
for (int i = 0; i < nums.length; ++i) {
prefixSum[i + 1] = prefixSum[i] + nums[i];
}
long res = 0;
Deque<Integer> queue = new LinkedList<>();
int st = nums.length - 1;
queue.addLast(st);
for (int ed = nums.length - 1; ed >= 0; --ed) {
while (k >= 0 && st >= 0) {
--st;
if (st == -1) {
break;
}
// 用单调栈来模拟最大可行范围
while (!queue.isEmpty() && nums[queue.peekFirst()] <= nums[st]) {
long tmp = queue.pollFirst();
k -= (queue.isEmpty() ? (ed + 1 - tmp) : (queue.peekFirst() - tmp)) * (nums[st] - nums[(int)tmp]);
}
queue.addFirst(st);
}
res += (ed - st);
// 踢掉最后一个数，补一下最后一个数导致的diff
k += nums[queue.peekLast()] - nums[ed];
// 如果最后一个数是当前最大的数字，不能忘记补一下离开队列
if (queue.peekLast() == ed) {
queue.pollLast();
}
}
return res;
}
}