剑指 Offer II 114+115+116+117+LC827

外星文字典

现有一种使用英语字母的外星文语言，这门语言的字母顺序与英语顺序不同。给定一个字符串列表 words ，作为这门语言的词典，words 中的字符串已经 按这门新语言的字母顺序进行了排序 。
请你根据该词典还原出此语言中已知的字母顺序，并 按字母递增顺序 排列。若不存在合法字母顺序，返回 “” 。若存在多种可能的合法字母顺序，返回其中 任意一种 顺序即可。
字符串 s 字典顺序小于 字符串 t 有两种情况：

• 在第一个不同字母处，如果 s 中的字母在这门外星语言的字母顺序中位于 t 中字母之前，那么 s 的字典顺序小于 t 。
• 如果前面 min(s.length, t.length) 字母都相同，那么 s.length < t.length 时，s 的字典顺序也小于 t 。

分析：

使用拓扑排序。首先建图，建图时遍历字符串组，进行两两比较，认为字典顺序较前的字母存在一条边到字典顺序较小的字母；同时在建图时统计出现过的字母(数量记为cnt)以及每一个字母的入度。完成上述操作之后，从所有入度为 0 的点开始（含义为没有比这些字符字典序更小的字符），跑一遍拓扑排序：在 BFS 过程中，不断的删点（出队的点可以看做从图中移除）和更新删除点的出边点的入度，若有新的入度为 0 的点，则将其进行入队操作。若最终出队节点数量与总数量 cnt 相等，说明这是一张拓扑图（无环，字符之间不存在字典序冲突），出队的顺序即是字典序，否则存在冲突，返回空串。

class Solution {
public static String alienOrder(String[] words) {
        // graph[i][j]：i点（字符i+'a'） 是否存在指向 j点（字符j+'a'）的边，即：字符i+'a'排在字符j+'a'之前
        boolean[][] graph = new boolean[26][26];
        int[] inDegree = new int[26]; // 入度表 inDegree[i]：i点的入度值
        boolean[] exist = new boolean[26]; // exist[i]：在图中是否存在字符i+'a'

        // 将存在的字符加入exist，标记存在这个点：
        for (int i = 0; i < words.length; i++) {
            for (char c : words[i].toCharArray()) exist[c-'a'] = true;
        }

        // 两两遍历比较每个字符串，建图：
        for (int i = 0; i < words.length-1; i++) {
            int j = i+1;
            char[] word1 = words[i].toCharArray();
            char[] word2 = words[j].toCharArray();
            int cur = 0;
            while (cur < word1.length && cur < word2.length && word1[cur] == word2[cur]) cur++;
            if (cur < word1.length && cur == word2.length) return "";
            if (cur < word1.length && cur < word2.length) {
                char from = word1[cur], to = word2[cur];
                inDegree[to-'a'] += graph[from-'a'][to-'a'] ? 0 : 1;
                graph[from-'a'][to-'a'] = true;
            }
        }

        // 拓扑排序，根据图graph、入度表inDegree，生成拓扑排序结果
        return topoSort(graph, inDegree, exist);
    }

    // 拓扑排序
    private static String topoSort(boolean[][] graph, int[] inDegree, boolean[] exist) {
        StringBuilder order = new StringBuilder();
        Queue<Integer> queue = new LinkedList<>();
        int count = 0;
        
        for (int i = 0; i < 26; i++) {
            if (exist[i] && inDegree[i] == 0) queue.add(i);
            if (exist[i]) count++;
        }
       
        while (!queue.isEmpty()) {
            int i = queue.poll();
            order.append((char)(i+'a'));
            for (int j = 0; j < 26; j++) {
                if (graph[i][j]) {
                    graph[i][j] = false;
                    if (--inDegree[j] == 0) queue.add(j);
                }
            }
        }

        // 如果排序的点数等于图中总点数，则存在拓扑序，否则，不存在：
        return order.length() == count ? order.toString() : "";
    }
}
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

重建序列

给定一个长度为 n 的整数数组 nums ，其中 nums 是范围为 [1，n] 的整数的排列。还提供了一个 2D 整数数组 sequences ，其中 sequences[i] 是 nums 的子序列。
检查 nums 是否是唯一的最短 超序列 。最短 超序列 是 长度最短 的序列，并且所有序列 sequences[i] 都是它的子序列。对于给定的数组 sequences ，可能存在多个有效的 超序列 。

• 例如，对于 sequences = [[1,2],[1,3]] ，有两个最短的 超序列 ，[1,2,3] 和 [1,3,2] 。
• 而对于 sequences = [[1,2],[1,3],[1,2,3]] ，唯一可能的最短 超序列 是 [1,2,3] 。[1,2,3,4] 是可能的超序列，但不是最短的。

如果 nums 是序列的唯一最短 超序列 ，则返回 true ，否则返回 false 。子序列 是一个可以通过从另一个序列中删除一些元素或不删除任何元素，而不改变其余元素的顺序的序列。

分析：

由于 sequences 中的每个序列都是nums 的子序列，因此每个序列中的数字顺序都和nums 中的数字顺序一致。为了判断 nums 是不是序列的唯一最短超序列，只需要判断根据 sequences 中的每个序列构造超序列的结果是否唯一。
可以将sequences 中的所有序列看成有向图，数字 1 到 n 分别表示图中的 n 个结点，每个序列中的相邻数字表示的结点之间存在一条有向边。根据给定的序列构造超序列等价于有向图的拓扑排序。首先根据有向边计算每个结点的入度，然后将所有入度为 0 的结点添加到队列中，进行拓扑排序。每一轮拓扑排序时，队列中的元素个数表示可以作为超序列下一个数字的元素个数，根据队列中的元素个数，执行如下操作。

• 如果队列中的元素个数大于 1，则超序列的下一个数字不唯一，因此nums 不是唯一的最短超序列，返回false。
• 如果队列中的元素个数等于 1，则超序列的下一个数字是队列中唯一的数字。将该数字从队列中取出，将该数字指向的每个数字的入度减 1，并将入度变成 0 的数字添加到队列中。

重复上述过程，直到出现队列中的元素个数不等于 1 的情况。如果队列中的元素个数大于 1，则 nums 不是唯一的最短超序列，返回 false。如果队列为空，则完整的拓扑排序结束，nums 是唯一的最短超序列，返回 true。

class Solution {
    public boolean sequenceReconstruction(int[] nums, int[][] sequences) {
        int n = nums.length;
        int[] indegrees = new int[n+1];
        Set<Integer>[] graph = new Set[n + 1];
        for (int i = 1; i <= n; i++) {
            graph[i] = new HashSet<Integer>();
        }
        for (int[] sequence : sequences) {
            int size = sequence.length;
            for (int i = 1; i < size; i++) {
                int prev = sequence[i - 1], next = sequence[i];
                if (graph[prev].add(next)) {
                    indegrees[next]++;
                }
            }
        }
        Queue<Integer> q = new LinkedList<>();
        for (int i = 1; i <= n; i++) {
            if (indegrees[i] == 0) q.offer(i);
        }
        while (!q.isEmpty()){
            if (q.size()>1) return false;
            int u =q.poll();
            Set<Integer> set = graph[u];
            for (int v : set){
                indegrees[v]--;
                if (indegrees[v] == 0) q.offer(v);
            }

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

省份数量

有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。

省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。

给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。返回矩阵中 省份 的数量。

分析

可以把 n 个城市和它们之间的相连关系看成图，城市是图中的节点，相连关系是图中的边，给定的矩阵isConnected 即为图的邻接矩阵，省份即为图中的连通分量。通过dfs来实现求解图中的连通分量。遍历所有城市，对于每个城市，如果该城市尚未被访问过，则从该城市开始深度优先搜索，通过矩阵isConnected 得到与该城市直接相连的城市有哪些，这些城市和该城市属于同一个连通分量，然后对这些城市继续深度优先搜索，直到同一个连通分量的所有城市都被访问到，即可得到一个省份。遍历完全部城市以后，即可得到连通分量的总数，即省份的总数。

class Solution {
    public int findCircleNum(int[][] isConnected) {
        int cities = isConnected.length;
        boolean[] visited = new boolean[cities];
        int provinces = 0;
        for (int i = 0; i < cities; i++) {
            if (!visited[i]) {
                dfs(isConnected, visited, cities, i);
                provinces++;
            }
        }
        return provinces;
    }

    public void dfs(int[][] isConnected, boolean[] visited, int cities, int i) {
        for (int j = 0; j < cities; j++) {
            if (isConnected[i][j] == 1 && !visited[j]) {
                visited[j] = true;
                dfs(isConnected, visited, cities, j);
            }
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

相似的字符串

如果交换字符串 X 中的两个不同位置的字母，使得它和字符串 Y 相等，那么称 X 和 Y 两个字符串相似。如果这两个字符串本身是相等的，那它们也是相似的。

例如，“tars” 和 “rats” 是相似的 (交换 0 与 2 的位置)； “rats” 和 “arts” 也是相似的，但是 “star” 不与 “tars”，“rats”，或 “arts” 相似。

总之，它们通过相似性形成了两个关联组：{“tars”, “rats”, “arts”} 和 {“star”}。注意，“tars” 和 “arts” 是在同一组中，即使它们并不相似。形式上，对每个组而言，要确定一个单词在组中，只需要这个词和该组中至少一个单词相似。

给定一个字符串列表 strs。列表中的每个字符串都是 strs 中其它所有字符串的一个 字母异位词 。请问 strs 中有多少个相似字符串组？

分析：

把每一个字符串看作点，字符串之间是否相似看作边，那么可以发现本题询问的是给定的图中有多少连通分量。于是可以想到使用并查集维护节点间的连通性。枚举给定序列中的任意一对字符串，检查其是否具有相似性，如果相似，那么就将这对字符串相连。

class Solution {
    int[] f;

    public int numSimilarGroups(String[] strs) {
        int n = strs.length;
        int m = strs[0].length();
        f = new int[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 fi = find(i), fj = find(j);
                if (fi == fj) {
                    continue;
                }
                if (check(strs[i], strs[j], m)) {
                    f[fi] = fj;
                }
            }
        }
        int ret = 0;
        for (int i = 0; i < n; i++) {
            if (f[i] == i) {
                ret++;
            }
        }
        return ret;
    }

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

    public boolean check(String a, String b, int len) {
        int num = 0;
        for (int i = 0; i < len; i++) {
            if (a.charAt(i) != b.charAt(i)) {
                num++;
                if (num > 2) {
                    return false;
                }
            }
        }
        return true;
    }
}
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
37
38
39
40
41
42
43
44
45
46
47

最大人工岛

给你一个大小为 n x n 二进制矩阵 grid 。最多 只能将一格 0 变成 1 。返回执行此操作后，grid 中最大的岛屿面积是多少？

分析：

并查集+枚举。具体的先使用并查集维护所有 g[i][j] = 1的块连通性，并在维护连通性的过程中，使用 sz[idx] 记录下每个连通块的大小（注意：只有连通块根编号，sz[idx] 才有意义，即只有 sz[find(x)] 才有意义）。随后再次遍历 grid，根据原始的 g[i][j]的值进行分别处理：

• 若 g[i][j] = 1，该位置不会作为翻转点，但真实最大面积未必是由翻转后所导致的（可能取自原有的连通块），因此需要将 sz[root] 参与比较，其中 root 为(i,j) 所属的连通块根节点编号；
• 若 g[i][j] = 0，该位置可作为翻转点，统计其四联通位置对应的连通块大小总和 tot（注意若四联通方向有相同连通块，只统计一次），那么 tot + 1即是翻转该位置所得到的新连通块大小。

最后对所有连通块大小取最大值即是答案。

class Solution {
    static int N = 510;
    static int[] p = new int[N * N], sz = new int[N * N];
    int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
    int find(int x) {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }
    void union(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return ;
        if (sz[ra] > sz[rb]) {
            union(b, a);
        } else {
            sz[rb] += sz[ra]; p[ra] = p[rb];
        }
    }
    public int largestIsland(int[][] g) {
        int n = g.length;
        for (int i = 1; i <= n * n; i++) {
            p[i] = i; sz[i] = 1;
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (g[i][j] == 0) continue;
                for (int[] di : dirs) {
                    int x = i + di[0], y = j + di[1];
                    if (x < 0 || x >= n || y < 0 || y >= n || g[x][y] == 0) continue;
                    union(i * n + j + 1, x * n + y + 1);
                }
            }
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (g[i][j] == 1) {
                    ans = Math.max(ans, sz[find(i * n + j + 1)]);
                } else {
                    int tot = 1;
                    Set<Integer> set = new HashSet<>();
                    for (int[] di : dirs) {
                        int x = i + di[0],y = j + di[1];
                        if (x < 0 || x >= n || y < 0 || y >= n || g[x][y] == 0) continue;
                        int root = find(x * n + y + 1);
                        if (set.contains(root)) continue;
                        tot += sz[root];
                        set.add(root);
                    }
                    ans = Math.max(ans, tot);
                }
            }
        }
        return ans;
    }
}
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55