力扣 220th 周赛 - Tadow 碎碎念

好久没写 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 <= 10⁵
-10⁴ <= nums[i] <= 10⁴

解法一

递推公式很容易得到，先来一发暴力解法，不出意料的 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] = [u_i, v_i, dis_i] 表示点 u_i 和点 v_i 之间有一条长度为 dis_i 的边。请注意，两个点之间可能有超过一条边。

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

请你返回一个 布尔数组answer，其中answer.length == queries.length ，当 queries[j] 的查询结果为 true 时， answer 第j 个值为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]
解释：上图为给定的输入数据。注意到 0 和 1 之间有两条重边，分别为 2 和 16 。
对于第一个查询，0 和 1 之间没有小于 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 <= 10⁵
1 <= edgeList.length, queries.length <= 10⁵
edgeList[i].length == 3
queries[j].length == 3
0 <= u_i, v_i, p_j, q_j <= n - 1
u_i != v_i
p_j != q_j
1 <= dis_i, limit_j <= 10⁹
两个点之间可能有多条边。

解法一

看到了评论区的一句提示然后写出了下面的解法，后来看题解区大佬科普这种类型的题目属于离线算法，其实核心的思想就是，对查询的 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;
}