省份數(shù)量

題目：有 n 個城市豁跑，其中一些彼此相連力细，另一些沒有相連系枪。如果城市 a 與城市 b 直接相連雀哨，且城市 b 與城市 c 直接相連，那么城市 a 與城市 c 間接相連私爷。省份 是一組直接或間接相連的城市雾棺，組內(nèi)不含其他沒有相連的城市。給你一個 n x n 的矩陣 isConnected 衬浑，其中 isConnected[i][j] = 1 表示第 i 個城市和第 j 個城市直接相連捌浩，而 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]

題目截圖

思路：這個題是每日一題工秩，我也不知道我做過沒做過了尸饺，反正思路就是朋友圈的思路。是一個圈子的放一起拓诸。不是一起的分開放侵佃。這里用set來實現(xiàn)，所有的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);
            }
        }
    }
}

做完了我才發(fā)現(xiàn)這個題果然ac過迈螟，而且是兩個月前，我說怎么似曾相識的呢尔崔。答毫。。這個就是思路季春，只要思路對就沒啥難度洗搂，下一題了。

最長重復子數(shù)組

題目：給兩個整數(shù)數(shù)組 A 和 B 载弄，返回兩個數(shù)組中公共的耘拇、長度最長的子數(shù)組的長度。

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

思路：又是重復子串問題惫叛。因為這個數(shù)組其實比字符串還好處理。長度都很小逞刷，我覺得暴力法都有可能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;
    }
}

這個代碼就沒啥邏輯了仑最，純暴力一個一個去計數(shù)的扔役。至于性能肯定是好不了，然後說起優(yōu)化警医，之前的子序列問題都可以用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方法因為要連續(xù)葫笼，所以不等以后直接補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;
    }
}

性能第一的代碼路星。據(jù)說是用的二分+hash溯街。反正拆開每個字我都認識，放一起就有點看不懂了洋丐，附上解釋截圖：

二分+hash思路

大概的意思的因為都是正整數(shù)呈昔，所以用某種方式處理子串，相同的數(shù)字會有一樣的一個hash值友绝。我們根據(jù)值一樣不一樣判斷是不是相同的子串堤尾？反正中文看我能看懂，怎么實現(xiàn)的一臉懵B迁客。郭宝。這個我就不難為自己了，下一題了掷漱。

賬戶合并

題目：給定一個列表 accounts粘室，每個元素 accounts[i] 是一個字符串列表，其中第一個元素 accounts[i][0] 是 名稱 (name)卜范，其余元素是 emails 表示該賬戶的郵箱地址∠瓮常現(xiàn)在，我們想合并這些賬戶海雪。如果兩個賬戶都有一些共同的郵箱地址锦爵，則兩個賬戶必定屬于同一個人。請注意喳魏，即使兩個賬戶具有相同的名稱棉浸，它們也可能屬于不同的人，因為人們可能具有相同的名稱刺彩。一個人最初可以擁有任意數(shù)量的賬戶迷郑，但其所有賬戶都具有相同的名稱枝恋。合并賬戶后，按以下格式返回賬戶：每個賬戶的第一個元素是名稱嗡害，其余元素是按順序排列的郵箱地址焚碌。賬戶本身可以以任意順序返回。

示例 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]的范圍內(nèi)。
accounts[i]的長度將在[1痊银，10]的范圍內(nèi)抵蚊。
accounts[i][j]的長度將在[1，30]的范圍內(nèi)曼验。

思路：有時候想想力扣也挺不容易泌射，為了出題提出各種奇葩的情景。鬓照。先說這個題熔酷，我覺得我應該可以理解為名字不同賬號一定不同。名字相同如果有相同的賬號說名是一個人豺裆，可以合并拒秘，否則說明不是一個人思杯，還是不可以合并归露。這種題我第一想法就是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;
    }
}

做起來才發(fā)現(xiàn)這個題好復雜园匹，真的是中等難度么雳刺？按照朋友圈的思路，要深搜才能把一個圈子的放一起裸违，而且還要批量把圈子里的所有人都放一起掖桦。越寫越蒙，從開始到放棄供汛。枪汪。
然后換一種方式深搜，本來我第一版是存下標的怔昨，硬生生改成字面量省的自己暈了雀久。。反正seen用來存處理過了的郵箱名趁舀，每個處理過的都深搜完了岸啡，也就是這個賬戶對應的用戶的所有賬戶都完事了。反正寫的挺繞的赫编，我這個代碼也是參考官方題解寫的，這個題說難也沒那么難奋隶，說簡單各種數(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;
        }
    }
}

感覺是標準并查集唯欣，又是我知識盲區(qū)嘹吨。。境氢。這個題就這樣了蟀拷。

刪除注釋

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

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

字符串// 表示行注釋亭螟，表示//和其右側(cè)的其余字符應該被忽略挡鞍。

字符串/* 表示一個塊注釋，它表示直到/的下一個（非重疊）出現(xiàn)的所有字符都應該被忽略预烙。（閱讀順序為從左到右）非重疊是指墨微，字符串//并沒有結(jié)束塊注釋，因為注釋的結(jié)尾與開頭相重疊扁掸。

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

如果一行在刪除注釋之后變?yōu)榭兆址侗模敲床灰敵鲈撔邢壑妗＜矗鸢噶斜碇械拿總€字符串都是非空的掐隐。

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

我們保證每一個塊注釋最終都會被閉合熟丸， 所以在行或塊注釋之外的/*總是開始新的注釋。

最后伪节，隱式換行符可以通過塊注釋刪除光羞。 有關詳細信息，請參閱下面的示例怀大。

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

示例 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ù)組時就是 ["ab"].
注意:
source的長度范圍為[1, 100].
source[i]的長度范圍為[0, 80].
每個塊注釋都會被閉合。
給定的源碼中不會有單引號蒜焊、雙引號或其他控制字符倒信。

思路：這個題的我目前的思路是把所有的換行符用用一個特殊符號表示，然后所有的代碼都變成一個字符串了泳梆。遇到//就刪除到下一個換行符之前堤结，如果是代碼塊注釋的話遇到后面的那個都刪除。反正思路大概就這樣鸭丛，我去實現(xiàn)試試竞穷。
好了，第一版代碼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代表行內(nèi)注釋中。2代表處于代碼塊注釋中
        for(int i = 0;i<string.length();i++) {
            if(cur == 0) {//當前正常輸出允蚣，如果遇到注釋了修改當前狀態(tài)
                if(string.charAt(i) != '/' || (string.charAt(i+1) != '/' && string.charAt(i+1) != '*')) {//說明不是注釋
                    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) == '\'') {//當前處于行內(nèi)注釋中，遇到下一行自動失效
                sb1.append("'");
                cur = 0;
            }else if(cur == 2) {//說明處在代碼塊注釋中嚷兔，直到遇到結(jié)束注釋才會結(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;
    }
}

因為要自己理思路森渐，所以注釋寫的挺全的了我覺得，反正這個題這個思路肯定是沒問題冒晰，但是性能不太好同衣，我去看看性能排行第一的代碼：

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

額，這個性能第一的代碼的代碼量壶运。耐齐。。反正思路上也是一次遍歷蒋情。只不過人家沒有合成一個字符串遍歷埠况。。事后想想確實這個沒啥必要棵癣。询枚。一開始我也不知道怎么靈機一動的。浙巫。反正這個題比較簡單，就不多說了刷后，下一題的畴。

交換字符串中的元素

題目：給你一個字符串 s，以及該字符串中的一些「索引對」數(shù)組 pairs尝胆，其中 pairs[i] = [a, b] 表示字符串中的兩個索引（編號從 0 開始）丧裁。你可以 任意多次交換 在 pairs 中任意一對索引處的字符。返回在經(jīng)過若干次交換后含衔，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 并查集

這個并查集一般是發(fā)生在兩兩相關，整個圈子亂七八糟一團亂的時候使用的裆操，最簡單的一個例子（我也是看網(wǎng)上的說法）：比如古代江湖怒详，倆人的關系不是朋友就是敵人。而朋友的朋友也是朋友跷车。這兩句話延伸出一大群亂七八糟莫名其妙的聯(lián)系： A,B朋友棘利，A,C朋友，B,D朋友朽缴。這樣一圈看下來A.B,C,D都是朋友善玫。繼續(xù)往下 F,E是朋友。那么A,F是連不到一起去的密强，所以A,F是敵人茅郎。這才幾個人就要一層一層找了，要是幾百上千個或渤。系冗。。朋友的朋友的朋友....從而薪鹦，并查集就起了大用了：
這里有兩個需要做的：一個是尋根（設置一個人作為根）掌敬。一個是并查。
簡單的并查集的概念和場景說完了池磁，下面說實現(xiàn)：
因為如上說的Z,A朋友奔害，A,B朋友，B地熄，C朋友华临，C,D朋友，D,E朋友端考，E,F朋友⊙盘叮現(xiàn)在想知道Z和F是不是朋友一層一層往下找就很麻煩。按照一個常規(guī)思路就要歸圈子了：比如江湖上的門派却特。你是武當派扶供，我是武當派，那我們就是朋友裂明。這個武當派是人為的去歸納的一個門派诚欠。其實換種說法:你是張三豐門人，我也是，那我們就是朋友轰绵。而這個張三豐粉寞，就是我們認為的一個圈子的根。
同理：你是張三豐門人左腔，我是滅絕師太的門人唧垦，咱倆就是敵人，所以這就是兩個圈子液样。
但是會出現(xiàn)一種情況：張三豐因為喜歡郭襄振亮，所以說峨眉派的人我也認這個朋友，于是乎所有的張三豐門人和滅絕師太門人也是朋友了鞭莽。
當然了坊秸，不非要領頭有關系，比如說周芷若和宋青書結(jié)婚了澎怒，所以兩個門派是朋友了褒搔，這個也可以。
不管是張三豐因為暗戀所以合二為一喷面，還是宋青書周芷若結(jié)婚合二為一星瘾，反正這個兩個圈子的人合到一起的行為就是并查。
而根據(jù)某個人去往上一層一層理惧辈，最終找出這個圈子的代表人物的過程就是尋根琳状。
尋根和并查兩中操作把一個集合中的人分成不同的圈子，這個過程就是并查集算法盒齿。
其實這個并查集算法是有一個標準的模板的念逞，下面是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ù)要查詢集合中的大小決定。比如江湖上一共就一百個人边翁，那么這里只要初始化100個容量就可以翎承。一千個人就初始化1000個。倒彰。依此類推。
而這個類的初始化方法就是最初把每一個人都作為一個獨立的圈子來看待莱睁。
而下面的find方法就是尋根待讳，找尋這個圈子中的領頭人。
union方法就是并查仰剿，把無關系的兩個人聯(lián)系到一起创淡。
實現(xiàn)起來其實都挺簡單的，這里除了尋根用到了遞歸剩下的都是只要思路懂了就沒啥難度南吮。
然后并查集就簡單介紹到這里琳彩，下面開始正式說這個題。

這個題只要會了并查集實現(xiàn)起來比較簡單，下面是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();
    }

    //根據(jù)下標集合進行局部排序
    private void sort(StringBuilder res, List<Integer> list) {
        int len = list.size();
        char[] array = new char[len];
        //根據(jù)下標集合構建字符集合
        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));//設置根節(jié)點關聯(lián)
        over();//結(jié)束并查集
        //相同根節(jié)點的進行排序抖仅，就是字典序最小的字符串
        //字符串已限制只有小寫英文字母，可以使用桶排序毙替，統(tǒng)計每個字符數(shù)量
        int[][] map = new int[cs.length][26];//統(tǒng)計根節(jié)點字符數(shù)量
        int[] ts = new int[cs.length];//記錄每個根節(jié)點最小字符下標
        for(int i=0;i<cs.length;i++)
            map[is[i]][cs[i]-'a']++;//根據(jù)根節(jié)點岸售，字符統(tǒng)計
        for(int i=0;i<cs.length;i++){
            for(int j=ts[is[i]];j<26;j++){//根據(jù)記錄的最小下標開始遍歷
                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);
    }
}

簡單來說并查集的核心思路沒變，就是人家的處理可能稍微好點厂画，比如我的實現(xiàn)是自己從頭按順序填充這個圈子的元素凸丸，但是人家是直接在遍歷中處理了，挺好的實現(xiàn)袱院，但是我自己反正是想不到屎慢，這個題就這樣吧，下一題忽洛。

分隔鏈表

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

示例 1：
輸入:
root = [1, 2, 3], k = 5
輸出: [[1],[2],[3],[],[]]
解釋:
輸入輸出各部分都應該是鏈表欣喧，而不是數(shù)組。
例如, 輸入的結(jié)點 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]]
解釋:
輸入被分成了幾個連續(xù)的部分锈锤，并且每部分的長度相差不超過1.前面部分的長度大于等于后面部分的長度驯鳖。
提示:
root 的長度范圍： [0, 1000].
輸入的每個節(jié)點的大小范圍：[0, 999].
k 的取值范圍： [1, 50].

思路：簡而言之我的想法就是先判斷鏈表的長度闲询，然后除k獲取每一節(jié)的長度。倍數(shù)是最短長度浅辙。余數(shù)是最短+1的長度數(shù)扭弧。思路還是很清晰的，我去實現(xià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;
    }
}

這個題比較簡單氨淌，就是一個分割泊愧，而且我這個性能也超過百分百了，所以不看題解了盛正，直接過吧删咱。
本篇筆記就記到這里，如果稍微幫到你了記得點個喜歡點個關注豪筝，也祝大家工作順順利利痰滋！