力扣经典150题第三十八题：生命游戏

力扣经典150题第三十八题：生命游戏

引言

本篇博客介绍了力扣经典150题中的第三十八题：生命游戏。生命游戏是约翰·康威在1970年发明的细胞自动机，每个细胞的状态由其周围的八个相邻细胞状态决定。根据题目要求，我们需要实现一个原地算法，将给定的 m x n 网格面板 board 的当前状态转换为下一个状态。

题目详解

给定一个 m x n 网格面板 board，每个格子的状态是 1（活细胞）或 0（死细胞）。根据生存定律，下一个状态的细胞状态取决于周围八个相邻位置的细胞状态。

具体生存定律如下：

• 如果活细胞周围的活细胞数少于两个，则该位置活细胞死亡。
• 如果活细胞周围有两个或三个活细胞，则该位置活细胞仍然存活。
• 如果活细胞周围有超过三个活细胞，则该位置活细胞死亡。
• 如果死细胞周围恰好有三个活细胞，则该位置死细胞复活。

要求使用原地算法实现状态转换，即在不使用额外空间的情况下，直接修改给定的 board。

解题思路

为了实现原地算法，我们可以使用额外的状态表示当前细胞状态和下一个状态。

具体步骤如下：

1. 使用额外状态表示细胞的当前状态和下一个状态。这里可以用两位二进制数来表示，比如 00 表示死细胞到死细胞，01 表示活细胞到死细胞，10 表示死细胞到活细胞，11 表示活细胞到活细胞。
2. 遍历原始矩阵，计算每个细胞周围的活细胞数量，并根据当前状态确定下一个状态。
3. 根据下一个状态更新原始矩阵。

通过上述步骤，可以实现原地算法来更新生命游戏的状态。

代码实现

public class GameOfLife {
    public void gameOfLife(int[][] board) {
        int m = board.length;
        int n = board[0].length;

        // 遍历矩阵，根据当前状态确定下一个状态
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int liveNeighbors = countLiveNeighbors(board, i, j, m, n);

                // 根据当前状态和周围活细胞数量确定下一个状态
                if (board[i][j] == 1) {
                    if (liveNeighbors < 2 || liveNeighbors > 3) {
                        // 活细胞死亡
                        board[i][j] = 3; // 01
                    }
                } else {
                    if (liveNeighbors == 3) {
                        // 死细胞复活
                        board[i][j] = 2; // 10
                    }
                }
            }
        }

        // 更新矩阵为下一个状态
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                board[i][j] >>= 1; // 右移一位得到下一个状态
            }
        }
    }

    // 计算某个细胞周围的活细胞数量
    private int countLiveNeighbors(int[][] board, int x, int y, int m, int n) {
        int[][] directions = {
            {-1, -1}, {-1, 0}, {-1, 1},
            {0, -1},         {0, 1},
            {1, -1}, {1, 0}, {1, 1}
        };
        int liveCount = 0;

        for (int[] dir : directions) {
            int nx = x + dir[0];
            int ny = y + dir[1];
            if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
                if (board[nx][ny] == 1 || board[nx][ny] == 3) {
                    liveCount++;
                }
            }
        }

        return liveCount;
    }

    public static void main(String[] args) {
        GameOfLife solution = new GameOfLife();

        // 示例测试
        int[][] board1 = {{0, 1, 0}, {0, 0, 1}, {1, 1, 1}, {0, 0, 0}};
        System.out.println("输入矩阵1：");
        printMatrix(board1);
        solution.gameOfLife(board1);
        System.out.println("下一个状态矩阵1：");
        printMatrix(board1);

        int[][] board2 = {{1, 1}, {1, 0}};
        System.out.println("输入矩阵2：");
        printMatrix(board2);
        solution.gameOfLife(board2);
        System.out.println("下一个状态矩阵2：");
        printMatrix(board2);
    }

    private static void printMatrix(int[][] matrix) {
        for (int[] row : matrix) {
            System.out.println(Arrays.toString(row));
        }
        System.out.println();
    }
}

示例演示

展示了两个不同的矩阵输入，并输出了生命游戏的下一个状态矩阵。

复杂度分析

该解法的时间复杂度为 O(m * n)，空间复杂度为 O(1)，满足题目要求的原地修改条件。

总结

本篇博客介绍了如何使用原地

算法实现生命游戏的状态转换。通过额外状态表示当前状态和下一个状态，并根据生存定律更新矩阵，最终实现了生命游戏的状态转换。