标签： dfs

目标

给你一个 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;
    }

}

性能

目标

给定一个根为 root 的二叉树，每个节点的深度是 该节点到根的最短距离 。

返回包含原始树中所有 最深节点 的 最小子树 。

如果一个节点在 整个树 的任意节点之间具有最大的深度，则该节点是 最深的 。

一个节点的 子树 是该节点加上它的所有后代的集合。

示例 1：

输入：root = [3,5,1,6,2,0,8,null,null,7,4]
输出：[2,7,4]
解释：
我们返回值为 2 的节点，在图中用黄色标记。
在图中用蓝色标记的是树的最深的节点。
注意，节点 5、3 和 2 包含树中最深的节点，但节点 2 的子树最小，因此我们返回它。

示例 2：

输入：root = [1]
输出：[1]
解释：根节点是树中最深的节点。

示例 3：

输入：root = [0,1,3,null,2]
输出：[2]
解释：树中最深的节点为 2 ，有效子树为节点 2、1 和 0 的子树，但节点 2 的子树最小。

说明：

• 树中节点的数量在 [1, 500] 范围内。
• 0 <= Node.val <= 500
• 每个节点的值都是 独一无二 的。

思路

有一颗二叉树 root，返回包含所有最深节点的最小子树。

dfs 返回子树最大深度，如果左右子树的深度都等于全局的最大深度，则返回当前节点。也就是找到所有最深节点的最近公共祖先。

代码

/**
 * @date 2026-01-09 8:45
 */
public class SubtreeWithAllDeepest865 {

    public TreeNode subtreeWithAllDeepest(TreeNode root) {
        dfs(root, -1);
        return res;
    }

    public int dfs(TreeNode node, int deep) {
        if (node == null) {
            return deep;
        }
        int left = dfs(node.left, deep + 1);
        int right = dfs(node.right, deep + 1);
        int max = Math.max(left, right);
        maxDeep = Math.max(max, maxDeep);
        if (left == maxDeep && right == maxDeep) {
            res = node;
        }
        return max;
    }

}

性能

目标

给你一棵二叉树，它的根为 root 。请你删除 1 条边，使二叉树分裂成两棵子树，且它们子树和的乘积尽可能大。

由于答案可能会很大，请你将结果对 10^9 + 7 取模后再返回。

示例 1：

输入：root = [1,2,3,4,5,6]
输出：110
解释：删除红色的边，得到 2 棵子树，和分别为 11 和 10 。它们的乘积是 110 （11*10）

示例 2：

输入：root = [1,null,2,3,4,null,null,5,6]
输出：90
解释：移除红色的边，得到 2 棵子树，和分别是 15 和 6 。它们的乘积为 90 （15*6）

示例 3：

输入：root = [2,3,9,10,7,8,6,5,4,11,1]
输出：1025

示例 4：

输入：root = [1,1]
输出：1

说明：

• 每棵树最多有 50000 个节点，且至少有 2 个节点。
• 每个节点的值在 [1, 10000] 之间。

思路

删除二叉树的一条边，使得产生的两个子树和的乘积最大。

直接的想法是两次遍历，第一次遍历求得所有节点和。第二次遍历则是计算乘积最大值。

可以将子树和保存起来，遍历结束后直接处理和。

注意：求的是最大的乘积然后取模，而非模的最大值。先找出最大的乘积再取模，不能先对乘积取模再比较。

代码

/**
 * @date 2026-01-07 8:52
 */
public class MaxProduct1339 {

    public long res = 0L;

    public int maxProduct(TreeNode root) {
        int mod = 1000000007;
        int totalSum = dfs(root);
        dfs(root, totalSum);
        return (int) (res % mod);
    }

    public int dfs(TreeNode node) {
        if (node == null) {
            return 0;
        }
        return node.val + dfs(node.left) + dfs(node.right);
    }

    public int dfs(TreeNode node, int totalSum) {
        if (node == null) {
            return 0;
        }
        int sum = node.val + dfs(node.left, totalSum) + dfs(node.right, totalSum);
        res = Math.max(res, (long) sum * (totalSum - sum));
        return sum;
    }

}

性能