1202.交换字符串中的元素

傷城~ 2023-01-05 05:22 133阅读 0赞

# 前言 #

交换字符中的元素

--------------------

# 题目 #

给你一个字符串 s，以及该字符串中的一些「索引对」数组 pairs，其中 pairs\[i\] = \[a, b\] 表示字符串中的两个索引（编号从 0 开始）。  
你可以 任意多次交换 在 pairs 中任意一对索引处的字符。  
返回在经过若干次交换后，s 可以变成的按字典序最小的字符串。

**示例 1:**

输入：s = "dcab", pairs = [[0,3],[1,2]]
    输出："bacd"
    解释： 
    交换 s[0] 和 s[3], s = "bcad"
    交换 s[1] 和 s[2], s = "bacd"

**示例 2：**

输入：s = "dcab", pairs = [[0,3],[1,2],[0,2]]
    输出："abcd"
    解释：
    交换 s[0] 和 s[3], s = "bcad"
    交换 s[0] 和 s[2], s = "acbd"
    交换 s[1] 和 s[2], s = "abcd"

**示例 3：**

输入：s = "cba", pairs = [[0,1],[1,2]]
    输出："abc"
    解释：
    交换 s[0] 和 s[1], s = "bca"
    交换 s[1] 和 s[2], s = "bac"
    交换 s[0] 和 s[1], s = "abc"

### 解析： ###

说实话，只看leetCode上面的文字描述，估计我本身能力有限，还是没有明白，但是通过实例，可以明白什么意思，首先我们拿到题目以后先审题，当然这是老生常谈的话题，通过上面三个案例，我们可以明白此题意思：

**开始代码实现**:  
很直白就是，输入参数1:字符串，参数2：数组（数组里面包含要交换的索引，然后再输出数据）

# 伪代码 #

package com.zcw.leetcode;
    
    import org.springframework.util.ObjectUtils;
    
    import java.util.ArrayList;
    import java.util.List;
    
    /** * @ClassName : Test1202 * @Description : 1202.交换字符串中的元素 * @Author : zhaocunwei * @Date: 2021-01-11 21:16 */
    public class Test1202 { 
    
        /** * 看到此题，我先是想着把List遍历出来，同时我们通过分析知道返回参数为String， * 先定义好这个String，然后遍历list后，慢慢获取里面的数据 * @param s * @param pairs * @return */
    
        //案例1
        public  static String smallestStringWithSwaps(String s, List<List<Integer>> pairs){ 
            String temp ="";
            //创建list 集合，用来存放获取的数据
            List<String> str = new ArrayList<>();
    
            for(int i=0;i<pairs.size();i++){ 
                List<Integer> integers = pairs.get(i);
                for(int y=0; y<integers.size();y++){ 
                    Integer integer = integers.get(y);
                    /** * dcab * 通过第一个参数知道获取的参数 * 0 3 互换 bcad * 1 2 互换 bacd * dcab -> bcad -> bacd-> bacd */
                    char tempChar1 = 0;
                    char tempChar2 =0;
    
                    char c = s.charAt(integer); //d b a c
    
                    if(tempChar1==0){ 
                        tempChar1=c;
                    }
    
                    str.add(Character.toString(tempChar1));
                }
            }
    
            return "";
        }
    
        public static void main(String[] args) { 
            String s = "dcab";
            List<List<Integer>> pairs = new ArrayList<List<Integer>>();
    
    
            List<Integer> pair = new ArrayList<Integer>();
            pair.add(0);
            pair.add(3);
            pairs.add(pair);
    
            List<Integer> pair1 = new ArrayList<Integer>();
            pair1.add(1);
            pair1.add(2);
            pairs.add(pair1);
    
            String s1 = Test1202.smallestStringWithSwaps(s, pairs);
            System.out.println(s1);
        }
    }

# 代码实现 #

由于本人能力有限，这是从其他博主文章复制过来的，运行后，案例1是可以正确返回，查看代码，需要自己细细的理解：

package com.zcw.leetcode;
    
    
    import java.util.*;
    
    /** * @ClassName : Test1202 * @Description : 1202.交换字符串中的元素 * @Author : zhaocunwei * @Date: 2021-01-11 21:16 */
    public class Test1202 { 
    
            public  static String smallestStringWithSwaps(String s, List<List<Integer>> pairs) { 
                //初始化连通图
                DisjointSetUnion dsu = new DisjointSetUnion(s.length());
                for(List<Integer> pair:pairs){ 
                    //合并
                    dsu.unionSet(pair.get(0),pair.get(1));
                }
                //使用map存储祖先节点到子节点列表的映射，存储并查集结果
                //例如s = "dcab", pairs = [[0,3],[1,2]]
                //0:[d,b] 1:[c,a]
                Map<Integer,List<Character>> map =new HashMap<Integer,List<Character>>();
                for(int i =0;i<s.length();i++){ 
                    int parent = dsu.find(i);//找到该节点的父节点
                    if(!map.containsKey(parent)){ 
                        map.put(parent,new ArrayList<Character>());
                    }
                    map.get(parent).add(s.charAt(i));
                }
                //对map中的值进行排序
                for(Map.Entry<Integer,List<Character>> entry:map.entrySet()){ 
                    Collections.sort(entry.getValue(),new Comparator<Character>(){ 
                        public int compare(Character c1,Character c2){ 
                            return c2-c1;
                        }
                    });
                }
                StringBuffer sb = new StringBuffer();
                for(int i =0;i<s.length();i++){ 
                    int x = dsu.find(i);
                    List<Character> list =map.get(x);
                    sb.append(list.remove(list.size()-1));
                }
                return sb.toString();
    
            }
        }
        //定义并差集类
        class DisjointSetUnion{ 
            int n;  //并查集长度
            int[] rank;  //节点等级
            int[] f;   //存储对应的祖先节点
    
            //构造函数,初始化属性
            public DisjointSetUnion(int n){ 
                this.n = n;
                rank = new int[n];
                Arrays.fill(rank,1);
                f = new int[n];
                for(int i=0;i<n;i++){ 
                    f[i] = i;
                }
            }
    
            //方法find,寻找给节点的祖先
            public int find(int x){ 
                return f[x] == x?x:(f[x]=find(f[x]));
            }
    
            //合并到一个图中，共同有一个祖先
            public void unionSet(int x, int y) { 
                int fx=find(x),fy = find(y);
                if(fx==fy){ 
                    return;
                }
                if(rank[fx]<rank[fy]){ 
                    //swap(fx,fy);
                    int temp = fx;
                    fx=fy;
                    fy=temp;
                }
                //fx级别高，要作为祖先
                rank[fx] +=rank[fy];
                f[fy] = fx;
            }
    
        public static void main(String[] args) { 
            String s = "dcab";
            List<List<Integer>> pairs = new ArrayList<List<Integer>>();
    
    
            List<Integer> pair = new ArrayList<Integer>();
            pair.add(0);
            pair.add(3);
            pairs.add(pair);
    
            List<Integer> pair1 = new ArrayList<Integer>();
            pair1.add(1);
            pair1.add(2);
            pairs.add(pair1);
    
            String s1 = Test1202.smallestStringWithSwaps(s, pairs);
            System.out.println(s1);
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyMzcwOTEz_size_16_color_FFFFFF_t_70]

# 详细说明 #

package com.zcw.leetcode;
    
    
    import java.util.*;
    
    /** * @ClassName : Test1202 * @Description : 1202.交换字符串中的元素 * @Author : zhaocunwei * @Date: 2021-01-11 21:16 */
    public class Test1202 { 
    
        public static String smallestStringWithSwaps(String s, List<List<Integer>> pairs) { 
    
            //初始化连通图，把字符串的长度传到对象的构造方法总
            DisjointSetUnion dsu = new DisjointSetUnion(s.length());
    
            //遍历传递的参数
            for (List<Integer> pair : pairs) { 
                //合并： 传递：参数0，1是因为我们传递的数组只包含两个数据，索引-0 ，索引-1
                dsu.unionSet(pair.get(0), pair.get(1));
            }
            //使用map存储祖先节点到子节点列表的映射，存储并查集结果
            //例如s = "dcab", pairs = [[0,3],[1,2]]
            //0:[d,b] 1:[c,a]
            Map<Integer, List<Character>> map = new HashMap<Integer, List<Character>>();
    
            for (int i = 0; i < s.length(); i++) { 
                //找到该节点的父节点
                int parent = dsu.find(i);
                if (!map.containsKey(parent)) { 
                    map.put(parent, new ArrayList<Character>());
                }
                map.get(parent).add(s.charAt(i));
            }
            //对map中的值进行排序
            for (Map.Entry<Integer, List<Character>> entry : map.entrySet()) { 
                Collections.sort(entry.getValue(), new Comparator<Character>() { 
                    public int compare(Character c1, Character c2) { 
                        return c2 - c1;
                    }
                });
            }
            StringBuffer sb = new StringBuffer();
            for (int i = 0; i < s.length(); i++) { 
                int x = dsu.find(i);
                List<Character> list = map.get(x);
                sb.append(list.remove(list.size() - 1));
            }
            return sb.toString();
    
        }
    
        public static void main(String[] args) { 
            String s = "dcab";
            List<List<Integer>> pairs = new ArrayList<List<Integer>>();
    
    
            List<Integer> pair = new ArrayList<Integer>();
            pair.add(0);
            pair.add(3);
            pairs.add(pair);
    
            List<Integer> pair1 = new ArrayList<Integer>();
            pair1.add(1);
            pair1.add(2);
            pairs.add(pair1);
    
            String s1 = Test1202.smallestStringWithSwaps(s, pairs);
            System.out.println(s1);
        }
    }
    
    /** * 定义并差集类 */
    
    class DisjointSetUnion { 
        /** * 并差集长度 */
        int n;
        /** * 节点等级 */
        int[] rank;
    
        /** * 存储对应的祖先节点 */
        int[] f;
    
        /** * 构造函数,初始化属性 */
        public DisjointSetUnion(int n) { 
            //字符串长度赋值给，对象属性
            this.n = n;
            //初始化当前对象数组，长度为字符串长度
            rank = new int[n];
    
            //rank是对象中数组变量，1是一个rank中元素数据类型的值，作用：填充rank数组中的每个元素都是1
            Arrays.fill(rank, 1);
            //初始化数组，用来存放对应的祖先结点
            f = new int[n];
            //遍历字符串长度，然后填充数组f，为后续的递归进行操作数据
            for (int i = 0; i < n; i++) { 
                f[i] = i;
            }
        }
    
        /** * 方法find,寻找已经传递节点的祖先 */
        public int find(int x) { 
            //三元表达式，递归调用当前方法，相等后返回数据
            return f[x] == x ? x : (f[x] = find(f[x]));
        }
    
        /** * 合并到一个图中，共同有一个祖先 */
        public void unionSet(int x, int y) { 
            int fx = find(x), fy = find(y);
            if (fx == fy) { 
                return;
            }
            if (rank[fx] < rank[fy]) { 
                //swap(fx,fy);
                int temp = fx;
                fx = fy;
                fy = temp;
            }
            //fx级别高，要作为祖先
            rank[fx] += rank[fy];
            f[fy] = fx;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyMzcwOTEz_size_16_color_FFFFFF_t_70]: /images/20221119/b083a8330be9479ca0ab0330c27b5235.png