上岸算法LeetCode Weekly Contest 284解题报告
【 NO.1 找出数组中的所有 K 近邻下标】解题思路
遍历 nums 找到所有 key 的下标，然后将其左右 k 范围内的下标加到答案数组中即可。
代码展示
class Solution {
public List<Integer> findKDistantIndices(int[] nums, int key, int k) {
List<Integer> res = new ArrayList<>();
int last = -1;
for (int i = 0; i < nums.length; i++) {
if (nums == key) {
for (int j = Math.max(last + 1, i - k); j <= i + k && j < nums.length; j++) {
res.add(j);
last = j;
}
}
}
return res;
}
}
【 NO.2 统计可以提取的工件】
解题思路
二维前缀和的典型应用场景。
代码展示
class Solution {
public int digArtifacts(int n, int[][] artifacts, int[][] dig) {
int[][] map = new int;
for (var p : dig) {
map]] = 1;
}
// preSum = (0, 0) ~ (i-1, j-1) square
int[][] preSum = new int;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
preSum = map + preSum + preSum - preSum;
}
}
int res = 0;
for (var p : artifacts) {
int sum = preSum + 1] + 1] - preSum + 1]] - preSum] + 1] + preSum]];
int real = (p - p + 1) * (p - p + 1);
if (sum == real) {
res++;
}
}
return res;
}
}
【 NO.3 K 次操作后最大化顶端元素】
解题思路
枚举每个位置，判断这个位置经过 k 次操作后能否变成栈顶。详见注释。
代码展示
class Solution {
public int maximumTop(int[] nums, int k) {
int res = -1;
for (int i = 0; i < nums.length; i++) {
if (verify(i, k, nums.length)) {
res = Math.max(res, nums);
}
}
return res;
}
// 判断 k 次操作后能否使得 idx 位置的元素变成栈顶
private boolean verify(int idx, int k, int length) {
if (k <= idx) {
return k == idx; // k < idx 时说明一直弹出也无法使得 idx 达到栈顶；k == idx 时恰好达到栈顶。
}
if (length == 1) {
return k % 2 == 0; // 只有一个元素，此时只能弹出、放回、弹出、放回
}
return k != idx + 1; // 有多个元素，且 k > idx，此时只有在 k == idx + 1 的时候无法做到，因为这时相当于 k == 1 && idx == 0
}
}
【 NO.4 得到要求路径的最小带权子图】
解题思路
求出 src1 到其他所有节点的最短路，然后枚举 src2 到 dest 的所有路径，每找到一条路径 X，枚举 src1 到这个路径上每一个点的最短路 Y, 此时 X 和 Y 的长度和就可以作为备选答案。
代码展示
class Solution {
long res;
public long minimumWeight(int n, int[][] edges, int src1, int src2, int dest) {
Dijkstra dijkstra = new Dijkstra(n);
for (int[] edge : edges) {
dijkstra.addEdge(edge, edge, edge);
}
long[] src1MinPath = dijkstra.dijkstra(src1);
res = Long.MAX_VALUE;
boolean[] vis = new boolean;
int[] path = new int;
vis = true;
path = src2;
dfs(src2, dest, dijkstra.graph, src1MinPath, vis, path, 1, 0);
return res == Long.MAX_VALUE ? -1 : res;
}
private void dfs(int cur, int dest, List<List<Dijkstra.Node>> graph, long[] src1MinPath, boolean[] vis, int[] path, int pathLen, long len) {
if (cur == dest) {
for (int i = 0; i < pathLen; i++) {
if (src1MinPath] < Long.MAX_VALUE) {
res = Math.min(res, len + src1MinPath]);
}
}
return;
}
for (var nxt : graph.get(cur)) {
if (vis) {
continue;
}
vis = true;
path = nxt.to;
dfs(nxt.to, dest, graph, src1MinPath, vis, path, pathLen + 1, len + nxt.len);
vis = false;
}
}
}
class Dijkstra {
static class Node {
int to;
long len;
Node(int to, long len) {
this.to = to;
this.len = len;
}
}
List<List<Node>> graph;
public Dijkstra(int size) {
graph = new ArrayList<>(size);
for (int i = 0; i < size; i++) {
graph.add(new ArrayList<>());
}
}
public void addEdge(int from, int to, long len) {
graph.get(from).add(new Node(to, len));
}
public long[] dijkstra(int start) {
long[] res = new long;
Arrays.fill(res, Long.MAX_VALUE);
res = 0;
PriorityQueue<Node> heap = new PriorityQueue<>((o1, o2) -> (int) (o1.len - o2.len));
heap.add(new Node(start, 0));
boolean[] visited = new boolean;
while (!heap.isEmpty()) {
Node node = heap.poll();
if (visited) {
continue;
}
visited = true;
for (Node next : graph.get(node.to)) {
if (res > node.len + next.len) {
res = node.len + next.len;
heap.add(new Node(next.to, node.len + next.len));
}
}
}
return res;
}
}
页:
[1]