上岸算法LeetCode Weekly Contest 284解题报告

上岸算法 · 发表于 2022-3-14 16:43:15

登录后可回复主题

您需要登录才可以下载或查看，没有帐号？注册账号

x

【 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[i] == 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[n][n];
   for (var p : dig) {
         map[p[0]][p[1]] = 1;
   }

   // preSum[i][j] = (0, 0) ~ (i-1, j-1) square
   int[][] preSum = new int[n + 1][n + 1];
   for (int i = 1; i <= n; i++) {
         for (int j = 1; j <= n; j++) {
            preSum[i][j] = map[i - 1][j - 1] + preSum[i - 1][j] + preSum[i][j - 1] - preSum[i - 1][j - 1];
      }
   }

   int res = 0;
   for (var p : artifacts) {
         int sum = preSum[p[2] + 1][p[3] + 1] - preSum[p[2] + 1][p[1]] - preSum[p[0]][p[3] + 1] + preSum[p[0]][p[1]];
         int real = (p[3] - p[1] + 1) * (p[2] - p[0] + 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[i]);
      }
   }
   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[0], edge[1], edge[2]);
   }
   long[] src1MinPath = dijkstra.dijkstra(src1);
   res = Long.MAX_VALUE;

   boolean[] vis = new boolean[n];
   int[] path = new int[n];
   vis[src2] = true;
   path[0] = 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[path[i]] < Long.MAX_VALUE) {
               res = Math.min(res, len + src1MinPath[path[i]]);
            }
      }
         return;
   }
   for (var nxt : graph.get(cur)) {
         if (vis[nxt.to]) {
            continue;
      }
         vis[nxt.to] = true;
         path[pathLen] = nxt.to;
         dfs(nxt.to, dest, graph, src1MinPath, vis, path, pathLen + 1, len + nxt.len);
         vis[nxt.to] = 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[graph.size()];
   Arrays.fill(res, Long.MAX_VALUE);
   res[start] = 0;
   PriorityQueue<Node> heap = new PriorityQueue<>((o1, o2) -> (int) (o1.len - o2.len));
   heap.add(new Node(start, 0));
   boolean[] visited = new boolean[graph.size()];
   while (!heap.isEmpty()) {
         Node node = heap.poll();
         if (visited[node.to]) {
            continue;
      }
         visited[node.to] = true;
         for (Node next : graph.get(node.to)) {
            if (res[next.to] > node.len + next.len) {
               res[next.to] = node.len + next.len;
               heap.add(new Node(next.to, node.len + next.len));
            }
      }
   }
   return res;
  }
}

帐号		自动登录	找回密码
密码			注册账号

[吹水聊天] 上岸算法LeetCode Weekly Contest 284解题报告

登录后可回复主题

浏览过的版块