[Leetcode Weekly Contest]284([Leetcode Weekly Contest]284)

链接:LeetCode

[Leetcode]2200. 找出数组中的所有 K 近邻下标

给你一个下标从 0 开始的整数数组 nums 和两个整数 key 和 k 。K 近邻下标 是 nums 中的一个下标 i ,并满足至少存在一个下标 j 使得 |i – j| <= k 且 nums[j] == key 。

以列表形式返回按 递增顺序 排序的所有 K 近邻下标。

遍历即可。

class Solution {
    public List<Integer> findKDistantIndices(int[] nums, int key, int k) {
        LinkedList<Integer> res = new LinkedList<>();
        List<Integer> indexs = new ArrayList<>();
        for(int i=0;i<nums.length;++i) {
            if(nums[i] == key) indexs.add(i);
        }
        for(var index:indexs) {
            for(int value=index-k;value<=index+k; value++) {
                if(value < 0 || value >= nums.length) continue;
                if(!res.isEmpty() && value<=res.getLast()) continue;
                else res.add(value);
            }
        }
        return res;
    }
}

[Leetcode]2201. 统计可以提取的工件

存在一个 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 中的元素互不相同。

哈希表,记录每个工件所在位置。

class Solution {
    public int digArtifacts(int n, int[][] artifacts, int[][] dig) {
        HashMap<Integer, List<String>> artifactsMap = new HashMap<>();
        HashSet<String> digSet = new HashSet<>();
        for(int i=0;i<artifacts.length;++i) {
            int r1 = artifacts[i][0], c1 =  artifacts[i][1], r2 = artifacts[i][2], c2 =  artifacts[i][3];
            List<String> indexs = new ArrayList<>();
            for(int r=r1;r<=r2;r++) {
                for(int c=c1;c<=c2;c++) {
                    indexs.add(""+r+"-"+c);
                }
            }
            artifactsMap.put(i, indexs);
        }
        for(var d:dig) digSet.add(""+d[0]+"-"+d[1]);
        int res = 0;
        for(var artifactsValue:artifactsMap.values()) {
            boolean succeed = true;
            for(var val: artifactsValue) {
                if (!digSet.contains(val)) {
                    succeed=false;
                    break;
                }
            }
            if(succeed) res ++;
        }
        return res;
    }
}

[Leetcode]2202. K 次操作后最大化顶端元素

给你一个下标从 0 开始的整数数组 nums ,它表示一个 栈 ,其中 nums[0] 是栈顶的元素。

每一次操作中,你可以执行以下操作 之一 :

如果栈非空,那么 删除 栈顶端的元素。
如果存在 1 个或者多个被删除的元素,你可以从它们中选择任何一个,添加 回栈顶,这个元素成为新的栈顶元素。
同时给你一个整数 k ,它表示你总共需要执行操作的次数。

请你返回 恰好 执行 k 次操作以后,栈顶元素的 最大值 。如果执行完 k 次操作以后,栈一定为空,请你返回 -1 。

枚举,分情况讨论即可。注意要特别判断下执行完 k 次操作以后,栈一定为空的情况。

class Solution {
    public int maximumTop(int[] nums, int k) {
        int n = nums.length;
        if(n == 1) return (k&1)!=0 ? -1:nums[0];
        if(k == 0) return nums[0];
        if(k == 1) return nums[1];
        if(k>=n+1) return Arrays.stream(nums).max().getAsInt();
        if(k == n) return Arrays.stream(Arrays.copyOfRange(nums, 0, n-1)).max().getAsInt();
        else {
            return Math.max(nums[k], Arrays.stream(Arrays.copyOfRange(nums, 0, k-1)).max().getAsInt());
        }
    }
}

[Leetcode]2203. 得到要求路径的最小带权子图

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

求三次最短路,dijkstra算法。
我们可以枚举三岔口的交点 x,然后求 \(\textit{src1}\) 和 \(\textit{src2}\) 到 x 的最短路,以及 x 到 \(\textit{dest}\) 的最短路,这可以通过在反图(即所有边反向后的图)上求从 \(\textit{dest}\) 出发的最短路得出。
累加这三条最短路的和,即为三岔口在 x 处的子图的边权和。

class Solution {
    public List<Integer> replaceNonCoprimes(int[] nums) {
        Stack<Integer> res = new Stack<>();
        int n = 0;
        for(int i=0;i<nums.length;i++) {
            res.add(nums[i]);
            n++;
            while (n>=2 && gcd(res.get(n-1), res.get(n-2))>1) {
                int last = res.pop();
                int pre = res.pop();
                int gcdValue = gcd(last, pre);
                res.add(last/gcdValue*pre);
                n--;
            }
        }
        return res;
    }
    public int gcd(int p, int q) {
        if(q==0) return p;
        return gcd(q, p%q);
    }
}

Leetcode

————————

Link: leetcode

[Leetcode]2200. Find all k-nearest neighbor subscripts in the array

Give you an integer array nums with subscript starting from 0 and two integers key and K. The k-nearest neighbor subscript is a subscript i in nums and satisfies that there is at least one subscript j such that | I – J | & lt= K and num [J] = = key.

Returns all k-nearest neighbor subscripts sorted in ascending order in list form.

Just traverse.

class Solution {
    public List<Integer> findKDistantIndices(int[] nums, int key, int k) {
        LinkedList<Integer> res = new LinkedList<>();
        List<Integer> indexs = new ArrayList<>();
        for(int i=0;i<nums.length;++i) {
            if(nums[i] == key) indexs.add(i);
        }
        for(var index:indexs) {
            for(int value=index-k;value<=index+k; value++) {
                if(value < 0 || value >= nums.length) continue;
                if(!res.isEmpty() && value<=res.getLast()) continue;
                else res.add(value);
            }
        }
        return res;
    }
}

[Leetcode]2201. Statistics of the workpieces that can be extracted

There is a grid with n x n size and subscript starting from 0. Some workpieces are buried in the grid. Give you an integer n and a two-dimensional integer array of artifacts with subscript starting from 0. Artifacts describe the position of rectangular workpiece, where artifacts [i] = [r1i, c1i, r2i, c2i] represents the filling of the ith workpiece in the sub grid:

(r1i, c1i) is the coordinate of the upper left cell of the ith workpiece, and
(r2i, c2i) is the coordinate of the lower right cell of the ith workpiece.
You will dig some cells in the grid and remove the landfill. If a part of the workpiece is buried in the cell, this part of the workpiece will be exposed. You can extract all the exposed parts.

Give you a two-dimensional integer array dig with subscript starting from 0, where dig [i] = [RI, CI] indicates that you will mine cells (RI, CI) and return the number of artifacts you can extract.

The generated test cases meet the following requirements:

There are no overlapping two workpieces.
Each piece can only cover up to 4 cells.
The elements in dig are different from each other.

Hash table, which records the location of each workpiece.

class Solution {
    public int digArtifacts(int n, int[][] artifacts, int[][] dig) {
        HashMap<Integer, List<String>> artifactsMap = new HashMap<>();
        HashSet<String> digSet = new HashSet<>();
        for(int i=0;i<artifacts.length;++i) {
            int r1 = artifacts[i][0], c1 =  artifacts[i][1], r2 = artifacts[i][2], c2 =  artifacts[i][3];
            List<String> indexs = new ArrayList<>();
            for(int r=r1;r<=r2;r++) {
                for(int c=c1;c<=c2;c++) {
                    indexs.add(""+r+"-"+c);
                }
            }
            artifactsMap.put(i, indexs);
        }
        for(var d:dig) digSet.add(""+d[0]+"-"+d[1]);
        int res = 0;
        for(var artifactsValue:artifactsMap.values()) {
            boolean succeed = true;
            for(var val: artifactsValue) {
                if (!digSet.contains(val)) {
                    succeed=false;
                    break;
                }
            }
            if(succeed) res ++;
        }
        return res;
    }
}

[Leetcode]2202. Maximize top element after K operations

Give you an integer array nums with subscript starting from 0, which represents a stack, where nums [0] is the element at the top of the stack.

In each operation, you can do one of the following:

If the stack is not empty, delete the element at the top of the stack.
If there is one or more deleted elements, you can select any one of them and add it back to the top of the stack. This element becomes a new top of the stack element.
At the same time, give you an integer k, which indicates the total number of operations you need to perform.

Please return the maximum value of the top element of the stack after just K operations. If the stack must be empty after K operations, please return – 1.

Enumerate and discuss by case. Pay attention to the case that the stack must be empty after K operations.

class Solution {
    public int maximumTop(int[] nums, int k) {
        int n = nums.length;
        if(n == 1) return (k&1)!=0 ? -1:nums[0];
        if(k == 0) return nums[0];
        if(k == 1) return nums[1];
        if(k>=n+1) return Arrays.stream(nums).max().getAsInt();
        if(k == n) return Arrays.stream(Arrays.copyOfRange(nums, 0, n-1)).max().getAsInt();
        else {
            return Math.max(nums[k], Arrays.stream(Arrays.copyOfRange(nums, 0, k-1)).max().getAsInt());
        }
    }
}

[Leetcode]2203. The minimum weighted subgraph of the required path is obtained

Give you an integer n, which represents the number of nodes of a weighted directed graph, with node numbers from 0 to N – 1.
To give you an integer that has a weight from the edge to the edge of the two-dimensional array.
Finally, give you three different integers SRC1, src2 and dest to represent the three different points in the figure.
Please select a subgraph with the smallest edge weight from the graph, so that from SRC1 and src2, DeST can be reached in this subgraph. If such a subgraph does not exist, please return – 1.
The points and edges in the subgraph should be part of the original graph. The edge weight sum of a subgraph is defined as the sum of the weights of all the edges it contains.

Find the third shortest path, Dijkstra algorithm.
We can enumerate the intersection X of three intersections, and then find the shortest path from \ (\ textit {SRC1} \) and \ (\ textit {src2} \) to x, and the shortest path from X to \ (\ textit {dest} \), which can be obtained by finding the shortest path from \ (\ textit {dest} \) on the inverse graph (i.e. the graph after all edges are reversed).
The sum of the three shortest paths is the edge weight sum of the subgraph of the three intersections at X.

class Solution {
    public List<Integer> replaceNonCoprimes(int[] nums) {
        Stack<Integer> res = new Stack<>();
        int n = 0;
        for(int i=0;i<nums.length;i++) {
            res.add(nums[i]);
            n++;
            while (n>=2 && gcd(res.get(n-1), res.get(n-2))>1) {
                int last = res.pop();
                int pre = res.pop();
                int gcdValue = gcd(last, pre);
                res.add(last/gcdValue*pre);
                n--;
            }
        }
        return res;
    }
    public int gcd(int p, int q) {
        if(q==0) return p;
        return gcd(q, p%q);
    }
}

Leetcode