剑指offer专项突击版第40天

剑指 Offer II 117. 相似的字符串

• 题意就是根据字符串的相似性将 $strs$ 里的所有字符串进行分组，求出组数。
• 其中所有字符串都是彼此的字母异位词也就是每种不同的字母数量均相等，所以只会出现三种情况：两个字符串相同位置上1、所有字母完全相等。2、2个字母不相等。3、超过2个不相等。容易发现前两种情况为字符串相似，最后则为不相似。

并查集

轮询所有字符串两两之间的关系，将所有两字符串的父亲不一样且字符串相似的关系连一条边，最后求连通分量即可（连通块）。

class Solution {
public:
    vector<int> f;
    int getf(int v) {
        if(v == f[v]) return v;
        else return f[v] = getf(f[v]);
    }

    bool check(string &a, string &b) {
        int cnt = 0;
        for(int i = 0; i < a.size(); i++)
            if(a[i] != b[i]) {
                cnt++;
                if(cnt > 2) return false;
            }
        return true;    
    }

    int numSimilarGroups(vector<string>& strs) {
        int n = strs.size(), m = strs[0].size();
        f.resize(n);
        for(int i = 0; i < n; i++) f[i] = i;
        for(int i = 0; i < n; i++)
            for(int j = i+1; j < n; j++) {
                int fa = getf(i), fb = getf(j);
                if(fa != fb && check(strs[i],strs[j])) {
                    f[fb] = fa;
                } 
            }
        int res = 0;
        for(int i = 0; i < n; i++) if(f[i] == i) res++;    
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

---

剑指 Offer II 118. 多余的边

并查集

若当前边两结点父亲不一样则说明两结点所在的连通分量并没有连通，所以就需要当前边对两连通分量进行连通，反之两结点父亲一样就说明两结点已经连通，故无需再次连边可去掉当前边。

class Solution {
public:
    vector<int> f;
    int getf(int v) {
        if(v == f[v]) return v;
        else return f[v] = getf(f[v]);
    }
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        int n = edges.size();
        vector<int> res;
        f.resize(n+1);
        for(int i = 0; i <= n; i++) f[i] = i;
        for(int i = 0; i < n; i++) {
            int fa = getf(edges[i][0]), fb = getf(edges[i][1]);
            if(fa != fb) {
                f[fb] = fa;
            } else {
                res.emplace_back(edges[i][0]);
                res.emplace_back(edges[i][1]);
            }
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

---

剑指 Offer II 119. 最长连续序列

方法一、排序去重

将数组排序去重后（也可以直接使用set），直接计数即可，时间复杂度 $O(NlogN)$ 。

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        if(nums.size() == 0) return 0;
        sort(nums.begin(),nums.end());
        nums.erase(unique(nums.begin(),nums.end()),nums.end());
        int res = 1, cnt = 1;
        for(int i = 1; i < nums.size(); i++) {
            if(nums[i] == nums[i-1]+1) {
                cnt++; 
                res = max(res,cnt);
            } else cnt = 1;
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

方法二、并查集

• 理论时间复杂度 $O(NlogN)$ ，实际时间是方法一的5倍多，空间2倍多。
• 思路：将所有相邻的数都放在同一连通分量上，并记录其连通分量大小（直接使用哈希查找相邻数），最后获得最大的连通分量即为答案。

class Solution {
public:
    unordered_map<int,int> f, cnt;
    int getf(int v) {
        if(f[v] == v) return v;
        else return f[v] = getf(f[v]);
    }

    void merge(int a,int b) {
        int fa = getf(a), fb = getf(b);
        if(fa != fb) {
            f[fb] = fa;
            cnt[fa] += cnt[fb];
        }
    }

    int longestConsecutive(vector<int>& nums) {
        for(const int &num: nums) {
            f[num] = num;
            cnt[num] = 1;
        }

        for(const int &num: nums) {
            if(f.count(num+1)) merge(num,num+1);
            if(f.count(num-1)) merge(num,num-1);
        }

        int res = 0;
        for(const int &num: nums) {
            if(f[num] == num) {
                res = max(res,cnt[num]);
            }
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

方法三、思维
时间复杂度 $O(N)$

1. 仔细思考发现，所有连续的序列必定有个左边界（最小的数）和 右边界（最大的数），在不同连续序列的边界之间肯定都不连续。
2. 将所有数加入哈希表后，在轮询哈希表时若哈希表中不存在当前数的前一个数就说明当前数是一个连续序列的左边界。
3. 这时我们就可以只轮询左边界，若当前数为连续序列左边界，那么需要遍历到它的右边界，这样就可获得一个连续序列的长度，以此类推即可获得所有连续序列的长度，最后取最大值即为答案。

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> all;
        for (const int &num : nums) {
            all.insert(num);
        }
        int res = 0;
        for (const int &num : all) {
            if (!all.count(num - 1)) {
                int cur_num = num;
                int cnt = 1;
                while (all.count(cur_num + 1)) {
                    cur_num += 1;
                    cnt += 1;
                }
                res = max(res, cnt);
            }
        }
        return res;           
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

---

小样，这还不拿下你？hhh