好久没写 LeetCode 的题了,来补一下 220 周赛 的 T3 和 T4

1696. 跳跃游戏 VI

Difficulty: 中等

给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。

一开始你在下标 0 处。每一步,你最多可以往前跳 k 步,但你不能跳出数组的边界。也就是说,你可以从下标 i 跳到 [i + 1, min(n - 1, i + k)] 包含 两个端点的任意位置。

你的目标是到达数组最后一个位置(下标为 n - 1 ),你的 得分 为经过的所有数字之和。

请你返回你能得到的 最大得分 。

示例 1:

输入:nums = [1,-1,-2,4,-7,3], k = 2
输出:7
解释:你可以选择子序列 [1,-1,4,3] (上面加粗的数字),和为 7

示例 2:

输入:nums = [10,-5,-2,4,0,3], k = 3
输出:17
解释:你可以选择子序列 [10,4,3] (上面加粗数字),和为 17

示例 3:

输入:nums = [1,-5,-20,4,-1,3,-6,-3], k = 2
输出:0

提示:

  • 1 <= nums.length, k <= 105
  • -104 <= nums[i] <= 104

解法一

递推公式很容易得到,先来一发暴力解法,不出意料的 T 了

//1 2 3 4 5 k=2
public int maxResult(int[] nums, int k) {
int n = nums.length;
int[] dp = new int[n];
dp[0] = nums[0];
for (int i = 1; i < n; i++) {
dp[i] = -0x3f3f3f3f;
for (int j = i-1; i-j <= k && j >= 0; j--) {
dp[i] = Math.max(dp[j]+nums[i], dp[i]);
}
}
return dp[n-1];
}

解法二

其实这题想了挺久的,主要是没想到 T3 会用到单调队列去优化 dp,很巧的是这个单调队列优化这个知识点我刚刚在 yxc 那边学了一点,那个题目相对这题会复杂很多,是多重背包的问题。然后我就感觉这个题好像也可以用单调队列来优化,然后就试了一发,然后就 AC 了😁

这里也可以借助其他的数据结构,比如线段树,st 表,优先队列什么的去维护连续的大小为 k 的区间的最大值,这里我就不写了

//1 2 3 4 5 k=2
public int maxResult(int[] nums, int k) {
int n = nums.length;
int[] dp = new int[n];
dp[0] = nums[0];
//dp[i] = Max( dp[i-1], dp[i-2], dp[i-3],... dp[i-k+1], dp[i-k])
//dp[i+1] = Max(dp[i], dp[i-1], dp[i-2], dp[i-3],... dp[i-k+1])
//dp[i] --> dp[i+1] 滑动窗口最大值
LinkedList<int[]> queue = new LinkedList<>();
for (int i = 1; i < n; i++) {
while (!queue.isEmpty() && dp[i-1] > queue.getLast()[0]) {
queue.removeLast();
}
if (!queue.isEmpty() && i-queue.getFirst()[1] >= k) {
queue.removeFirst();
}
//这里也可以在队列中只存 dp 值的坐标,简化代码
queue.addLast(new int[]{dp[i-1], i});
dp[i] = queue.getFirst()[0]+nums[i];
}
return dp[n-1];
}

1697. 检查边长度限制的路径是否存在

Difficulty: 困难

给你一个 n 个点组成的无向图边集 edgeList ,其中 edgeList[i] = [ui, vi, disi] 表示点 ui 和点 vi 之间有一条长度为 disi 的边。请注意,两个点之间可能有超过一条边。

给你一个查询数组queries ,其中 queries[j] = [pj, qj, limitj] ,你的任务是对于每个查询 queries[j] ,判断是否存在从 pj 到 qj的路径,且这条路径上的每一条边都 严格小于 limitj

请你返回一个 布尔数组answer,其中answer.length == queries.length ,当 queries[j] 的查询结果为 true 时, answerj 个值为true,否则为 false 。

示例 1:

输入:n = 3, edgeList = [[0,1,2],[1,2,4],[2,0,8],[1,0,16]], queries = [[0,1,2],[0,2,5]]
输出:[false,true]
解释:上图为给定的输入数据。注意到 01 之间有两条重边,分别为 216
对于第一个查询,01 之间没有小于 2 的边,所以我们返回 false
对于第二个查询,有一条路径(0 -> 1 -> 2)两条边都小于 5 ,所以这个查询我们返回 true

示例 2:

输入:n = 5, edgeList = [[0,1,10],[1,2,5],[2,3,9],[3,4,13]], queries = [[0,4,14],[1,4,13]]
输出:[true,false]
解释:上图为给定数据。

提示:

  • 2 <= n <= 105
  • 1 <= edgeList.length, queries.length <= 105
  • edgeList[i].length == 3
  • queries[j].length == 3
  • 0 <= ui, vi, pj, qj <= n - 1
  • ui != vi
  • pj != qj
  • 1 <= disi, limitj <= 109
  • 两个点之间可能有 多条 边。

解法一

看到了评论区的一句提示然后写出了下面的解法,后来看题解区大佬科普这种类型的题目属于 离线算法,其实核心的思想就是,对查询的 limit 和边权值进行排序,然后从小 query 的 limit 开始,将 edge 权值不大于 limit 的都丢到并查集里面,然后查询一下就行了

int[] parent;

public int find(int a) {
if (parent[a] == a) {
return a;
}
return parent[a] = find(parent[a]);
}

public void union(int a,int b) {
int pa = find(a);
int pb = find(b);
if (pa == pb) return;
parent[pa] = pb;
}

class Pair {
int p, q;
int limit;
int idx;
public Pair(int p, int q, int limit, int idx) {
this.p = p;
this.q = q;
this.limit = limit;
this.idx = idx;
}
}

public boolean[] distanceLimitedPathsExist(int n, int[][] edge, int[][] q) {
parent = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;
boolean[] res = new boolean[q.length];
Pair[] query = new Pair[q.length];
for (int i = 0; i < q.length; i++) {
query[i] = new Pair(q[i][0], q[i][1], q[i][2], i);
}
Arrays.sort(edge, (e1, e2)->e1[2]-e2[2]);
Arrays.sort(query, (q1, q2)->q1.limit-q2.limit);
int j = 0;
for (int i = 0; i < query.length; i++) {
while (j < edge.length && edge[j][2] < query[i].limit) {
union(edge[j][0], edge[j][1]);
j++;
}
res[query[i].idx] = find(query[i].p) == find(query[i].q);
}
return res;
}

看了大佬们的代码后稍微做了下点简化

int[] parent;

public int find(int a) {
if (parent[a] == a) return a;
return parent[a] = find(parent[a]);
}

public void union(int a,int b) {
int pa = find(a);
int pb = find(b);
if (pa == pb) return;
parent[pa] = pb;
}

public boolean[] distanceLimitedPathsExist(int n, int[][] edge, int[][] q) {
parent = new int[n];
int qlen = q.length;
for (int i = 0; i < n; i++) parent[i] = i;
boolean[] res = new boolean[qlen];
//记录 query 排序后的 id
Integer[] qid = new Integer[qlen];
for (int i = 0; i < qlen; i++) qid[i] = i;
Arrays.sort(edge, (e1, e2)->e1[2]-e2[2]);
Arrays.sort(qid, (i1, i2)->q[i1][2]-q[i2][2]);
int j = 0;
for (int i = 0; i < qlen; i++) {
while (j < edge.length && edge[j][2] < q[qid[i]][2]) {
union(edge[j][0], edge[j][1]);
j++;
}
res[qid[i]] = find(q[qid[i]][0]) == find(q[qid[i]][1]);
}
return res;
}