LeetCode周记 EP24

2024-12-08

字数统计: 2k字 | 阅读时长: 9分

前言

最近忙着做毕设实验，之前的周记都搁置了。实验有了些结果，还不错。这周是每日一棋。

本周主题：复杂回溯、记忆化搜索

题目：

241204每日一题—Number of Valid Move Combinations On Chessboard
241207每日一题—Knight Probability in Chessboard
241208每日一题—Transform to Chessboard
Number of Valid Move Combinations On Chessboard

就是说一个move combo就是一个int[][] destinations，代表每个棋子要移动到的位置，每秒每个棋子移动一个格子，且移动过程中不能发生抢占格子的情况。这个目的地是根据棋子的可移动方向选的，包括原地不动。

DFS+回溯

思路：先预处理每个棋子的所有合法移动。写一个回溯，暴力枚举每个棋子的每个合法移动，如果这些棋子没有重叠在一起，则答案加一。

具体来说, 合法移动包含:

棋子的初始位置 $\left(x_0, y_0\right)$ 。
棋子的移动方向 $\left(d_x, d_y\right)$ 。
棋子的移动次数 step。

在回溯时，可以剪枝：如果当前棋子的当前这个合法移动，与前面的棋子冲突，即同一时刻两个棋子重叠，那么不往下递归，枚举当前棋子的下一个合法移动。

这个回溯的特点是层数很多，把每个节点想象成神经网络的一层，每层的节点数量是合法移动的数量，最终计算是其全连接的结果累加。且在判断是否回溯时，要符合所有先前节点的移动，由于这些移动可能所处的时间步不同，所以需要模拟其发展过程，确认移动过程中不存在冲突即合法。

class Solution {
    // 每种棋子的移动方向
    private static final Map<Character, int[][]> PIECE_DIRS = Map.of(
        'r', new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}, // 车
        'b', new int[][]{{1, 1}, {-1, 1}, {-1, -1}, {1, -1}}, // 象
        'q', new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}, {1, 1}, {-1, 1}, {-1, -1}, {1, -1}} // 皇后
    );

    public int countCombinations(String[] pieces, int[][] positions) {
        int n = pieces.length;
        // 预处理所有合法移动
        Move[][] allMoves = new Move[n][];
        for (int i = 0; i < n; i++) {
            allMoves[i] = generateMoves(positions[i][0], positions[i][1], PIECE_DIRS.get(pieces[i].charAt(0)));
        }

        Move[] path = new Move[n]; // 注意 path 的长度是固定的
        return dfs(0, n, allMoves, path);
    }

    // Java 14 引入的不可变的数据载体类，Java 16 成为正式特性
    // 起点 (x0,y0)，移动方向 (dx,dy)，移动次数 step
    private record Move(int x0, int y0, int dx, int dy, int step) {
    }

    // 计算位于 (x0,y0) 的棋子在 dirs 这些方向上的所有合法移动
    private Move[] generateMoves(int x0, int y0, int[][] dirs) {
        final int SIZE = 8;
        List<Move> moves = new ArrayList<>();
        moves.add(new Move(x0, y0, 0, 0, 0)); // 原地不动
        for (int[] d : dirs) {
            // 往 d 方向走 1,2,3,... 步
            int x = x0 + d[0], y = y0 + d[1];
            // 这里不限制step的大小，只是沿着一个方向一直走
            for (int step = 1; 0 < x && x <= SIZE && 0 < y && y <= SIZE; step++) {
                moves.add(new Move(x0, y0, d[0], d[1], step));
                x += d[0];
                y += d[1];
            }
        }
        return moves.toArray(Move[]::new);
    }

    // 判断两个移动是否合法，即不存在同一时刻两个棋子重叠的情况
    private boolean isValid(Move m1, Move m2) {
        int x1 = m1.x0, y1 = m1.y0; // 初始位置
        int x2 = m2.x0, y2 = m2.y0;
        for (int i = 0; i < Math.max(m1.step, m2.step); i++) {
            // 每一秒走一步
            if (i < m1.step) {
                x1 += m1.dx;
                y1 += m1.dy;
            }
            if (i < m2.step) {
                x2 += m2.dx;
                y2 += m2.dy;
            }
            if (x1 == x2 && y1 == y2) { // 重叠
                return false;
            }
        }
        return true;
    }

    private int dfs(int i, int n, Move[][] allMoves, Move[] path) {
        // i表示第i个棋子， 想象一共有3个节点，每个节点有三个合法方向，则该代码对其进行全连接累加。
        if (i == n) {
            return 1;
        }
        int res = 0;
        // 标签语法，用于控制特定层次的循环或提前退出多层循环
        outer:
        // 枚举当前棋子的所有合法移动
        for (Move move1 : allMoves[i]) {
            // 判断合法移动 move1 是否有效
            for (int j = 0; j < i; j++) {
                if (!isValid(move1, path[j])) {
                    continue outer; // 无效，枚举下一个 move1
                }
            }
            path[i] = move1; // 直接覆盖，无需恢复现场
            res += dfs(i + 1, n, allMoves, path); // 枚举后续棋子的所有合法移动组合
        }
        return res;
    }
}

Knight Probability in Chessboard

原问题是Knight走$k$步后留在棋盘上的概率，走出一步后，问题变为了Knight走$k-1$步后留在棋盘上的概率，是一个规模更小的子问题，可递归求解。直接递归超时，如下：

// author: SilenceZheng66
class Solution {
    public int[] factor1 = new int[]{1, 2};
    public int[] factor2 = new int[]{-1, 1};
    public int total = 0;
    public double knightProbability(int n, int k, int row, int column) {
        move(n, k, 0, row, column);
        return (double)total/(double)Math.pow(8, k);
    }

    public void move(int n, int k, int cnt, int r, int c){
        if(r>=n||c>=n||r<0||c<0) return;
        if(cnt==k){
            total++;
            return;
        }
        // 组合落点
        for(int f1:factor1){
            for(int f2:factor2){
                for(int f3:factor2){
                    move(n, k, cnt+1, r+f1*f2, c+(3-f1)*f3);
                }
            }
        }
    }
}

记忆化搜索

上面的解法有一个问题：递归函数不可记忆，无法进行优化。因此需要重新确定状态和计算方式。

定义状态为 $dfs(k,i,j)$，表示从 $(i,j)$ 出发，走 $k$ 步后仍然在棋盘上的概率。

枚举可走的八个方向, 其中有 $\frac{1}{8}$ 概率走到了 $(x, y)$, 问题变成：

从 $(x, y)$ 出发, 走 $k-1$ 步后仍然在棋盘上的概率, 即 $d f s(k-1, x, y)$

八种情况累加，得

$d f s(k, i, j)=\frac{1}{8} \sum_{(x, y)} d f s(k-1, x, y)$

递归边界：如果Knight出界, 那么在棋盘上的概率为 0 , 即 $d f s(k, i, j)=0$ 。如果 $k=0$ 时Knight仍然在棋盘上, 那么概率为 1 , 即 $d f s(0, i, j)=1$ 。

递归入口：$d f s(k, r o w, c o l u m n)$, 也就是答案。

三、递归搜索 + 保存递归返回值 = 记忆化搜索
考虑到整个递归过程中有大量重复递归调用（递归入参相同）。由于递归函数没有副作用, 同样的入参无论计算多少次, 算出来的结果都是一样的, 因此可以用记忆化搜索来优化：

如果一个状态（递归入参）是第一次遇到，那么可以在返回前，把状态及其结果记到一个 memo 数组中。
如果一个状态不是第一次遇到（memo 中保存的结果不等于 memo 的初始值), 那么可以直接返回 memo 中保存的结果。

注意：memo 数组的初始值一定不能等于要记忆化的值。

class Solution {
    private static final int[][] DIRS = {{2, 1}, {1, 2}, {-1, 2}, {-2, 1}, {-2, -1}, {-1, -2}, {1, -2}, {2, -1}};

    public double knightProbability(int n, int k, int row, int column) {
        double[][][] memo = new double[k + 1][n][n];
        return dfs(k, row, column, n, memo);
    }

    private double dfs(int k, int i, int j, int n, double[][][] memo) {
        if (i < 0 || j < 0 || i >= n || j >= n) {
            return 0;
        }
        if (k == 0) {
            return 1;
        }
        if (memo[k][i][j] > 0) { // 之前计算过
            return memo[k][i][j];
        }
        double res = 0;
        for (int[] d : DIRS) {
            res += dfs(k - 1, i + d[0], j + d[1], n, memo);
        }
        return memo[k][i][j] = res / DIRS.length; // 记忆化
    }
}