标签： 并查集

目标

给你一个 m x n 的网格 grid。网格里的每个单元都代表一条街道。grid[i][j] 的街道可以是：

• 1 表示连接左单元格和右单元格的街道。
• 2 表示连接上单元格和下单元格的街道。
• 3 表示连接左单元格和下单元格的街道。
• 4 表示连接右单元格和下单元格的街道。
• 5 表示连接左单元格和上单元格的街道。
• 6 表示连接右单元格和上单元格的街道。

你最开始从左上角的单元格 (0,0) 开始出发，网格中的「有效路径」是指从左上方的单元格 (0,0) 开始、一直到右下方的 (m-1,n-1) 结束的路径。该路径必须只沿着街道走。

注意：你 不能 变更街道。

如果网格中存在有效的路径，则返回 true，否则返回 false 。

示例 1：

输入：grid = [[2,4,3],[6,5,2]]
输出：true
解释：如图所示，你可以从 (0, 0) 开始，访问网格中的所有单元格并到达 (m - 1, n - 1) 。

示例 2：

输入：grid = [[1,2,1],[1,2,1]]
输出：false
解释：如图所示，单元格 (0, 0) 上的街道没有与任何其他单元格上的街道相连，你只会停在 (0, 0) 处。

示例 3：

输入：grid = [[1,1,2]]
输出：false
解释：你会停在 (0, 1)，而且无法到达 (0, 2) 。

示例 4：

输入：grid = [[1,1,1,1,1,1,3]]
输出：true

示例 5：

输入：grid = [[2],[2],[2],[2],[2],[2],[6]]
输出：true

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 300
• 1 <= grid[i][j] <= 6

思路

有一个二维矩阵 grid，每个单元格的值都代表一种街道类型，判断能否从左上角出发沿着街道走到右下角。

根据当前的街道类型，初始化可走的方向，同时判断下一个位置是否超出了边界，是否访问过，是否与当前街道连通。

代码

/**
 * @date 2026-04-27 9:08
 */
public class HasValidPath1391 {

    public boolean hasValidPath(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        boolean[][] visited = new boolean[m][n];
        return dfs(0, 0, new int[]{1, 2, 3, 4, 5, 6}, visited, grid);
    }

    public static int[][][] directions = new int[][][]{
            {{0, 0}, {0, 0}},
            {{0, -1}, {0, 1}},
            {{-1, 0}, {1, 0}},
            {{0, -1}, {1, 0}},
            {{0, 1}, {1, 0}},
            {{0, -1}, {-1, 0}},
            {{0, 1}, {-1, 0}},
    };

    public static int[][][] allowedTypes = new int[][][]{
            {{}},
            {{1, 4, 6}, {1, 3, 5}},
            {{2, 3, 4}, {2, 5, 6}},
            {{1, 4, 6}, {2, 5, 6}},
            {{1, 3, 5}, {2, 5, 6}},
            {{1, 4, 6}, {2, 3, 4}},
            {{1, 3, 5}, {2, 3, 4}},
    };

    public boolean dfs(int row, int col, int[] types, boolean[][] visited, int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        if (row == m || row < 0 || col == n || col < 0 || visited[row][col]) {
            return false;
        }
        visited[row][col] = true;
        int type = grid[row][col];
        boolean valid = false;
        for (int t : types) {
            if (t == type) {
                valid = true;
                break;
            }
        }
        if (!valid) {
            return false;
        }
        boolean res = row == m - 1 && col == n - 1;
        for (int i = 0; i < directions[type].length; i++) {
            res = res || dfs(row + directions[type][i][0], col + directions[type][i][1], allowedTypes[type][i], visited, grid);
        }
        return res;
    }

}

性能

目标

给你一个二维字符网格数组 grid ，大小为 m x n ，你需要检查 grid 中是否存在 相同值 形成的环。

一个环是一条开始和结束于同一个格子的长度 大于等于 4 的路径。对于一个给定的格子，你可以移动到它上、下、左、右四个方向相邻的格子之一，可以移动的前提是这两个格子有 相同的值 。

同时，你也不能回到上一次移动时所在的格子。比方说，环 (1, 1) -> (1, 2) -> (1, 1) 是不合法的，因为从 (1, 2) 移动到 (1, 1) 回到了上一次移动时的格子。

如果 grid 中有相同值形成的环，请你返回 true ，否则返回 false 。

示例 1：

输入：grid = [["a","a","a","a"],["a","b","b","a"],["a","b","b","a"],["a","a","a","a"]]
输出：true
解释：如下图所示，有 2 个用不同颜色标出来的环：

示例 2：

输入：grid = [["c","c","c","a"],["c","d","c","c"],["c","c","e","c"],["f","c","c","c"]]
输出：true
解释：如下图所示，只有高亮所示的一个合法环：

示例 3：

输入：grid = [["a","b","b"],["b","z","b"],["b","b","a"]]
输出：false

说明：

• m == grid.length
• n == grid[i].length
• 1 <= m <= 500
• 1 <= n <= 500
• grid 只包含小写英文字母。

思路

判断网格图中是否存在相同元素值形成的环，要求环的长度大于等于 4。沿着环移动总是能回到起点（沿着环顺时针或者逆时针移动，不能往回走，环中的元素只能访问一次）。

从每个格子出发 dfs，记录已访问的坐标 visited[i][j]，假设上一个访问的坐标 (px, py)，针对每一个格子枚举上下左右四个方向，下一个格子坐标为 (nx, ny)，如果不是 (px, py)，并且没越界且元素值相等，返回 visited[nx][ny] || dfs(nx, ny, x, y, visited, grid)。对于网格图，如果 (nx, ny) 不等于 (px, py) 并且已访问过说明存在环，并且环的长度至少是 4。

代码

/**
 * @date 2026-04-26 23:14
 */
public class ContainsCycle1559 {

    public static int[][] directions = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    public boolean containsCycle(char[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        boolean[][] visited = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (visited[i][j]) {
                    continue;
                }
                if (dfs(i, j, -1, -1, visited, grid)) {
                    return true;
                }
            }
        }
        return false;
    }

    public boolean dfs(int x, int y, int px, int py, boolean[][] visited, char[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        visited[x][y] = true;
        for (int[] d : directions) {
            int nx = x + d[0];
            int ny = y + d[1];
            if ((nx != px || ny != py) && nx >= 0 && nx < m && ny >= 0 && ny < n && grid[x][y] == grid[nx][ny] &&
                    (
                            visited[nx][ny] || dfs(nx, ny, x, y, visited, grid)
                    )
            ) {
                return true;
            }
        }
        return false;
    }
}

性能

目标

给你两个整数数组 source 和 target ，长度都是 n 。还有一个数组 allowedSwaps ，其中每个 allowedSwaps[i] = [ai, bi] 表示你可以交换数组 source 中下标为 ai 和 bi（下标从 0 开始）的两个元素。注意，你可以按 任意 顺序 多次 交换一对特定下标指向的元素。

相同长度的两个数组 source 和 target 间的 汉明距离 是元素不同的下标数量。形式上，其值等于满足 source[i] != target[i] （下标从 0 开始）的下标 i（0 <= i <= n-1）的数量。

在对数组 source 执行 任意 数量的交换操作后，返回 source 和 target 间的 最小汉明距离 。

示例 1：

输入：source = [1,2,3,4], target = [2,1,4,5], allowedSwaps = [[0,1],[2,3]]
输出：1
解释：source 可以按下述方式转换：
- 交换下标 0 和 1 指向的元素：source = [2,1,3,4]
- 交换下标 2 和 3 指向的元素：source = [2,1,4,3]
source 和 target 间的汉明距离是 1 ，二者有 1 处元素不同，在下标 3 。

示例 2：

输入：source = [1,2,3,4], target = [1,3,2,4], allowedSwaps = []
输出：2
解释：不能对 source 执行交换操作。
source 和 target 间的汉明距离是 2 ，二者有 2 处元素不同，在下标 1 和下标 2 。

示例 3：

输入：source = [5,1,2,4,3], target = [1,5,4,2,3], allowedSwaps = [[0,4],[4,2],[1,3],[1,4]]
输出：0

说明：

• n == source.length == target.length
• 1 <= n <= 10^5
• 1 <= source[i], target[i] <= 10^5
• 0 <= allowedSwaps.length <= 10^5
• allowedSwaps[i].length == 2
• 0 <= ai, bi <= n - 1
• ai != bi

思路

有两个长度相等的数组 source 和 target，另有一个交换数组 allowedSwaps[i] = [ai, bi]，表示可以交换 source[ai] 与 source[bi]。求按照任意顺序交换任意次之后，source 与 target 的最小汉明距离。汉明距离指满足 source[i] != target[i] 的 i 的个数。

记录可以交换的连通元素的频次，然后比较对应位置上 target 的元素，最小的汉明距离就是对应不上的元素个数。

使用并查集记录连通分量，为每一个连通分量维护一个哈希表，记录元素出现的频次。枚举 target，找到所属的连通分量，将对应连通分量的元素频次 -1，如果最终频次小于 0 那么汉明距离 +1。

代码

/**
 * @date 2026-04-21 9:12
 */
public class MinimumHammingDistance1722 {

    public class UnionFind {
        int[] fa;

        public UnionFind(int n) {
            this.fa = new int[n];
            Arrays.setAll(this.fa, i -> i);
        }

        public int find(int e) {
            if (e != fa[e]) {
                fa[e] = find(fa[e]);
            }
            return fa[e];
        }

        public void merge(int x, int y) {
            int a = find(x);
            int b = find(y);
            if (a < b) {
                fa[b] = a;
            } else if (a > b) {
                fa[a] = b;
            }
        }
    }

    public int minimumHammingDistance(int[] source, int[] target, int[][] allowedSwaps) {
        int n = source.length;
        UnionFind uf = new UnionFind(n);
        for (int[] swap : allowedSwaps) {
            uf.merge(swap[0], swap[1]);
        }
        Map<Integer, Map<Integer, Integer>> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int c = uf.find(i);
            map.putIfAbsent(c, new HashMap<>());
            map.get(c).merge(source[i], 1, Integer::sum);
        }
        int res = 0;
        for (int i = 0; i < n; i++) {
            int c = uf.find(i);
            map.get(c).merge(target[i], -1, Integer::sum);
            if (map.get(c).get(target[i]) < 0) {
                res++;
            }
        }
        return res;
    }

}

性能

目标

给出长度相同的两个字符串s1 和 s2 ，还有一个字符串 baseStr 。

其中 s1[i] 和 s2[i] 是一组等价字符。

• 举个例子，如果 s1 = "abc" 且 s2 = "cde"，那么就有 'a' == 'c', 'b' == 'd', 'c' == 'e'。

等价字符遵循任何等价关系的一般规则：

• 自反性 ：'a' == 'a'
• 对称性 ：'a' == 'b' 则必定有 'b' == 'a'
• 传递性 ：'a' == 'b' 且 'b' == 'c' 就表明 'a' == 'c'

例如， s1 = "abc" 和 s2 = "cde" 的等价信息和之前的例子一样，那么 baseStr = "eed" , "acd" 或 "aab"，这三个字符串都是等价的，而 "aab" 是 baseStr 的按字典序最小的等价字符串

利用 s1 和 s2 的等价信息，找出并返回 baseStr 的按字典序排列最小的等价字符串。

示例 1：

输入：s1 = "parker", s2 = "morris", baseStr = "parser"
输出："makkek"
解释：根据 A 和 B 中的等价信息，我们可以将这些字符分为 [m,p], [a,o], [k,r,s], [e,i] 共 4 组。每组中的字符都是等价的，并按字典序排列。所以答案是 "makkek"。

示例 2：

输入：s1 = "hello", s2 = "world", baseStr = "hold"
输出："hdld"
解释：根据 A 和 B 中的等价信息，我们可以将这些字符分为 [h,w], [d,e,o], [l,r] 共 3 组。所以只有 S 中的第二个字符 'o' 变成 'd'，最后答案为 "hdld"。

示例 3：

输入：s1 = "leetcode", s2 = "programs", baseStr = "sourcecode"
输出："aauaaaaada"
解释：我们可以把 A 和 B 中的等价字符分为 [a,o,e,r,s,c], [l,p], [g,t] 和 [d,m] 共 4 组，因此 S 中除了 'u' 和 'd' 之外的所有字母都转化成了 'a'，最后答案为 "aauaaaaada"。

说明：

• 1 <= s1.length, s2.length, baseStr <= 1000
• s1.length == s2.length
• 字符串s1, s2, and baseStr 仅由从 'a' 到 'z' 的小写英文字母组成。

思路

定义 s1[i] 与 s2[i] 是等价字符，返回 baseStr 字典序最小的等价字符串。

可以使用并查集，用字典序小的字符代表等价字符，然后逐个替换 baseStr 即可。

代码

/**
 * @date 2025-06-05 0:15
 */
public class SmallestEquivalentString1061 {

    public class UnionFind {
        private int[] father;

        public UnionFind() {
            this.father = new int[26];
            Arrays.setAll(father, i -> i);
        }

        public void merge(int a, int b) {
            int x = find(a);
            int y = find(b);
            if (x == y) {
                return;
            }
            if (x < y) {
                father[y] = x;
            } else {
                father[x] = y;
            }
        }

        public int find(int a) {
            if (father[a] != a) {
                father[a] = find(father[a]);
            }
            return father[a];
        }
    }

    public String smallestEquivalentString(String s1, String s2, String baseStr) {
        int n = s1.length();
        UnionFind uf = new UnionFind();
        for (int i = 0; i < n; i++) {
            uf.merge(s1.charAt(i) - 'a', s2.charAt(i) - 'a');
        }
        StringBuilder sb = new StringBuilder();
        for (char c : baseStr.toCharArray()) {
            sb.append((char) ('a' + uf.find(c - 'a')));
        }
        return sb.toString();
    }

}

性能