省份數(shù)量

題目：有 n 個(gè)城市，其中一些彼此相連，另一些沒(méi)有相連。如果城市 a 與城市 b 直接相連，且城市 b 與城市 c 直接相連，那么城市 a 與城市 c 間接相連。省份 是一組直接或間接相連的城市，組內(nèi)不含其他沒(méi)有相連的城市。給你一個(gè) n x n 的矩陣 isConnected ，其中 isConnected[i][j] = 1 表示第 i 個(gè)城市和第 j 個(gè)城市直接相連，而 isConnected[i][j] = 0 表示二者不直接相連。

返回矩陣中 省份 的數(shù)量

提示：
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]

題目截圖

思路：這個(gè)題是每日一題，我也不知道我做過(guò)沒(méi)做過(guò)了，反正思路就是朋友圈的思路。是一個(gè)圈子的放一起。不是一起的分開(kāi)放。這里用set來(lái)實(shí)現(xiàn)，所有的set里都沒(méi)有那么就單獨(dú)開(kāi)圈子。我去代碼試試。

class Solution {
    public int findCircleNum(int[][] M) { 
        int n = 0;
        for(int i = 0;i<M.length;i++) {
            if(M[i][i] == 1) {//說(shuō)明這個(gè)人沒(méi)被納入圈子，可以單獨(dú)開(kāi)圈
                n++;
                M[i][i] = -1;
                //把和這個(gè)能一個(gè)圈的都納入
                dfs(M, i);
            }
        }       
        return n;
    }
    public void dfs(int[][] M,int i) {      
        //如果跟這個(gè)有關(guān)系說(shuō)明是一個(gè)圈子
        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 說(shuō)明i和k有關(guān)系，k進(jìn)入i的圈子.同時(shí)k圈子里的也都進(jìn)入
                dfs(M, k);
            }
        }
    }
}

做完了我才發(fā)現(xiàn)這個(gè)題果然ac過(guò)，而且是兩個(gè)月前，我說(shuō)怎么似曾相識(shí)的呢。。。這個(gè)就是思路，只要思路對(duì)就沒(méi)啥難度，下一題了。

最長(zhǎng)重復(fù)子數(shù)組

題目：給兩個(gè)整數(shù)數(shù)組 A 和 B ，返回兩個(gè)數(shù)組中公共的、長(zhǎng)度最長(zhǎng)的子數(shù)組的長(zhǎng)度。

示例：
輸入：
A: [1,2,3,2,1]
B: [3,2,1,4,7]
輸出：3
解釋：
長(zhǎng)度最長(zhǎng)的公共子數(shù)組是 [3, 2, 1] 。
提示：
1 <= len(A), len(B) <= 1000
0 <= A[i], B[i] < 100

思路：又是重復(fù)子串問(wèn)題。因?yàn)檫@個(gè)數(shù)組其實(shí)比字符串還好處理。長(zhǎng)度都很小，我覺(jué)得暴力法都有可能ac，我先去嘗試寫下代碼。
暴力法果然過(guò)了，先貼代碼:

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;
    }
}

這個(gè)代碼就沒(méi)啥邏輯了，純暴力一個(gè)一個(gè)去計(jì)數(shù)的。至于性能肯定是好不了，然後說(shuō)起優(yōu)化，之前的子序列問(wèn)題都可以用dp，這種子串應(yīng)該也可以，我去用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;
    }
}

性能還是沒(méi)上來(lái)，但是我覺(jué)得解法應(yīng)該沒(méi)啥問(wèn)題，dp方法因?yàn)橐B續(xù)，所以不等以后直接補(bǔ)0而不是前面最大值。反正這個(gè)題就這樣了，我去看看題解吧：

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;
    }
}

性能第一的代碼。據(jù)說(shuō)是用的二分+hash。反正拆開(kāi)每個(gè)字我都認(rèn)識(shí)，放一起就有點(diǎn)看不懂了，附上解釋截圖：

二分+hash思路

大概的意思的因?yàn)槎际钦麛?shù)，所以用某種方式處理子串，相同的數(shù)字會(huì)有一樣的一個(gè)hash值。我們根據(jù)值一樣不一樣判斷是不是相同的子串？反正中文看我能看懂，怎么實(shí)現(xiàn)的一臉懵B。。這個(gè)我就不難為自己了，下一題了。

賬戶合并

題目：給定一個(gè)列表 accounts，每個(gè)元素 accounts[i] 是一個(gè)字符串列表，其中第一個(gè)元素 accounts[i][0] 是 名稱 (name)，其余元素是 emails 表示該賬戶的郵箱地址?，F(xiàn)在，我們想合并這些賬戶。如果兩個(gè)賬戶都有一些共同的郵箱地址，則兩個(gè)賬戶必定屬于同一個(gè)人。請(qǐng)注意，即使兩個(gè)賬戶具有相同的名稱，它們也可能屬于不同的人，因?yàn)槿藗兛赡芫哂邢嗤拿Q。一個(gè)人最初可以擁有任意數(shù)量的賬戶，但其所有賬戶都具有相同的名稱。合并賬戶后，按以下格式返回賬戶：每個(gè)賬戶的第一個(gè)元素是名稱，其余元素是按順序排列的郵箱地址。賬戶本身可以以任意順序返回。

示例 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"]]
解釋：
第一個(gè)和第三個(gè) John 是同一個(gè)人，因?yàn)樗麄冇泄餐泥]箱地址 "johnsmith@mail.com"。
第二個(gè) John 和 Mary 是不同的人，因?yàn)樗麄兊泥]箱地址沒(méi)有被其他帳戶使用。
可以以任何順序返回這些列表，例如答案 [['Mary'，'mary@mail.com']，['John'，'johnnybravo@mail.com']，
['John'，'john00@mail.com'，'john_newyork@mail.com'，'johnsmith@mail.com']] 也是正確的。
提示：
accounts的長(zhǎng)度將在[1，1000]的范圍內(nèi)。
accounts[i]的長(zhǎng)度將在[1，10]的范圍內(nèi)。
accounts[i][j]的長(zhǎng)度將在[1，30]的范圍內(nèi)。

思路：有時(shí)候想想力扣也挺不容易，為了出題提出各種奇葩的情景。。先說(shuō)這個(gè)題，我覺(jué)得我應(yīng)該可以理解為名字不同賬號(hào)一定不同。名字相同如果有相同的賬號(hào)說(shuō)名是一個(gè)人，可以合并，否則說(shuō)明不是一個(gè)人，還是不可以合并。這種題我第一想法就是map。但是因?yàn)椴煌~戶也可能有相同的名稱。。。是不是又是一個(gè)朋友圈的題?反正我目前的想法是暴力法，挨個(gè)去判斷唄。我去試著寫代碼了。
直接貼代碼：

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;
    }
}

做起來(lái)才發(fā)現(xiàn)這個(gè)題好復(fù)雜，真的是中等難度么？按照朋友圈的思路，要深搜才能把一個(gè)圈子的放一起，而且還要批量把圈子里的所有人都放一起。越寫越蒙，從開(kāi)始到放棄。。
然后換一種方式深搜，本來(lái)我第一版是存下標(biāo)的，硬生生改成字面量省的自己暈了。。反正seen用來(lái)存處理過(guò)了的郵箱名，每個(gè)處理過(guò)的都深搜完了，也就是這個(gè)賬戶對(duì)應(yīng)的用戶的所有賬戶都完事了。反正寫的挺繞的，我這個(gè)代碼也是參考官方題解寫的，這個(gè)題說(shuō)難也沒(méi)那么難，說(shuō)簡(jiǎn)單各種數(shù)據(jù)處理真的是繁瑣的不行，反正就這樣吧， 我去看看性能第一的代碼：

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;
        }
    }
}

感覺(jué)是標(biāo)準(zhǔn)并查集，又是我知識(shí)盲區(qū)。。。這個(gè)題就這樣了。

刪除注釋

題目：給一個(gè) C++ 程序，刪除程序中的注釋。這個(gè)程序source是一個(gè)數(shù)組，其中source[i]表示第i行源碼。 這表示每行源碼由\n分隔。

在 C++ 中有兩種注釋風(fēng)格，行內(nèi)注釋和塊注釋。

字符串// 表示行注釋，表示//和其右側(cè)的其余字符應(yīng)該被忽略。

字符串/* 表示一個(gè)塊注釋，它表示直到/的下一個(gè)（非重疊）出現(xiàn)的所有字符都應(yīng)該被忽略。（閱讀順序?yàn)閺淖蟮接遥┓侵丿B是指，字符串//并沒(méi)有結(jié)束塊注釋，因?yàn)樽⑨尩慕Y(jié)尾與開(kāi)頭相重疊。

第一個(gè)有效注釋優(yōu)先于其他注釋：如果字符串//出現(xiàn)在塊注釋中會(huì)被忽略。 同樣，如果字符串/*出現(xiàn)在行或塊注釋中也會(huì)被忽略。

如果一行在刪除注釋之后變?yōu)榭兆址?，那么不要輸出該行。即，答案列表中的每個(gè)字符串都是非空的。

樣例中沒(méi)有控制字符，單引號(hào)或雙引號(hào)字符。比如，source = "string s = "/* Not a comment. */";" 不會(huì)出現(xiàn)在測(cè)試樣例里。（此外，沒(méi)有其他內(nèi)容（如定義或宏）會(huì)干擾注釋。）

我們保證每一個(gè)塊注釋最終都會(huì)被閉合， 所以在行或塊注釋之外的/*總是開(kāi)始新的注釋。

最后，隱式換行符可以通過(guò)塊注釋刪除。 有關(guān)詳細(xì)信息，請(qǐng)參閱下面的示例。

從源代碼中刪除注釋后，需要以相同的格式返回源代碼。

示例 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" 用換行符分隔成數(shù)組時(shí)就是 ["ab"].
注意:
source的長(zhǎng)度范圍為[1, 100].
source[i]的長(zhǎng)度范圍為[0, 80].
每個(gè)塊注釋都會(huì)被閉合。
給定的源碼中不會(huì)有單引號(hào)、雙引號(hào)或其他控制字符。

思路：這個(gè)題的我目前的思路是把所有的換行符用用一個(gè)特殊符號(hào)表示，然后所有的代碼都變成一個(gè)字符串了。遇到//就刪除到下一個(gè)換行符之前，如果是代碼塊注釋的話遇到后面的那個(gè)都刪除。反正思路大概就這樣，我去實(shí)現(xiàn)試試。
好了，第一版代碼ac了，面向測(cè)試案例變成，不斷通過(guò)錯(cuò)誤原因修改代碼。。我先貼出來(lái)：

class Solution {
    public List<String> removeComments(String[] source) {
        StringBuffer sb = new StringBuffer();
        //因?yàn)轭}目說(shuō)不會(huì)有單引號(hào)，所以這里用單引號(hào)代表?yè)Q行
        for(String s:source) sb.append("'"+s);
        String string = sb.substring(1).toString();
        StringBuffer sb1 = new StringBuffer();
        int cur = 0;//0代表可以正常輸出，1代表行內(nèi)注釋中。2代表處于代碼塊注釋中
        for(int i = 0;i<string.length();i++) {
            if(cur == 0) {//當(dāng)前正常輸出，如果遇到注釋了修改當(dāng)前狀態(tài)
                if(string.charAt(i) != '/' || (string.charAt(i+1) != '/' && string.charAt(i+1) != '*')) {//說(shuō)明不是注釋
                    sb1.append(string.charAt(i));
                }else {//是注釋的話判斷是行內(nèi)還是注釋塊,行內(nèi)狀態(tài)變1，注釋塊狀態(tài)變2
                    i++;
                    cur=string.charAt(i) == '/'?1:2;
                }
            }else if(cur == 1 && string.charAt(i) == '\'') {//當(dāng)前處于行內(nèi)注釋中，遇到下一行自動(dòng)失效
                sb1.append("'");
                cur = 0;
            }else if(cur == 2) {//說(shuō)明處在代碼塊注釋中，直到遇到結(jié)束注釋才會(huì)結(jié)束
                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;
    }
}

因?yàn)橐约豪硭悸?，所以注釋寫的挺全的了我覺(jué)得，反正這個(gè)題這個(gè)思路肯定是沒(méi)問(wèn)題，但是性能不太好，我去看看性能排行第一的代碼：

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("http://", 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;
    }
}

額，這個(gè)性能第一的代碼的代碼量。。。反正思路上也是一次遍歷。只不過(guò)人家沒(méi)有合成一個(gè)字符串遍歷。。事后想想確實(shí)這個(gè)沒(méi)啥必要。。一開(kāi)始我也不知道怎么靈機(jī)一動(dòng)的。。反正這個(gè)題比較簡(jiǎn)單，就不多說(shuō)了，下一題。

交換字符串中的元素

題目：給你一個(gè)字符串 s，以及該字符串中的一些「索引對(duì)」數(shù)組 pairs，其中 pairs[i] = [a, b] 表示字符串中的兩個(gè)索引（編號(hào)從 0 開(kāi)始）。你可以 任意多次交換 在 pairs 中任意一對(duì)索引處的字符。返回在經(jīng)過(guò)若干次交換后，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 中只含有小寫英文字母

思路：這個(gè)題是今天的每日一題，感覺(jué)這個(gè)月簡(jiǎn)直就是并查集+圖論的月份。。簡(jiǎn)單說(shuō)下這個(gè)題：這里有個(gè)概念：每?jī)蓚€(gè)可以互換的詞都可以隨意變化順序。同理 如果 0-1，0-2的話，那么就是這三個(gè)可以隨意變換順序。所以只要知道每一個(gè)可以隨意變化的圈子，讓其從小到大排序就ok了。而這個(gè)圈子的獲取就離不開(kāi)并查集了。
因?yàn)椴⒉榧乙彩窃谒㈩}的過(guò)程中野蠻生長(zhǎng)，隨緣寫法，所以正好今天又又又又刷到這種題目了，所以我打算簡(jiǎn)單的說(shuō)一下這個(gè)并查集：

java 并查集

這個(gè)并查集一般是發(fā)生在兩兩相關(guān)，整個(gè)圈子亂七八糟一團(tuán)亂的時(shí)候使用的，最簡(jiǎn)單的一個(gè)例子（我也是看網(wǎng)上的說(shuō)法）：比如古代江湖，倆人的關(guān)系不是朋友就是敵人。而朋友的朋友也是朋友。這兩句話延伸出一大群亂七八糟莫名其妙的聯(lián)系： A,B朋友，A,C朋友，B,D朋友。這樣一圈看下來(lái)A.B,C,D都是朋友。繼續(xù)往下 F,E是朋友。那么A,F是連不到一起去的，所以A,F是敵人。這才幾個(gè)人就要一層一層找了，要是幾百上千個(gè)。。。朋友的朋友的朋友....從而，并查集就起了大用了：
這里有兩個(gè)需要做的：一個(gè)是尋根（設(shè)置一個(gè)人作為根）。一個(gè)是并查。
簡(jiǎn)單的并查集的概念和場(chǎng)景說(shuō)完了，下面說(shuō)實(shí)現(xiàn)：
因?yàn)槿缟险f(shuō)的Z,A朋友，A,B朋友，B，C朋友，C,D朋友，D,E朋友，E,F朋友?，F(xiàn)在想知道Z和F是不是朋友一層一層往下找就很麻煩。按照一個(gè)常規(guī)思路就要?dú)w圈子了：比如江湖上的門派。你是武當(dāng)派，我是武當(dāng)派，那我們就是朋友。這個(gè)武當(dāng)派是人為的去歸納的一個(gè)門派。其實(shí)換種說(shuō)法:你是張三豐門人，我也是，那我們就是朋友。而這個(gè)張三豐，就是我們認(rèn)為的一個(gè)圈子的根。
同理：你是張三豐門人，我是滅絕師太的門人，咱倆就是敵人，所以這就是兩個(gè)圈子。
但是會(huì)出現(xiàn)一種情況：張三豐因?yàn)橄矚g郭襄，所以說(shuō)峨眉派的人我也認(rèn)這個(gè)朋友，于是乎所有的張三豐門人和滅絕師太門人也是朋友了。
當(dāng)然了，不非要領(lǐng)頭有關(guān)系，比如說(shuō)周芷若和宋青書(shū)結(jié)婚了，所以兩個(gè)門派是朋友了，這個(gè)也可以。
不管是張三豐因?yàn)榘祽偎院隙橐?，還是宋青書(shū)周芷若結(jié)婚合二為一，反正這個(gè)兩個(gè)圈子的人合到一起的行為就是并查。
而根據(jù)某個(gè)人去往上一層一層理，最終找出這個(gè)圈子的代表人物的過(guò)程就是尋根。
尋根和并查兩中操作把一個(gè)集合中的人分成不同的圈子，這個(gè)過(guò)程就是并查集算法。
其實(shí)這個(gè)并查集算法是有一個(gè)標(biāo)準(zhǔn)的模板的，下面是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的初始大小要根據(jù)要查詢集合中的大小決定。比如江湖上一共就一百個(gè)人，那么這里只要初始化100個(gè)容量就可以。一千個(gè)人就初始化1000個(gè)。。依此類推。
而這個(gè)類的初始化方法就是最初把每一個(gè)人都作為一個(gè)獨(dú)立的圈子來(lái)看待。
而下面的find方法就是尋根，找尋這個(gè)圈子中的領(lǐng)頭人。
union方法就是并查，把無(wú)關(guān)系的兩個(gè)人聯(lián)系到一起。
實(shí)現(xiàn)起來(lái)其實(shí)都挺簡(jiǎn)單的，這里除了尋根用到了遞歸剩下的都是只要思路懂了就沒(méi)啥難度。
然后并查集就簡(jiǎn)單介紹到這里，下面開(kāi)始正式說(shuō)這個(gè)題。

這個(gè)題只要會(huì)了并查集實(shí)現(xiàn)起來(lái)比較簡(jiǎn)單，下面是ac代碼：

class Solution {    
    public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
        //這里有個(gè)概念：每?jī)蓚€(gè)可以互換的詞都可以隨意變化順序。同理 如果 0-1，0-2的話，那么就是這三個(gè)可以隨意變換順序
        //所以只要知道每一個(gè)可以隨意變化的圈子，讓其從小到大排序就ok了
        //而這個(gè)隨意變化的圈子的獲取，就是并查集了。
        int len = s.length();
        //這個(gè)題最大值是10的5次方。所以這里并查集初始大小100000
        DSU dsu = new DSU(100000);
        //并查
        for (List<Integer> list : pairs)
            dsu.union(list.get(0), list.get(1));
        //尋根：每個(gè)下標(biāo)集合有1個(gè)leader，用leader作為key(唯一)，下標(biāo)集合List作為value
        HashMap<Integer, List<Integer>> map = new HashMap<>();
        //從小到大遍歷，使得List<Integer>中的值是有序的(事后不用再排序了)
        for (int i = 0; i < len; ++i) {
            int key = dsu.find(i);
            //這個(gè)方法是如果給定key對(duì)應(yīng)的值是null則set默認(rèn)值
            map.computeIfAbsent(key, unused -> new ArrayList<>()).add(i);
        }
        StringBuilder res = new StringBuilder(s);
        //遍歷所有每個(gè)下標(biāo)集合，進(jìn)行字符局部排序
        for (List<Integer> list : map.values())
            if (list.size() > 1)
                sort(res, list);

        return res.toString();
    }

    //根據(jù)下標(biāo)集合進(jìn)行局部排序
    private void sort(StringBuilder res, List<Integer> list) {
        int len = list.size();
        char[] array = new char[len];
        //根據(jù)下標(biāo)集合構(gòu)建字符集合
        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);
    }
}

然后這個(gè)性能其實(shí)也還行，而且我覺(jué)得并查集的思路肯定沒(méi)錯(cuò)，我去看看性能第一的代碼：

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));//設(shè)置根節(jié)點(diǎn)關(guān)聯(lián)
        over();//結(jié)束并查集
        //相同根節(jié)點(diǎn)的進(jìn)行排序，就是字典序最小的字符串
        //字符串已限制只有小寫英文字母，可以使用桶排序，統(tǒng)計(jì)每個(gè)字符數(shù)量
        int[][] map = new int[cs.length][26];//統(tǒng)計(jì)根節(jié)點(diǎn)字符數(shù)量
        int[] ts = new int[cs.length];//記錄每個(gè)根節(jié)點(diǎn)最小字符下標(biāo)
        for(int i=0;i<cs.length;i++)
            map[is[i]][cs[i]-'a']++;//根據(jù)根節(jié)點(diǎn)，字符統(tǒng)計(jì)
        for(int i=0;i<cs.length;i++){
            for(int j=ts[is[i]];j<26;j++){//根據(jù)記錄的最小下標(biāo)開(kāi)始遍歷
                if(map[is[i]][j]>0){//如果某字符不為空
                    map[is[i]][j]--;//記錄的字符數(shù)量減一
                    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);
    }
}

簡(jiǎn)單來(lái)說(shuō)并查集的核心思路沒(méi)變，就是人家的處理可能稍微好點(diǎn)，比如我的實(shí)現(xiàn)是自己從頭按順序填充這個(gè)圈子的元素，但是人家是直接在遍歷中處理了，挺好的實(shí)現(xiàn)，但是我自己反正是想不到，這個(gè)題就這樣吧，下一題。

分隔鏈表

題目：給定一個(gè)頭結(jié)點(diǎn)為 root 的鏈表, 編寫一個(gè)函數(shù)以將鏈表分隔為 k 個(gè)連續(xù)的部分。每部分的長(zhǎng)度應(yīng)該盡可能的相等: 任意兩部分的長(zhǎng)度差距不能超過(guò) 1，也就是說(shuō)可能有些部分為 null。這k個(gè)部分應(yīng)該按照在鏈表中出現(xiàn)的順序進(jìn)行輸出，并且排在前面的部分的長(zhǎng)度應(yīng)該大于或等于后面的長(zhǎng)度。返回一個(gè)符合上述規(guī)則的鏈表的列表。舉例： 1->2->3->4, k = 5 // 5 結(jié)果 [ [1], [2], [3], [4], null ]

示例 1：
輸入:
root = [1, 2, 3], k = 5
輸出: [[1],[2],[3],[],[]]
解釋:
輸入輸出各部分都應(yīng)該是鏈表，而不是數(shù)組。
例如, 輸入的結(jié)點(diǎn) root 的 val= 1, root.next.val = 2, \root.next.next.val = 3, 且 root.next.next.next = null。
第一個(gè)輸出 output[0] 是 output[0].val = 1, output[0].next = null。
最后一個(gè)元素 output[4] 為 null, 它代表了最后一個(gè)部分為空鏈表。
示例 2：
輸入:
root = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 3
輸出: [[1, 2, 3, 4], [5, 6, 7], [8, 9, 10]]
解釋:
輸入被分成了幾個(gè)連續(xù)的部分，并且每部分的長(zhǎng)度相差不超過(guò)1.前面部分的長(zhǎng)度大于等于后面部分的長(zhǎng)度。
提示:
root 的長(zhǎng)度范圍： [0, 1000].
輸入的每個(gè)節(jié)點(diǎn)的大小范圍：[0, 999].
k 的取值范圍： [1, 50].

思路：簡(jiǎn)而言之我的想法就是先判斷鏈表的長(zhǎng)度，然后除k獲取每一節(jié)的長(zhǎng)度。倍數(shù)是最短長(zhǎng)度。余數(shù)是最短+1的長(zhǎng)度數(shù)。思路還是很清晰的，我去實(shí)現(xiàn)下試試。
思路清晰，沒(méi)啥問(wèn)題，我直接貼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;
    }
}

這個(gè)題比較簡(jiǎn)單，就是一個(gè)分割，而且我這個(gè)性能也超過(guò)百分百了，所以不看題解了，直接過(guò)吧。
本篇筆記就記到這里，如果稍微幫到你了記得點(diǎn)個(gè)喜歡點(diǎn)個(gè)關(guān)注，也祝大家工作順順利利！