本文共 5660 字，大约阅读时间需要 18 分钟。
547. 省份数量
题目链接： 思路： 并查集裸题 代码如下class Solution { int[] pre; private int find(int x) { if(x==pre[x]) return x; int temp = find(pre[x]); return temp; } private void union(int a,int b) { int pa = find(a); int pb = find(b); if(pa!=pb) pre[pa]=pb; } public int findCircleNum(int[][] isConnected) { pre = new int[isConnected.length]; for (int i=0;i 1202. 交换字符串中的元素
题目链接： 思路： 由于可以进行无限次交换，所以同处于同一个集合的元素可以交换到集合中的任意位置，所以这个题目可以记下每个集合中的字符串，并将同属于一个集合中的字符串放入一个优先队列中，依次输出同一个集合中的最小元素 代码如下class Solution { private int find(int x,int[] pre) { if(x==pre[x]) return x; int temp = find(pre[x],pre); pre[x] = temp; return temp; } private void unite(int a,int b,int[]pre) { int para = find(a,pre); int parb = find(b,pre); if(para!=parb) pre[para] = parb; } public String smallestStringWithSwaps(String s, List > pairs) { int size = s.length(); int[] pre =new int[size+5]; for (int i=0;i > map = new HashMap<>(); for (int i=0;i queue = map.getOrDefault(par,new PriorityQueue ()); queue.offer(s.charAt(i)); map.put(par,queue); } StringBuilder sb = new StringBuilder(); for (int i=0;i queue = map.get(par); sb.append(queue.poll()); } return sb.toString(); }}
947. 移除最多的同行或同列石头
题目链接： 思路： 因为同行与同列只能保证一个石头，所以可以将同行，同列的石头放入同一个并查集集合中，移出的最大石头数为石头总数-有多少个连通集集合，因为每个连通集最后只会剩余1个石头 代码class Solution { public int removeStones(int[][] stones) { UnionFind unionFind = new UnionFind(); for (int[] stone : stones) { unionFind.union(stone[0] + 10001, stone[1]); } return stones.length - unionFind.getCount(); } private class UnionFind { private Map parent; private int count; public UnionFind() { this.parent = new HashMap<>(); this.count = 0; } public int getCount() { return count; } public int find(int x) { if (!parent.containsKey(x)) { parent.put(x, x); count++; } if (x != parent.get(x)) { parent.put(x, find(parent.get(x))); } return parent.get(x); } public void union(int x, int y) { int rootX = find(x); int rootY = find(y); if (rootX == rootY) { return; } parent.put(rootX, rootY); count--; } }} 721. 账户合并
题目链接 思路： 1.建立一个hash表h1存储每个邮箱的编号 2.建立一个hash表h2建立邮箱与名字之间的映射 3.通过h1这个映射建立并查集 4.将同一集合的邮箱排序和名字一起放入一个List中 代码class Solution { class Union { private int[] pre; public Union(int count) { pre = new int[count]; for (int i=0;i > accountsMerge(List > accounts) { List > ans = new ArrayList<>(); Map indexToEmail = new HashMap<>(); Map indexToName = new HashMap<>(); int emailCount = 0; for (List account: accounts) { String name = account.get(0); for (int i=1;i account:accounts) { String email1 =account.get(1); int pre1 = indexToEmail.get(email1); for (int i=2;i > indexEmail = new HashMap<>(); for (String email: indexToEmail.keySet()) { int index = union.find(indexToEmail.get(email)); List indexSameEmail = indexEmail.getOrDefault(index,new ArrayList<>()); indexSameEmail.add(email); indexEmail.put(index,indexSameEmail); } for (List emails:indexEmail.values()) { Collections.sort(emails); String name = indexToName.get(emails.get(0)); List account = new ArrayList<>(); account.add(name); account.addAll(emails); ans.add(account); } return ans; }}
1584. 连接所有点的最小费用
题目链接 思路： Krusal算法，建立各点的图，对图的权值按从小到大排序，执行krusal算法class Solution { int[] pre; class Adj { int va,vb,adj; Adj(int va,int vb,int adj) { this.va=va; this.vb=vb; this.adj=adj; } } private int find(int x) { if(x==pre[x]) return x; int temp = find(pre[x]); return temp; } private int union(int a,int b) { int pa = find(a); int pb = find(b); if(pa!=pb){ pre[pa]=pb; return 0; } return 1; } public int minCostConnectPoints(int[][] points) { List adjs= new ArrayList<>(); pre = new int[points.length]; for (int i=0;i () { @Override public int compare(Adj o1, Adj o2) { return o1.adj-o2.adj; } }); int ans = 0,count=0; for (int i=0;i 1489. 找到最小生成树里的关键边和伪关键边
题目链接： 思路： 关键边: 去掉这条边生成树的权值会变大或不能生成树 非关键边: 一开始加入这条边之后的生成树权值和最小生成树相同 先计算出最小生成树的权值，然后依次对每条边进行关键边和非关键边的判定 某条边是关键边后不用进行非关键边的判定 代码如下：class Solution { public List addToArrayForm(int[] A, int K) { List arr = new ArrayList<>(); int count=0; int num=K,i=0; for (;i 0;i++) { int ge = num%10; count=(ge+A[i])/10; arr.add((ge+A[i])%10); num/=10; } if(i 0) { while(num>0) { int ge = num%10; arr.add((count+ge)%10); count = (count+ge)/10; num/=10; } } if(count>0) { arr.add(count); } }} 转载地址：http://djaen.baihongyu.com/