leetcode之并查集+记忆化搜索+回溯+最小生成树刷题总结1

1-连接所有点的最小费用
题目连接：题目连接戳这里！！！

思路:cruskal+并查集
根据题意，我们得到了一张 n 个节点的完全图，任意两点之间的距离均为它们的曼哈顿距离。现在我们需要在这个图中取得一个子图，恰满足子图的任意两点之间有且仅有一条简单路径，且这个子图的所有边的总权值之和尽可能小。能够满足任意两点之间有且仅有一条简单路径只有树，且这棵树包含 n 个节点。我们称这棵树为给定的图的生成树，其中总权值最小的生成树，我们称其为最小生成树。
最小生成树有一个非常经典的解法：Kruskal。

我们首先将这张完全图中的边全部提取到边集数组中，然后对所有边进行排序，从小到大进行枚举，每次贪心选边加入答案。使用并查集维护连通性，若当前边两端不连通即可选择这条边。

class Solution {
    public int minCostConnectPoints(int[][] points) {
        int n = points.length ;
        DisjointSetUnion dsu = new DisjointSetUnion(n) ;
        List<Edge> edges = new ArrayList<Edge>() ;
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                edges.add(new Edge(dist(points,i,j),i,j)) ;
            }
        }

        Collections.sort(edges, new Comparator<Edge>(){ //对所有边进行由小到大排序
            public int compare(Edge edge1, Edge edge2){
                return edge1.len - edge2.len ;
            }
        }) ;

        int ans = 0, num = 1 ;
        for(Edge edge : edges){
            int len = edge.len, x = edge.x, y = edge.y ;
            if(dsu.unionSet(x,y)){
                ans += len;
                num ++ ;
                if(num == n){
                    break ;
                }
            }
        }
        return ans ;
    }
    public int dist(int [][] points, int x, int y){
        return Math.abs(points[x][0]-points[y][0])+Math.abs(points[x][1]-points[y][1]) ;
    }
}
//使用并查集检查是否联通

class DisjointSetUnion{
    int n ;
    int [] f ;
    public DisjointSetUnion(int n){
        this.n = n ;
        this.f = new int [n] ;
        for(int i=0; i<n; i++){
            f[i] = i ;
        }
    }
    public int find(int x){
        if(x!=f[x]){
            f[x] = find(f[x]) ;
        }
        return f[x] ;
    }
    public boolean unionSet(int x, int y){
        int fx = find(x), fy = find(y) ;
        if(fx==fy){
            return false ;
        }
        f[fx] = fy ;
        return true ;
    }
}

class Edge{ //定义一个边类
    int len,  x, y ;
    public Edge(int len, int x, int y){
        this.len = len ;
        this.x = x ;
        this.y = y ;
    }
}

2-最少体力消耗路径
题目链接：题目连接戳这里！！！

思路：并查集
我们将这 m*n 个节点放入并查集中，实时维护它们的连通性。

由于我们需要找到从左上角到右下角的最短路径，因此我们可以将图中的所有边按照权值从小到大进行排序，并依次加入并查集中。当我们加入一条权值为 x 的边之后，如果左上角和右下角从非连通状态变为连通状态，那么 x 即为答案。

class Solution {
    public int minimumEffortPath(int[][] heights) {
        int m = heights.length ;
        int n = heights[0].length ;
        List<int[]> edges = new ArrayList<int[]>() ;
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                int id = i * n + j ;
                if(i>0){
                    edges.add(new int [] {id-n, id, Math.abs(heights[i][j]-heights[i-1][j])}) ;
                }
                if(j>0){
                    edges.add(new int [] {id-1, id, Math.abs(heights[i][j]-heights[i][j-1])}) ;
                }
            }
        }
        Collections.sort(edges, new Comparator<int[]>(){ //按照边的权值由小到大排序
            public int compare(int [] edge1, int [] edge2){
                return edge1[2] - edge2[2] ;
            }
        }) ;

        UnionFind uf = new UnionFind(m*n) ;
        int ans = 0 ;
        for(int [] edge : edges){
            int x = edge[0], y = edge[1], v = edge[2] ;
            uf.unite(x,y) ;
            if(uf.connected(0,m*n-1)){
                ans = v ;
                break ;
            }
        }
        return ans ;
    }
}

// 并查集模板
class UnionFind {
    int[] parent;
    int n ;

    public UnionFind(int n) {
        this.n = n;
        this.parent = new int[n];

        for (int i = 0; i < n; ++i) {
            parent[i] = i;
        }
    }
    
    public int findset(int x) {
        return parent[x] == x ? x : (parent[x] = findset(parent[x]));
    }
    
    public boolean unite(int x, int y) {
        x = findset(x);
        y = findset(y);
        if (x == y) {
            return false;
        }
        parent[y] = x;
    
        return true;
    }
    
    
    public boolean connected(int x, int y) {
        x = findset(x);
        y = findset(y);
        return x == y;
    }
}

3-交换字符串中的元素
题目链接：题目链接戳这里！！！

思路：并查集
1-并查集对每个元素索引，实现属于同一联通分量元素的合并
2-遍历字符串s，找出每个索引在并查集中的代表元，同属于一个代表元的元素放到一起。
3-对同属于每一个联通分量中的字符按照ASCII码进行升序排序。
4-重新生成一个长度和s相同的字符串，对于每一个索引，查询索引在并查集中的代表元，再从哈希表中获得这个代表元对应的字符集列表，从中移除 ASCII 值最小的字符依次拼接起来。

public class Solution {

    public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
        if (pairs.size() == 0) {//没有交换
            return s;
        }
        int n = s.length() ;
        UnionFind uf = new UnionFind(n) ;
        for(int i=0; i<pairs.size(); i++){ //根据索引构建并查集
            int index1 = pairs.get(i).get(0) ;
            int index2 = pairs.get(i).get(1) ;
            uf.union(index1,index2) ;
        }
        char [] c = s.toCharArray() ;
        Map<Integer,PriorityQueue<Character>> map = new HashMap<>(n) ;
        for(int i=0; i<n; i++){ //遍历元素，找到代表元，并代表元相同的放到一个集合，并按字典序排序
        int root = uf.find(i) ;
        if(map.containsKey(root)){
            map.get(root).add(c[i])  ;
        }else{
            PriorityQueue<Character> minHeap = new PriorityQueue<>() ;
            minHeap.add(c[i]) ;
            map.put(root,minHeap) ;
        }
        }

        StringBuilder ans = new StringBuilder() ;
        for(int i=0; i<n; i++){
            int root = uf.find(i) ;
            ans.append(map.get(root).poll()) ;
        }
        return ans.toString() ;

    }
}
class UnionFind{
    int n ;
    int [] parent ;
    public UnionFind(int n){
        this.n = n ;
        this.parent = new int [n] ;
        for(int i=0; i<n; i++){
            parent[i] = i ;
        }
    }
    public int find(int x){
        if(x != parent[x]){
            parent[x] = find(parent[x]) ;
        }
        return parent[x] ;
    }
    public void union(int x, int y){
        int root1 = find(x) ;
        int root2 = find(y) ;
        if(root1==root2){
            return ;
        }
        parent[root1] = root2 ;
    }
}

4-可能的二分法
题目链接：题目链接戳这里！！！

思路1：邻接表+并查集
1-对于每个不喜欢的建立双向邻接表，将每个人，不喜欢的放到一个集合里。
2-对每个集合的元素进行并查集合并。
3-如果对于每个元素，其邻接元素与自己在同一个集合，则返回false,否则返回true.

class Solution {
    public boolean possibleBipartition(int n, int[][] dislikes) {
        if(dislikes.length==0){
            return true ;
        }
        Map<Integer, List<Integer>> edges = new HashMap<>() ;
        UnionFind uf = new UnionFind(n) ;
        for(int [] dislike : dislikes){
          List<Integer> temp1 = edges.getOrDefault(dislike[0],new ArrayList<>()) ;
          temp1.add(dislike[1]) ;
          edges.put(dislike[0],temp1) ;
          List<Integer> temp2 = edges.getOrDefault(dislike[1], new ArrayList<>()) ;
          temp2.add(dislike[0]) ;
          edges.put(dislike[1],temp2) ;
        }
        for(int i : edges.keySet()){
            List<Integer> list = edges.get(i) ;
            for(int neighbors : list){
                if(uf.find(neighbors) == uf.find(i)){
                    return false ;
                }
                uf.union(neighbors,list.get(0)) ;
            }
        }
        return true ;
    }
}
 class UnionFind{
        int n ;
        int [] parent ;
        public UnionFind(int n){
            this.n = n ;
            this.parent = new int [n+1] ;
            for(int i=1; i<=n; i++){
                parent[i] = i ;
            }
        }
        public int find(int x){
            if(x != parent[x]){
                parent[x] = find(parent[x]) ;
            }
            return parent[x] ;
        }
        public void union(int x, int y){
            int root1 = find(x) ;
            int root2 = find(y) ;
            if(root1==root2){
                return ;
            }
            parent[root1] = root2 ;
        }
    }

思路2：邻接表+dfs+染色法

尝试将每个人分配到一个组是很自然的想法。假设第一组中的人是红色，第二组中的人是蓝色。

如果第一个人是红色的，那么这个人不喜欢的人必须是蓝色的。然后，任何不喜欢蓝色人的人都是红色的，那么任何不喜欢红色人的人都是蓝色的，依此类推。

如果在任何时候存在冲突，那么这个任务是不可能的完成的，因为从第一步开始每一步都符合逻辑。如果没有冲突，那么着色是有效的，所以答案是 true。

class Solution {
    Map<Integer,Integer> map ;
    List<List<Integer>> list = new ArrayList<>() ;
    public boolean possibleBipartition(int n, int[][] dislikes) {
        if(dislikes.length==0){
            return true ;
        }
        //dfs+染色法
        for(int i=0; i<=n; i++){
            list.add(new ArrayList<>()) ;
        }
        for(int [] dislike : dislikes){
            list.get(dislike[0]).add(dislike[1]) ;
            list.get(dislike[1]).add(dislike[0]) ;
        }
        map = new HashMap<>() ;
        for(int i=1; i<=4; i++){
            if(!map.containsKey(i) && !dfs(i,0)){
                return false ;
            }
        }
        return true ;
        }
        public boolean dfs(int i, int color){
            if(map.containsKey(i)){
                return map.get(i) == color ;
            }
            map.put(i,color) ;
            for(int neighbors : list.get(i)){
                if(!dfs(neighbors,color^1)){
                    return false ;
                }
            }
            return true ;
        }
    }

5-将整数按权重进行排列
题目链接：题目链接戳这里！！！

思路1:递归法求出每个数字的权重，权重不同时候，根据权重升序排序，权重相同根据整数升序排序。

class Solution {
    public int getKth(int lo, int hi, int k) {
        //递归法
        List<Integer> list = new ArrayList<>() ;
        for(int i=lo; i<=hi; i++){
            list.add(i) ;
        }
        Collections.sort(list, new Comparator<Integer>(){
            public int compare(Integer u, Integer v){
            if(f(u) != f(v)){
                return f(u) - f(v) ;
            }else{
                return u - v ;
            }
            }
        }) ;
        return list.get(k-1) ;
    }

    public int f(int x){
        if(x==1){
            return 0 ;
        }else if(x%2==0){
            return 1 + f(x/2) ;
        }else{
            return 1 + f(3*x+1) ;
        }
    }
}

思路2：记忆化搜索
用hashmap去存储已经搜索过的，防止重复搜索。

class Solution {
    Map<Integer, Integer> map = new HashMap<>() ;
    public int getKth(int lo, int hi, int k) {
        //递归法
        List<Integer> list = new ArrayList<>() ;
        for(int i=lo; i<=hi; i++){
            list.add(i) ;
        }
        Collections.sort(list, new Comparator<Integer>(){
            public int compare(Integer u, Integer v){
            if(f(u) != f(v)){
                return f(u) - f(v) ;
            }else{
                return u - v ;
            }
            }
        }) ;
        return list.get(k-1) ;
    }

    public int f(int x){
     if(!map.containsKey(x)){
         if(x==1){
             map.put(x,0) ;
         }else if(x%2==0){
             map.put(x,f(x/2)+1) ;
         }else{
             map.put(x,f(3*x+1)+1) ;
         }
     }
     return map.get(x) ;
  
    }
}

6-将数组拆分成斐波那契数列
题目链接：题目链接戳这里！！！

思路：回溯+剪支

对于这道题也一样，我们先把字符串不断的截取，看一下能不能构成斐波那契序列，如果不能就回到上一步，如果能就继续往下走。

class Solution {
    public List<Integer> splitIntoFibonacci(String num) {
       //回溯+剪支
       List<Integer> res = new ArrayList<>() ;
       char [] c = num.toCharArray() ;
       backtrace(res,c,0) ; 
       return res ;
    }
    public boolean backtrace(List<Integer> res, char [] c, int index){
        if(index==c.length && res.size()>=3){ //找到满足的组合
            return true ;
        }
        for(int i=index; i<c.length; i++){
            if(c[index]=='0' && i>index){ //两位数以上，0不能作首位
                break ;
            }
            long num = sub(c, index, i) ;
            if(num>Integer.MAX_VALUE){ //超出最大值
                break ;
            }
            int size = res.size() ;
            if(size>=2 && num > res.get(size-1)+res.get(size-2)){ //后面截取的更大，不可能满足要求
                break ;
            }
            if(size<=1 || num == res.get(size-1) + res.get(size-2)){//满足要求
                res.add((int)num) ;
                if(backtrace(res,c,i+1)){
                    return true ;
                }
                res.remove(res.size()-1) ;
            }
        }
        return false ;
    }
    public long sub(char [] c, int start, int end){ //截取字符串的数值
        long ans = 0 ;
        for(int i=start; i<=end; i++){
            ans = ans * 10 + c[i] -'0' ;
        }
        return ans ;
    }
}