省份数量

题目：有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。

返回矩阵中 省份 的数量

提示：
1 <= n <= 200
n == isConnected.length
n == isConnected[i].length
isConnected[i][j] 为 1 或 0
isConnected[i][i] == 1
isConnected[i][j] == isConnected[j][i]

题目截图

思路：这个题是每日一题，我也不知道我做过没做过了，反正思路就是朋友圈的思路。是一个圈子的放一起。不是一起的分开放。这里用set来实现，所有的set里都没有那么就单独开圈子。我去代码试试。

class Solution {
    public int findCircleNum(int[][] M) { 
        int n = 0;
        for(int i = 0;i<M.length;i++) {
            if(M[i][i] == 1) {//说明这个人没被纳入圈子，可以单独开圈
                n++;
                M[i][i] = -1;
                //把和这个能一个圈的都纳入
                dfs(M, i);
            }
        }       
        return n;
    }
    public void dfs(int[][] M,int i) {      
        //如果跟这个有关系说明是一个圈子
        for(int k = 0;k<M.length;k++) {
            if(M[i][k] == 1) {
                M[i][k] = -1;
                M[k][k] = -1;
                //M[i][k] = 1 说明i和k有关系，k进入i的圈子.同时k圈子里的也都进入
                dfs(M, k);
            }
        }
    }
}

做完了我才发现这个题果然ac过，而且是两个月前，我说怎么似曾相识的呢。。。这个就是思路，只要思路对就没啥难度，下一题了。

最长重复子数组

题目：给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。

示例：
输入：
A: [1,2,3,2,1]
B: [3,2,1,4,7]
输出：3
解释：
长度最长的公共子数组是 [3, 2, 1] 。
提示：
1 <= len(A), len(B) <= 1000
0 <= A[i], B[i] < 100

思路：又是重复子串问题。因为这个数组其实比字符串还好处理。长度都很小，我觉得暴力法都有可能ac，我先去尝试写下代码。
暴力法果然过了，先贴代码:

class Solution {
    public int findLength(int[] A, int[] B) {
        int res = 0;
        for(int i = 0;i<A.length-res;i++) {                     
            for(int j = 0;j<B.length-res;j++) {  
                int idx = i;
                int idx2 = j;
                int count = 0;
                while(idx<A.length && idx2<B.length &&A[idx] == B[idx2]) {
                    count++;   
                    idx++;
                    idx2++;
                }
                res = Math.max(res, count); 
            }           
        }
        return res;
    }
}

这个代码就没啥逻辑了，纯暴力一个一个去计数的。至于性能肯定是好不了，然後说起优化，之前的子序列问题都可以用dp，这种子串应该也可以，我去用dp试试看：

class Solution {
    public int findLength(int[] A, int[] B) {
        int res = 0;
        int[][] dp = new int[A.length+1][B.length+1];
        for(int i = 0;i<A.length;i++) {                     
            for(int j = 0;j<B.length;j++) {  
                if(A[i] == B[j]) {
                    dp[i+1][j+1] = dp[i][j]+1;
                }else {
                    dp[i+1][j+1] = 0;
                }
                res = Math.max(res, dp[i+1][j+1]);
            }           
        }
        return res;
    }
}

性能还是没上来，但是我觉得解法应该没啥问题，dp方法因为要连续，所以不等以后直接补0而不是前面最大值。反正这个题就这样了，我去看看题解吧：

class Solution {
    public int findLength(int[] A, int[] B) {
        int left=1;
        int right=Math.min(A.length,B.length)+1;
        digits=new int[Math.min(A.length,B.length)];
        digits[0]=1; 
        int R=107;
        for(int i=1; i<digits.length; i++)
            digits[i]=digits[i-1]*R;
        while(left<right){
            int mid=(left+right)>>1;
            if(check(A,B,mid)) left=mid+1;
            else right=mid;
        }
        return left-1;
    }
    int[] digits;
    boolean check(int [] A, int[] B, int len){
        int R=107, hashA=0, hashB=0;
        Set<Integer> set=new HashSet<>(A.length-len+1);
        for(int i=0; i<len; i++)
            hashA=hashA*R+A[i]+1;   
        set.add(hashA);
        for(int i=len; i<A.length; i++){
            hashA-=digits[len-1]*(A[i-len]+1);
            hashA=hashA*R+A[i]+1;
            set.add(hashA);
        }
        for(int i=0; i<len; i++)
            hashB=hashB*R+B[i]+1;   
        if(set.contains(hashB)) return true;
        for(int i=len; i<B.length; i++){
            hashB-=digits[len-1]*(B[i-len]+1);
            hashB=hashB*R+B[i]+1;
            if(set.contains(hashB)) return true;
        }   
        return false;
    }
}

性能第一的代码。据说是用的二分+hash。反正拆开每个字我都认识，放一起就有点看不懂了，附上解释截图：

二分+hash思路

大概的意思的因为都是正整数，所以用某种方式处理子串，相同的数字会有一样的一个hash值。我们根据值一样不一样判断是不是相同的子串？反正中文看我能看懂，怎么实现的一脸懵B。。这个我就不难为自己了，下一题了。

账户合并

题目：给定一个列表 accounts，每个元素 accounts[i] 是一个字符串列表，其中第一个元素 accounts[i][0] 是 名称 (name)，其余元素是 emails 表示该账户的邮箱地址。现在，我们想合并这些账户。如果两个账户都有一些共同的邮箱地址，则两个账户必定属于同一个人。请注意，即使两个账户具有相同的名称，它们也可能属于不同的人，因为人们可能具有相同的名称。一个人最初可以拥有任意数量的账户，但其所有账户都具有相同的名称。合并账户后，按以下格式返回账户：每个账户的第一个元素是名称，其余元素是按顺序排列的邮箱地址。账户本身可以以任意顺序返回。

示例 1：
输入：
accounts = [["John", "johnsmith@mail.com", "john00@mail.com"], ["John", "johnnybravo@mail.com"], ["John", "johnsmith@mail.com", "john_newyork@mail.com"], ["Mary", "mary@mail.com"]]
输出：
[["John", 'john00@mail.com', 'john_newyork@mail.com', 'johnsmith@mail.com'], ["John", "johnnybravo@mail.com"], ["Mary", "mary@mail.com"]]
解释：
第一个和第三个 John 是同一个人，因为他们有共同的邮箱地址 "johnsmith@mail.com"。
第二个 John 和 Mary 是不同的人，因为他们的邮箱地址没有被其他帐户使用。
可以以任何顺序返回这些列表，例如答案 [['Mary'，'mary@mail.com']，['John'，'johnnybravo@mail.com']，
['John'，'john00@mail.com'，'john_newyork@mail.com'，'johnsmith@mail.com']] 也是正确的。
提示：
accounts的长度将在[1，1000]的范围内。
accounts[i]的长度将在[1，10]的范围内。
accounts[i][j]的长度将在[1，30]的范围内。

思路：有时候想想力扣也挺不容易，为了出题提出各种奇葩的情景。。先说这个题，我觉得我应该可以理解为名字不同账号一定不同。名字相同如果有相同的账号说名是一个人，可以合并，否则说明不是一个人，还是不可以合并。这种题我第一想法就是map。但是因为不同账户也可能有相同的名称。。。是不是又是一个朋友圈的题?反正我目前的想法是暴力法，挨个去判断呗。我去试着写代码了。
直接贴代码：

class Solution {
    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        Map<String, String> emailToName = new HashMap();
        Map<String, ArrayList<String>> graph = new HashMap();
        for (List<String> account: accounts) {
            String name = "";
            for (String email: account) {
                if (name == "") {
                    name = email;
                    continue;
                }
                graph.computeIfAbsent(email, x-> new ArrayList<String>()).add(account.get(1));
                graph.computeIfAbsent(account.get(1), x-> new ArrayList<String>()).add(email);
                emailToName.put(email, name);
            }
        }

        Set<String> seen = new HashSet();
        List<List<String>> ans = new ArrayList();
        for (String email: graph.keySet()) {
            if (!seen.contains(email)) {
                seen.add(email);
                Stack<String> stack = new Stack();
                stack.push(email);
                List<String> component = new ArrayList();
                while (!stack.empty()) {
                    String node = stack.pop();
                    component.add(node);
                    for (String nei: graph.get(node)) {
                        if (!seen.contains(nei)) {
                            seen.add(nei);
                            stack.push(nei);
                        }
                    }
                }
                Collections.sort(component);
                component.add(0, emailToName.get(email));
                ans.add(component);
            }
        }
        return ans;
    }
}

做起来才发现这个题好复杂，真的是中等难度么？按照朋友圈的思路，要深搜才能把一个圈子的放一起，而且还要批量把圈子里的所有人都放一起。越写越蒙，从开始到放弃。。
然后换一种方式深搜，本来我第一版是存下标的，硬生生改成字面量省的自己晕了。。反正seen用来存处理过了的邮箱名，每个处理过的都深搜完了，也就是这个账户对应的用户的所有账户都完事了。反正写的挺绕的，我这个代码也是参考官方题解写的，这个题说难也没那么难，说简单各种数据处理真的是繁琐的不行，反正就这样吧， 我去看看性能第一的代码：

class Solution {
    
    int[] f = new int[10001];
    HashMap<String, Integer> emailToId = new HashMap<>();
    HashMap<String, String> emailToName = new HashMap<>();
    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        for (int i = 0; i <= 10000; i++) {
            f[i] = i;
        }
        
        int id = 0;
        for (List<String> account : accounts) {
            String name = "";
            for (String email : account) {
                if (name.equals("")) {
                    name = email;
                    continue;
                }
                emailToName.put(email, name);
                
                if (!emailToId.containsKey(email)) {
                    emailToId.put(email, id++);
                }
                union(emailToId.get(email), emailToId.get(account.get(1)));
            }
        }
        
        Map<Integer, List<String>> emails = new HashMap<>();
        
        for (String email : emailToId.keySet()) {
            int index = find(emailToId.get(email));
            emails.computeIfAbsent(index, k -> new LinkedList<>()).add(email);
        }
        
        for (List<String> list : emails.values()) {
            Collections.sort(list);
            list.add(0, emailToName.get(list.get(0)));
        }
        
        return new ArrayList<>(emails.values());
    }
    
    private int find(int x) {
        if (x != f[x]) {
            f[x] = find(f[x]);
        }
        return f[x];
    }
    
    private void union(int a, int b) {
        int rootA = find(a);
        int rootB = find(b);
        
        if (rootA != rootB) {
            f[rootA] = rootB;
        }
    }
}

感觉是标准并查集，又是我知识盲区。。。这个题就这样了。

删除注释

题目：给一个 C++ 程序，删除程序中的注释。这个程序source是一个数组，其中source[i]表示第i行源码。 这表示每行源码由\n分隔。

在 C++ 中有两种注释风格，行内注释和块注释。

字符串// 表示行注释，表示//和其右侧的其余字符应该被忽略。

字符串/* 表示一个块注释，它表示直到/的下一个（非重叠）出现的所有字符都应该被忽略。（阅读顺序为从左到右）非重叠是指，字符串//并没有结束块注释，因为注释的结尾与开头相重叠。

第一个有效注释优先于其他注释：如果字符串//出现在块注释中会被忽略。 同样，如果字符串/*出现在行或块注释中也会被忽略。

如果一行在删除注释之后变为空字符串，那么不要输出该行。即，答案列表中的每个字符串都是非空的。

样例中没有控制字符，单引号或双引号字符。比如，source = "string s = "/* Not a comment. */";" 不会出现在测试样例里。（此外，没有其他内容（如定义或宏）会干扰注释。）

我们保证每一个块注释最终都会被闭合， 所以在行或块注释之外的/*总是开始新的注释。

最后，隐式换行符可以通过块注释删除。 有关详细信息，请参阅下面的示例。

从源代码中删除注释后，需要以相同的格式返回源代码。

示例 1:
输入:
source = ["/*Test program /", "int main()", "{ ", " // variable declaration ", "int a, b, c;", "/ This is a test", " multiline ", " comment for ", " testing /", "a = b + c;", "}"]
示例代码可以编排成这样:
/Test program /
int main()
{
// variable declaration
int a, b, c;
/ This is a test
multiline
comment for
testing */
a = b + c;
}
输出: ["int main()","{ "," ","int a, b, c;","a = b + c;","}"]
编排后:
int main()
{

int a, b, c;
a = b + c;
}
解释:
第 1 行和第 6-9 行的字符串 /* 表示块注释。第 4 行的字符串 // 表示行注释。
示例 2:
输入:
source = ["a/comment", "line", "more_comment/b"]
输出: ["ab"]
解释: 原始的 source 字符串是 "a/comment\nline\nmore_comment/b", 其中我们用粗体显示了换行符。删除注释后，隐含的换行符被删除，留下字符串 "ab" 用换行符分隔成数组时就是 ["ab"].
注意:
source的长度范围为[1, 100].
source[i]的长度范围为[0, 80].
每个块注释都会被闭合。
给定的源码中不会有单引号、双引号或其他控制字符。

思路：这个题的我目前的思路是把所有的换行符用用一个特殊符号表示，然后所有的代码都变成一个字符串了。遇到//就删除到下一个换行符之前，如果是代码块注释的话遇到后面的那个都删除。反正思路大概就这样，我去实现试试。
好了，第一版代码ac了，面向测试案例变成，不断通过错误原因修改代码。。我先贴出来：

class Solution {
    public List<String> removeComments(String[] source) {
        StringBuffer sb = new StringBuffer();
        //因为题目说不会有单引号，所以这里用单引号代表换行
        for(String s:source) sb.append("'"+s);
        String string = sb.substring(1).toString();
        StringBuffer sb1 = new StringBuffer();
        int cur = 0;//0代表可以正常输出，1代表行内注释中。2代表处于代码块注释中
        for(int i = 0;i<string.length();i++) {
            if(cur == 0) {//当前正常输出，如果遇到注释了修改当前状态
                if(string.charAt(i) != '/' || (string.charAt(i+1) != '/' && string.charAt(i+1) != '*')) {//说明不是注释
                    sb1.append(string.charAt(i));
                }else {//是注释的话判断是行内还是注释块,行内状态变1，注释块状态变2
                    i++;
                    cur=string.charAt(i) == '/'?1:2;
                }
            }else if(cur == 1 && string.charAt(i) == '\'') {//当前处于行内注释中，遇到下一行自动失效
                sb1.append("'");
                cur = 0;
            }else if(cur == 2) {//说明处在代码块注释中，直到遇到结束注释才会结束
                if(string.charAt(i) == '*' && string.charAt(i+1)=='/') {
                     cur = 0;
                     i++;
                }
            }
        }
        String[] res = sb1.toString().split("'");       
        List<String> res1 = new ArrayList<String>();
        for(String s:res) {
            if(!s.equals(""))res1.add(s);
        }
        return res1;
    }
}

因为要自己理思路，所以注释写的挺全的了我觉得，反正这个题这个思路肯定是没问题，但是性能不太好，我去看看性能排行第一的代码：

class Solution {
    public List<String> removeComments(String[] source) {
        boolean blockmode = false;
        int cur = 0;
        StringBuilder sb = new StringBuilder();
        List<String> ans = new ArrayList();
        for(int i=0;i<source.length;){
            String s = source[i];
            if(blockmode){
                int idx = s.indexOf("*/", cur);
                if(idx==-1){
                    cur = 0;
                    i++;
                }else if(idx==(s.length()-2)){
                    cur = 0;
                    i++;
                    if(sb.length()!=0){
                        ans.add(sb.toString());
                    }
                    sb = new StringBuilder();
                }else{
                    cur = idx+2;
                }
                if(idx!=-1){
                    blockmode = false;
                }
            }else{
                int idx1 = s.indexOf("/*", cur);
                int idx2 = s.indexOf("//", cur);
                if(idx1==-1&&idx2==-1){
                    sb.append(s.substring(cur));
                    cur = 0;
                    i++;
                    if(sb.length()!=0){
                        ans.add(sb.toString());
                    }
                    sb = new StringBuilder();
                }else if(idx1==-1){
                    sb.append(s.substring(cur, idx2));
                    cur = 0;
                    i++;
                    if(sb.length()!=0){
                        ans.add(sb.toString());
                    }
                    sb = new StringBuilder();
                }else if(idx2==-1){
                    sb.append(s.substring(cur, idx1));
                    blockmode = true;
                    if(s.length()==idx1+2){
                        cur = 0;
                        i++;
                        if(sb.length()!=0){
                            ans.add(sb.toString());
                        }
                        sb = new StringBuilder();
                    }else{
                        cur = idx1+2;
                    }
                }else{
                    if(idx1<idx2){
                        sb.append(s.substring(cur, idx1));
                        blockmode = true;
                        if(s.length()==idx1+2){
                            cur = 0;
                            i++;
                            if(sb.length()!=0){
                                ans.add(sb.toString());
                            }
                            sb = new StringBuilder();
                        }else{
                            cur = idx1+2;
                        }
                    }else{
                        sb.append(s.substring(cur, idx2));
                        cur = 0;
                        i++;
                        if(sb.length()!=0){
                            ans.add(sb.toString());
                        }
                        sb = new StringBuilder();
                    }
                }
            }
        }
        return ans;
    }
}

额，这个性能第一的代码的代码量。。。反正思路上也是一次遍历。只不过人家没有合成一个字符串遍历。。事后想想确实这个没啥必要。。一开始我也不知道怎么灵机一动的。。反正这个题比较简单，就不多说了，下一题。

交换字符串中的元素

题目：给你一个字符串 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"
提示：
1 <= s.length <= 10^5
0 <= pairs.length <= 10^5
0 <= pairs[i][0], pairs[i][1] < s.length
s 中只含有小写英文字母

思路：这个题是今天的每日一题，感觉这个月简直就是并查集+图论的月份。。简单说下这个题：这里有个概念：每两个可以互换的词都可以随意变化顺序。同理 如果 0-1，0-2的话，那么就是这三个可以随意变换顺序。所以只要知道每一个可以随意变化的圈子，让其从小到大排序就ok了。而这个圈子的获取就离不开并查集了。
因为并查集我也是在刷题的过程中野蛮生长，随缘写法，所以正好今天又又又又刷到这种题目了，所以我打算简单的说一下这个并查集：

java 并查集

这个并查集一般是发生在两两相关，整个圈子乱七八糟一团乱的时候使用的，最简单的一个例子（我也是看网上的说法）：比如古代江湖，俩人的关系不是朋友就是敌人。而朋友的朋友也是朋友。这两句话延伸出一大群乱七八糟莫名其妙的联系： A,B朋友，A,C朋友，B,D朋友。这样一圈看下来A.B,C,D都是朋友。继续往下 F,E是朋友。那么A,F是连不到一起去的，所以A,F是敌人。这才几个人就要一层一层找了，要是几百上千个。。。朋友的朋友的朋友....从而，并查集就起了大用了：
这里有两个需要做的：一个是寻根（设置一个人作为根）。一个是并查。
简单的并查集的概念和场景说完了，下面说实现：
因为如上说的Z,A朋友，A,B朋友，B，C朋友，C,D朋友，D,E朋友，E,F朋友。现在想知道Z和F是不是朋友一层一层往下找就很麻烦。按照一个常规思路就要归圈子了：比如江湖上的门派。你是武当派，我是武当派，那我们就是朋友。这个武当派是人为的去归纳的一个门派。其实换种说法:你是张三丰门人，我也是，那我们就是朋友。而这个张三丰，就是我们认为的一个圈子的根。
同理：你是张三丰门人，我是灭绝师太的门人，咱俩就是敌人，所以这就是两个圈子。
但是会出现一种情况：张三丰因为喜欢郭襄，所以说峨眉派的人我也认这个朋友，于是乎所有的张三丰门人和灭绝师太门人也是朋友了。
当然了，不非要领头有关系，比如说周芷若和宋青书结婚了，所以两个门派是朋友了，这个也可以。
不管是张三丰因为暗恋所以合二为一，还是宋青书周芷若结婚合二为一，反正这个两个圈子的人合到一起的行为就是并查。
而根据某个人去往上一层一层理，最终找出这个圈子的代表人物的过程就是寻根。
寻根和并查两中操作把一个集合中的人分成不同的圈子，这个过程就是并查集算法。
其实这个并查集算法是有一个标准的模板的，下面是java版本的代码：

class DSU {
    int[] parent;

    public DSU(int len) {
        parent = new int[len];
        for (int i = 0; i < len; ++i)
            parent[i] = i;
    }

    public int find(int x) {
        return parent[x] != x ? parent[x] = find(parent[x]) : x;
    }

    public void union(int x, int y) {
        parent[find(x)] = find(y);
    }
}

注意这里parent的初始大小要根据要查询集合中的大小决定。比如江湖上一共就一百个人，那么这里只要初始化100个容量就可以。一千个人就初始化1000个。。依此类推。
而这个类的初始化方法就是最初把每一个人都作为一个独立的圈子来看待。
而下面的find方法就是寻根，找寻这个圈子中的领头人。
union方法就是并查，把无关系的两个人联系到一起。
实现起来其实都挺简单的，这里除了寻根用到了递归剩下的都是只要思路懂了就没啥难度。
然后并查集就简单介绍到这里，下面开始正式说这个题。

这个题只要会了并查集实现起来比较简单，下面是ac代码：

class Solution {    
    public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
        //这里有个概念：每两个可以互换的词都可以随意变化顺序。同理 如果 0-1，0-2的话，那么就是这三个可以随意变换顺序
        //所以只要知道每一个可以随意变化的圈子，让其从小到大排序就ok了
        //而这个随意变化的圈子的获取，就是并查集了。
        int len = s.length();
        //这个题最大值是10的5次方。所以这里并查集初始大小100000
        DSU dsu = new DSU(100000);
        //并查
        for (List<Integer> list : pairs)
            dsu.union(list.get(0), list.get(1));
        //寻根：每个下标集合有1个leader，用leader作为key(唯一)，下标集合List作为value
        HashMap<Integer, List<Integer>> map = new HashMap<>();
        //从小到大遍历，使得List<Integer>中的值是有序的(事后不用再排序了)
        for (int i = 0; i < len; ++i) {
            int key = dsu.find(i);
            //这个方法是如果给定key对应的值是null则set默认值
            map.computeIfAbsent(key, unused -> new ArrayList<>()).add(i);
        }
        StringBuilder res = new StringBuilder(s);
        //遍历所有每个下标集合，进行字符局部排序
        for (List<Integer> list : map.values())
            if (list.size() > 1)
                sort(res, list);

        return res.toString();
    }

    //根据下标集合进行局部排序
    private void sort(StringBuilder res, List<Integer> list) {
        int len = list.size();
        char[] array = new char[len];
        //根据下标集合构建字符集合
        for (int i = 0; i < len; ++i)
            array[i] = res.charAt(list.get(i));
        //将字符集合排序
        Arrays.sort(array);
        //将字符按序“插入”回StringBuilder
        for (int i = 0; i < len; ++i)
            res.setCharAt(list.get(i), array[i]);
    }
}

class DSU {
    int[] parent;

    public DSU(int len) {
        parent = new int[len];
        for (int i = 0; i < len; ++i)
            parent[i] = i;
    }

    public int find(int x) {
        return parent[x] != x ? parent[x] = find(parent[x]) : x;
    }

    public void union(int x, int y) {
        parent[find(x)] = find(y);
    }
}

然后这个性能其实也还行，而且我觉得并查集的思路肯定没错，我去看看性能第一的代码：

class Solution {
    public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
        char[] cs = s.toCharArray();
        init(cs.length);//初始化并查集
        for(List<Integer> list:pairs)
            add(is,list.get(0),list.get(1));//设置根节点关联
        over();//结束并查集
        //相同根节点的进行排序，就是字典序最小的字符串
        //字符串已限制只有小写英文字母，可以使用桶排序，统计每个字符数量
        int[][] map = new int[cs.length][26];//统计根节点字符数量
        int[] ts = new int[cs.length];//记录每个根节点最小字符下标
        for(int i=0;i<cs.length;i++)
            map[is[i]][cs[i]-'a']++;//根据根节点，字符统计
        for(int i=0;i<cs.length;i++){
            for(int j=ts[is[i]];j<26;j++){//根据记录的最小下标开始遍历
                if(map[is[i]][j]>0){//如果某字符不为空
                    map[is[i]][j]--;//记录的字符数量减一
                    cs[i] = (char)('a'+j);
                    ts[is[i]] = j;//记录新的最小值记录
                    break;
                }
            }
        }
        return new String(cs);
    }
    int[] is;
    public void init(int len){
        is = new int[len];
        for(int i=0;i<is.length;i++)
            is[i] = i;
    }
    public void add(int[] is,int a,int b){
        is[get(is,a)] = get(is,b);
    }
    public int get(int[] is,int a){
        if(is[a]!=a)
            is[a] = get(is,is[a]);
        return is[a];
    }
    public void over(){
        for(int i=0;i<is.length;i++)
            get(is,i);
    }
}

简单来说并查集的核心思路没变，就是人家的处理可能稍微好点，比如我的实现是自己从头按顺序填充这个圈子的元素，但是人家是直接在遍历中处理了，挺好的实现，但是我自己反正是想不到，这个题就这样吧，下一题。

分隔链表

题目：给定一个头结点为 root 的链表, 编写一个函数以将链表分隔为 k 个连续的部分。每部分的长度应该尽可能的相等: 任意两部分的长度差距不能超过 1，也就是说可能有些部分为 null。这k个部分应该按照在链表中出现的顺序进行输出，并且排在前面的部分的长度应该大于或等于后面的长度。返回一个符合上述规则的链表的列表。举例： 1->2->3->4, k = 5 // 5 结果 [ [1], [2], [3], [4], null ]

示例 1：
输入:
root = [1, 2, 3], k = 5
输出: [[1],[2],[3],[],[]]
解释:
输入输出各部分都应该是链表，而不是数组。
例如, 输入的结点 root 的 val= 1, root.next.val = 2, \root.next.next.val = 3, 且 root.next.next.next = null。
第一个输出 output[0] 是 output[0].val = 1, output[0].next = null。
最后一个元素 output[4] 为 null, 它代表了最后一个部分为空链表。
示例 2：
输入:
root = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 3
输出: [[1, 2, 3, 4], [5, 6, 7], [8, 9, 10]]
解释:
输入被分成了几个连续的部分，并且每部分的长度相差不超过1.前面部分的长度大于等于后面部分的长度。
提示:
root 的长度范围： [0, 1000].
输入的每个节点的大小范围：[0, 999].
k 的取值范围： [1, 50].

思路：简而言之我的想法就是先判断链表的长度，然后除k获取每一节的长度。倍数是最短长度。余数是最短+1的长度数。思路还是很清晰的，我去实现下试试。
思路清晰，没啥问题，我直接贴ac代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode[] splitListToParts(ListNode root, int k) {
        ListNode[] res = new ListNode[k];
        int len = 0;
        ListNode t = root;
        while(t!=null) {
            t = t.next;
            len++;
        }
        int n = len/k;
        int y = len%k;
        for(int i = 0;i<k;i++) {
            ListNode temp = new ListNode(0);
            ListNode cur = temp;
            if(i<y) {
                for(int j = 0;j<=n;j++) {
                    cur.next = root;
                    cur = cur.next;
                    root = root.next;
                }
            }else {
                for(int j = 0;j<n;j++) {
                    cur.next = root;
                    cur = cur.next;
                    root = root.next;
                }
            }
            cur.next = null;
            res[i] = temp.next;
        }
        return res;
    }
}

这个题比较简单，就是一个分割，而且我这个性能也超过百分百了，所以不看题解了，直接过吧。
本篇笔记就记到这里，如果稍微帮到你了记得点个喜欢点个关注，也祝大家工作顺顺利利！