标签： dfs

目标

给你一个大小为 m * n 的二维整数数组 grid。

你从 左上角 的单元格 (0, 0) 出发，想要到达 右下角 的单元格 (m - 1, n - 1)。

在每一步中，你 可以 向右或向下 移动。

路径的 代价 定义为该路径上所有单元格（包括 起点和终点）的值的 按位异或。

返回从 (0, 0) 到 (m - 1, n - 1) 的所有有效路径中 最小 的可能异或值。

示例 1：

输入： grid = [[1,2],[3,4]]
输出： 6
解释：
有两条有效路径：
(0, 0) → (0, 1) → (1, 1)，异或值为：1 XOR 2 XOR 4 = 7
(0, 0) → (1, 0) → (1, 1)，异或值为：1 XOR 3 XOR 4 = 6
所有有效路径中的最小异或值为 6。

示例 2：

输入： grid = [[6,7],[5,8]]
输出： 9
解释：
有两条有效路径：
(0, 0) → (0, 1) → (1, 1)，异或值为：6 XOR 7 XOR 8 = 9
(0, 0) → (1, 0) → (1, 1)，异或值为：6 XOR 5 XOR 8 = 11
所有有效路径中的最小异或值为 9。

示例 3：

输入： grid = [[2,7,5]]
输出： 0
解释：
只有一条有效路径：
(0, 0) → (0, 1) → (0, 2)，异或值为：2 XOR 7 XOR 5 = 0
这条路径的异或值为 0，这是可能达到的最小值。

说明：

• 1 <= m == grid.length <= 1000
• 1 <= n == grid[i].length <= 1000
• m * n <= 1000
• 0 <= grid[i][j] <= 1023​

思路

有一个 m x n 的网格，允许向下或向右移动，求从左上到右下的路径上元素异或和的最小值。

注意到 m * n <= 1000，可以记忆路径到达 (i,j) 时的异或和，如果该状态已经访问过则跳过。

代码

/**
 * @date 2026-10-28 9:18
 */
public class MinCost3882 {

    public int minCost(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        boolean[][][] mem = new boolean[m][n][1024];
        dfs(0, 0, 0, grid, mem);
        for (int i = 0; i < 1024; i++) {
            if (mem[m - 1][n - 1][i]) {
                return i;
            }
        }
        return -1;
    }

    public void dfs(int i, int j, int xor, int[][] grid, boolean[][][] mem) {
        int m = grid.length;
        int n = grid[0].length;
        if (i >= m || j >= n) {
            return;
        }
        xor ^= grid[i][j];
        if (mem[i][j][xor]) {
            return;
        }
        mem[i][j][xor] = true;
        dfs(i + 1, j, xor, grid, mem);
        dfs(i, j + 1, xor, grid, mem);
    }

}

性能

目标

给你一棵二叉树的根节点 root ，找出并返回满足要求的节点数，要求节点的值等于其 子树 中值的 平均值 。

注意：

• n 个元素的平均值可以由 n 个元素 求和 然后再除以 n ，并 向下舍入 到最近的整数。
• root 的 子树 由 root 和它的所有后代组成。

示例 1：

输入：root = [4,8,5,0,1,null,6]
输出：5
解释：
对值为 4 的节点：子树的平均值 (4 + 8 + 5 + 0 + 1 + 6) / 6 = 24 / 6 = 4 。
对值为 5 的节点：子树的平均值 (5 + 6) / 2 = 11 / 2 = 5 。
对值为 0 的节点：子树的平均值 0 / 1 = 0 。
对值为 1 的节点：子树的平均值 1 / 1 = 1 。
对值为 6 的节点：子树的平均值 6 / 1 = 6 。

示例 2：

输入：root = [1]
输出：1
解释：对值为 1 的节点：子树的平均值 1 / 1 = 1。

说明：

• 树中节点数目在范围 [1, 1000] 内
• 0 <= Node.val <= 1000

思路

有一颗二叉树，统计其中节点值等于子树平均值（节点本身及其子树的节点值之和除以节点个数向下取整）的节点个数。

dfs 依题意统计即可。

代码

/**
 * @date 2026-09-10 8:56
 */
public class AverageOfSubtree2265 {

    int res = 0;

    public int averageOfSubtree(TreeNode root) {
        dfs(root);
        return res;
    }

    public class Dto {
        public int sum;
        public int num;

        public Dto() {
        }

        public Dto(int sum, int num) {
            this.sum = sum;
            this.num = num;
        }
    }

    public Dto dfs(TreeNode node) {
        if (node == null) {
            return new Dto();
        }
        Dto cur = new Dto(node.val, 1);
        Dto l = dfs(node.left);
        Dto r = dfs(node.right);
        cur.sum += l.sum + r.sum;
        cur.num += l.num + r.num;
        if (node.val == cur.sum / cur.num) {
            res++;
        }
        return cur;
    }
}
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode() {}
 * TreeNode(int val) { this.val = val; }
 * TreeNode(int val, TreeNode left, TreeNode right) {
 * this.val = val;
 * this.left = left;
 * this.right = right;
 * }
 * }
 */

性能

目标

给你一棵 n 个节点的无向树，节点从 1 到 n 编号，树以节点 1 为根。树由一个长度为 n - 1 的二维整数数组 edges 表示，其中 edges[i] = [ui, vi] 表示在节点 ui 和 vi 之间有一条边。

一开始，所有边的权重为 0。你可以将每条边的权重设为 1 或 2。

两个节点 u 和 v 之间路径的 代价 是连接它们路径上所有边的权重之和。

选择任意一个 深度最大 的节点 x。返回从节点 1 到 x 的路径中，边权重之和为 奇数 的赋值方式数量。

由于答案可能很大，返回它对 10^9 + 7 取模的结果。

注意： 忽略从节点 1 到节点 x 的路径外的所有边。

示例 1：

输入： edges = [[1,2]]
输出： 1
解释：
从节点 1 到节点 2 的路径有一条边（1 → 2）。
将该边赋权为 1 会使代价为奇数，赋权为 2 则为偶数。因此，合法的赋值方式有 1 种。

示例 2：

输入： edges = [[1,2],[1,3],[3,4],[3,5]]
输出： 2
解释：
最大深度为 2，节点 4 和节点 5 都在该深度，可以选择任意一个。
例如，从节点 1 到节点 4 的路径包括两条边（1 → 3 和 3 → 4）。
将两条边赋权为 (1,2) 或 (2,1) 会使代价为奇数，因此合法赋值方式有 2 种。

提示：

• 2 <= n <= 10^5
• edges.length == n - 1
• edges[i] == [ui, vi]
• 1 <= ui, vi <= n
• edges 表示一棵合法的树。

思路

有一颗含有 n 个节点的树，编号为 1 ~ n，根节点编号是 1。edges[i] = [ui, vi]，表示节点 ui 与 vi 之间有一条边。定义节点 u 与 v 之间的代价为它们之间路径上边的权重之和。可以为每一条边赋予权重 1 或 2，求使得根节点到最远叶子节点代价为奇数的赋权方案数。

定义到达当前节点代价为奇数或偶数的方案数为 dp[i][1] 与 dp[i][0]，状态转移方程为 dp[i][0] = dp[prev][0] + dp[prev][1]，dp[i][1] = dp[prev][0] + dp[prev][1]。

观察发现 dp[i][0] == dp[i][1]，因此代价为奇数的方案数为 dp[i][1] = 2 * dp[prev][1]。假设树的深度为 d，方案数为 2^(d - 1)。

求出树的深度 d，从中选取奇数条边赋值为 1，方案数为 2^(d - 1)。

代码

/**
 * @date 2026-06-11 10:16
 */
public class AssignEdgeWeights3558 {

    public int assignEdgeWeights(int[][] edges) {
        int n = edges.length + 1;
        List<Integer>[] g = new ArrayList[n + 1];
        Arrays.setAll(g, i -> new ArrayList<>());
        for (int[] edge : edges) {
            g[edge[0]].add(edge[1]);
            g[edge[1]].add(edge[0]);
        }
        int d = dfs(0, 1, g);
        return pow(2, d - 1, 1000000007);
    }

    public int dfs(int fa, int cur, List<Integer>[] g) {
        int res = 0;
        for (Integer next : g[cur]) {
            if (next == fa) {
                continue;
            }
            res = Math.max(res, dfs(cur, next, g) + 1);
        }
        return res;
    }

    public int pow(int base, int exp, int mod) {
        long res = 1L;
        while (exp > 0) {
            if ((exp & 1) == 1) {
                res = res * base % mod;
            }
            base = (int) ((long) base * base % mod);
            exp >>= 1;
        }
        return (int) res;
    }

}

性能

目标

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

}

性能