周赛 - 🏆 第 284 场力扣周赛 - 《学习笔记》

6031. 找出数组中的所有 K 近邻下标
5203. 统计可以提取的工件
5227. K 次操作后最大化顶端元素
6032. 得到要求路径的最小带权子图

t3的分类讨论我没搞清楚就瞎提交，麻了，建议冷静冷静再交！

6031. 找出数组中的所有 K 近邻下标

给你一个下标从 0 开始的整数数组 nums 和两个整数 key 和 k 。K 近邻下标 是 nums 中的一个下标 i ，并满足至少存在一个下标 j 使得 |i - j| <= k 且 nums[j] == key 。
以列表形式返回按 递增顺序 排序的所有 K 近邻下标。

示例 1：
输入：nums = [3,4,9,1,3,9,5], key = 9, k = 1 输出：[1,2,3,4,5,6] 解释：因此，nums[2] == key 且 nums[5] == key 。 - 对下标 0 ，|0 - 2| > k 且 |0 - 5| > k ，所以不存在 j 使得 |0 - j| <= k 且 nums[j] == key 。所以 0 不是一个 K 近邻下标。 - 对下标 1 ，|1 - 2| <= k 且 nums[2] == key ，所以 1 是一个 K 近邻下标。 - 对下标 2 ，|2 - 2| <= k 且 nums[2] == key ，所以 2 是一个 K 近邻下标。 - 对下标 3 ，|3 - 2| <= k 且 nums[2] == key ，所以 3 是一个 K 近邻下标。 - 对下标 4 ，|4 - 5| <= k 且 nums[5] == key ，所以 4 是一个 K 近邻下标。 - 对下标 5 ，|5 - 5| <= k 且 nums[5] == key ，所以 5 是一个 K 近邻下标。 - 对下标 6 ，|6 - 5| <= k 且 nums[5] == key ，所以 6 是一个 K 近邻下标。因此，按递增顺序返回 [1,2,3,4,5,6] 。
示例 2：
输入：nums = [2,2,2,2,2], key = 2, k = 2 输出：[0,1,2,3,4] 解释：对 nums 的所有下标 i ，总存在某个下标 j 使得 |i - j| <= k 且 nums[j] == key ，所以每个下标都是一个 K 近邻下标。因此，返回 [0,1,2,3,4] 。

提示：

1 <= nums.length <= 1000
1 <= nums[i] <= 1000
key 是数组 nums 中的一个整数
1 <= k <= nums.length

思路：
暴力查找

class Solution {
    public List<Integer> findKDistantIndices(int[] nums, int key, int k) {
        List<Integer> res = new ArrayList<>();
        int n = nums.length;
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < n; i++) {
            if (nums[i] == key)
                for (int j = Math.max(0, i - k); j <= Math.min(n - 1, i + k); j++)
                    set.add(j);
        }
        for (int x : set)
                res.add(x);
        Collections.sort(res);
        return res;
    }
}

5203. 统计可以提取的工件

存在一个 n x n 大小、下标从 0 开始的网格，网格中埋着一些工件。给你一个整数 n 和一个下标从 0 开始的二维整数数组 artifacts ，artifacts 描述了矩形工件的位置，其中 artifacts[i] = [r1i, c1i, r2i, c2i] 表示第 i 个工件在子网格中的填埋情况：

(r1i, c1i) 是第 i 个工件左上单元格的坐标，且
(r2i, c2i) 是第 i 个工件右下单元格的坐标。

你将会挖掘网格中的一些单元格，并清除其中的填埋物。如果单元格中埋着工件的一部分，那么该工件这一部分将会裸露出来。如果一个工件的所有部分都都裸露出来，你就可以提取该工件。
给你一个下标从 0 开始的二维整数数组 dig ，其中 dig[i] = [ri, ci] 表示你将会挖掘单元格 (ri, ci) ，返回你可以提取的工件数目。
生成的测试用例满足：

不存在重叠的两个工件。
每个工件最多只覆盖 4 个单元格。
dig 中的元素互不相同。

示例 1：
输入：n = 2, artifacts = [[0,0,0,0],[0,1,1,1]], dig = [[0,0],[0,1]] 输出：1 解释： 不同颜色表示不同的工件。挖掘的单元格用 ‘D’ 在网格中进行标记。有 1 个工件可以提取，即红色工件。蓝色工件在单元格 (1,1) 的部分尚未裸露出来，所以无法提取该工件。因此，返回 1 。
示例 2：
输入：n = 2, artifacts = [[0,0,0,0],[0,1,1,1]], dig = [[0,0],[0,1],[1,1]] 输出：2 解释：红色工件和蓝色工件的所有部分都裸露出来（用 ‘D’ 标记），都可以提取。因此，返回 2 。

提示：

1 <= n <= 1000
1 <= artifacts.length, dig.length <= min(n2, 105)
artifacts[i].length == 4
dig[i].length == 2
0 <= r1i, c1i, r2i, c2i, ri, ci <= n - 1
r1i <= r2i
c1i <= c2i
不存在重叠的两个工件
每个工件最多只覆盖 4 个单元格
dig 中的元素互不相同

思路：
暴力搜索即可

class Solution {
    public int digArtifacts(int n, int[][] dd, int[][] dig) {
        int[][] a = new int[n][n];
        for (int[] p : dd) {
            int x1 = p[0], y1 = p[1], x2 = p[2], y2 = p[3];
            for (int i = x1; i <= x2; i++) {
                for (int j = y1; j <= y2; j++)
                    a[i][j] = 1;
            }
        }
        for (int[] p : dig) {
            int x = p[0], y = p[1];
            a[x][y] = 0;
        }
        int res = 0;
        for (int[] p : dd) {
            int x1 = p[0], y1 = p[1], x2 = p[2], y2 = p[3];
            boolean flag = true;
            label: for (int i = x1; i <= x2; i++) {
                for (int j = y1; j <= y2; j++)
                    if (a[i][j] == 1) {
                        flag = false;
                        break label;
                    }
            }
            if (flag) res++;
        }
        return res;
    }
}

5227. K 次操作后最大化顶端元素

给你一个下标从 0 开始的整数数组 nums ，它表示一个栈，其中 nums[0] 是栈顶的元素。
每一次操作中，你可以执行以下操作之一：

如果栈非空，那么删除栈顶端的元素。
如果存在 1 个或者多个被删除的元素，你可以从它们中选择任何一个，添加回栈顶，这个元素成为新的栈顶元素。

同时给你一个整数 k ，它表示你总共需要执行操作的次数。
请你返回恰好执行 k 次操作以后，栈顶元素的 最大值 。如果执行完 k 次操作以后，栈一定为空，请你返回 -1 。

示例 1：
输入：nums = [5,2,2,4,0,6], k = 4 输出：5 解释： 4 次操作后，栈顶元素为 5 的方法之一为： - 第 1 次操作：删除栈顶元素 5 ，栈变为 [2,2,4,0,6] 。 - 第 2 次操作：删除栈顶元素 2 ，栈变为 [2,4,0,6] 。 - 第 3 次操作：删除栈顶元素 2 ，栈变为 [4,0,6] 。 - 第 4 次操作：将 5 添加回栈顶，栈变为 [5,4,0,6] 。注意，这不是最后栈顶元素为 5 的唯一方式。但可以证明，4 次操作以后 5 是能得到的最大栈顶元素。
示例 2：
输入：nums = [2], k = 1 输出：-1 解释： 第 1 次操作中，我们唯一的选择是将栈顶元素弹出栈。由于 1 次操作后无法得到一个非空的栈，所以我们返回 -1 。

提示：

1 <= nums.length <= 105
0 <= nums[i], k <= 109

思路：
分类讨论：
数组为空或者数组只有一个元素且操作数为奇数，之间返回-1
数组长度大于操作数，前k - 1个数与第k + 1个数两者取最大
数组长度等于操作数，前k - 1个数中的最大值
数组长度小于操作数，假设取出数组中所有数后，剩余可操作数为奇数，可以将最大的数，放回取出放回重复进行
剩余可操作数为偶数，可以将最大的数除外的任意数放回，然后就变成了上一行的情况。

class Solution {
    public int maximumTop(int[] nums, int k) {
        int n = nums.length;
        if (n == 0 || n == 1 && k % 2 == 1)
            return -1;
        if (n > k) {
            int max = 0;
            for (int i = 0; i < k - 1; i++)
                max = Math.max(max, nums[i]);
            return Math.max(max, nums[k]);
        } else if (n == k) {
            int max = 0;
            for (int i = 0; i < k - 1; i++)
                max = Math.max(max, nums[i]);
            return max;
        } else {
            int max = 0;
            for (int i = 0; i < n; i++)
                max = Math.max(max, nums[i]);
            return max;
        }
    }
}

6032. 得到要求路径的最小带权子图

给你一个整数 n ，它表示一个 带权有向 图的节点数，节点编号为 0 到 n - 1 。
同时给你一个二维整数数组 edges ，其中 edges[i] = [fromi, toi, weighti] ，表示从 fromi 到 toi 有一条边权为 weighti 的有向边。
最后，给你三个 互不相同 的整数 src1 ，src2 和 dest ，表示图中三个不同的点。
请你从图中选出一个 边权和最小 的子图，使得从 src1 和 src2 出发，在这个子图中，都可以到达 dest 。如果这样的子图不存在，请返回 -1 。
子图中的点和边都应该属于原图的一部分。子图的边权和定义为它所包含的所有边的权值之和。

示例 1：

输入：n = 6, edges = [[0,2,2],[0,5,6],[1,0,3],[1,4,5],[2,1,1],[2,3,3],[2,3,4],[3,4,2],[4,5,1]], src1 = 0, src2 = 1, dest = 5 输出：9 解释： 上图为输入的图。蓝色边为最优子图之一。注意，子图 [[1,0,3],[0,5,6]] 也能得到最优解，但无法在满足所有限制的前提下，得到更优解。
示例 2：

输入：n = 3, edges = [[0,1,1],[2,1,1]], src1 = 0, src2 = 1, dest = 2 输出：-1 解释： 上图为输入的图。可以看到，不存在从节点 1 到节点 2 的路径，所以不存在任何子图满足所有限制。

提示：

3 <= n <= 105
0 <= edges.length <= 105
edges[i].length == 3
0 <= fromi, toi, src1, src2, dest <= n - 1
fromi != toi
src1 ，src2 和 dest 两两不同。
1 <= weight[i] <= 105

思路：
正向两次 Dijkstra + 反向1次 Dijkstra + 枚举

class Solution {
    int N = 100010;
    long INF = (long)(1e12);
    int n, idx;
    int[] h = new int[N], e = new int[N], ne = new int[N], w = new int[N];
    boolean[] st = new boolean[N];
    long[] d1 = new long[N], d2 = new long[N], d3 = new long[N];
    void add(int a, int b, int c) {
        e[idx] = b;
        w[idx] = c;
        ne[idx] = h[a];
        h[a] = idx++;
    }
    public long minimumWeight(int n, int[][] edges, int src1, int src2, int dest) {
        this.n = n;
        Arrays.fill(h, -1);
        for (int[] p : edges) {
            int a = p[0], b = p[1], c = p[2];
            add(a, b, c);
        }
        dijkstra(src1, d1);
        dijkstra(src2, d2);
        if (d1[dest] == INF || d2[dest] == INF) return -1;
        Arrays.fill(h, -1);
        idx = 0;
        for (int[] p : edges) {
            int b = p[0], a = p[1], c = p[2];
            add(a, b, c);
        }
        dijkstra(dest, d3);
        long min = (long)(1e15);
        for (int i = 0; i < n; i++)
            min = Math.min(d1[i] + d2[i] + d3[i], min);
        return min;
    }
    void dijkstra(int start, long[] dist) {
        Arrays.fill(st, false);
        Arrays.fill(dist, INF);
        PriorityQueue<long[]> q = new PriorityQueue<>((o1, o2) -> {
           if (o1[1] == o2[1])
               return 0;
            else return o1[1] > o2[1] ? 1 : -1;
        });
        dist[start] = 0;
        q.offer(new long[]{start, 0});
        while (!q.isEmpty()) {
            long[] p = q.poll();
            int u = (int)p[0];
            long d = p[1];
            if (st[u]) continue;
            st[u] = true;
            dist[u] = d;
            for (int i = h[u]; i != -1; i = ne[i]) {
                int j = e[i], ww = w[i];
                if (dist[j] > d + ww) {
                    q.offer(new long[]{j, d + ww});
                }
            }
        }
    }
}