Re: [閒聊] 每日LeetCode

https://leetcode.com/problems/min-cost-to-connect-all-points/description/ 1584. Min Cost to Connect All Points 給你一個陣列表示 n 個點 points[i] = [xi, yi]，連結點 i 和點 j 的成本為： |xi - xj| + |yi - yj| ，返回可以連結所有的點的最小成本，且滿足任意兩點之間 只能有一條簡單路徑（不可有迴圈） 思路： 1.先找出所有的邊的長度，並把這些邊的起點、終點、長度保存起來依照長度排序。 （這邊用heap） 2.我們每次都從邊集合裡面拿出最小的邊，然後判斷兩個頂點是否是同一個起點， 如果是的話跳過，如果不是的話把兩個集合合併，這個過程也要更新集合的相關資訊 ，像是成本、集合大小等等。 （這邊用併查集） 3.如果在上面步驟的過程中發現某個集合的點數量等於題目要求的就直接返回。 Java Code： --------------------------------------------------- class Solution { private int[] root; private int[] size; private int[] cost; public int minCostConnectPoints(int[][] points) { int n = points.length; if (n == 1) { return 0; } PriorityQueue<Edge> edges = new PriorityQueue<>(Comparator.comparingInt(e -> e.length)); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (i != j) { int dis = Math.abs(points[i][0] - points[j][0]) + Math.abs(points[i][1] - points[j][1]); edges.add(new Edge(i, j, dis)); } } } root = new int[n]; size = new int[n]; Arrays.fill(size, 1); cost = new int[n]; for (int i = 0; i < n; i++) { root[i] = i; } while (!edges.isEmpty()) { Edge edge = edges.poll(); int res = merge(edge.from, edge.to, edge.length); if (res != -1) { return res; } } return 0; } private int merge(int x, int y, int length) { int rootX = find(x); int rootY = find(y); if (rootX != rootY) { if (rootX > rootY) { int tmp = rootX; rootX = rootY; rootY = tmp; } root[rootY] = root[rootX]; size[rootX] += size[rootY]; cost[rootX] += cost[rootY] + length; } if (size[rootX] == size.length) { return cost[rootX]; } return -1; } private int find(int x) { return root[x] == x ? x : (root[x] = find(root[x])); } } class Edge { int from; int to; int length; public Edge(int from, int to, int length) { this.from = from; this.to = to; this.length = length; } } --------------------------------------------------- 懶 -- https://i.imgur.com/3e5CZfj.jpg --
※ 批踢踢實業坊(ptt.cc), 來自: 122.100.73.13 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1694803452.A.BF4.html