力扣经典150题第三十八题：生命游戏
引言
本篇博客介绍了力扣经典150题中的第三十八题：生命游戏。生命游戏是约翰·康威在1970年发明的细胞自动机，每个细胞的状态由其周围的八个相邻细胞状态决定。根据题目要求，我们需要实现一个原地算法，将给定的 m x n 网格面板 board 的当前状态转换为下一个状态。
题目详解
给定一个 m x n 网格面板 board，每个格子的状态是 1（活细胞）或 0（死细胞）。根据生存定律，下一个状态的细胞状态取决于周围八个相邻位置的细胞状态。
具体生存定律如下：
- 如果活细胞周围的活细胞数少于两个，则该位置活细胞死亡。
- 如果活细胞周围有两个或三个活细胞，则该位置活细胞仍然存活。
- 如果活细胞周围有超过三个活细胞，则该位置活细胞死亡。
- 如果死细胞周围恰好有三个活细胞，则该位置死细胞复活。
要求使用原地算法实现状态转换，即在不使用额外空间的情况下，直接修改给定的 board。
解题思路
为了实现原地算法，我们可以使用额外的状态表示当前细胞状态和下一个状态。
具体步骤如下：
- 使用额外状态表示细胞的当前状态和下一个状态。这里可以用两位二进制数来表示，比如 00 表示死细胞到死细胞，01 表示活细胞到死细胞，10 表示死细胞到活细胞，11 表示活细胞到活细胞。
- 遍历原始矩阵，计算每个细胞周围的活细胞数量，并根据当前状态确定下一个状态。
- 根据下一个状态更新原始矩阵。
通过上述步骤，可以实现原地算法来更新生命游戏的状态。
代码实现
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)，满足题目要求的原地修改条件。
总结
本篇博客介绍了如何使用原地
算法实现生命游戏的状态转换。通过额外状态表示当前状态和下一个状态，并根据生存定律更新矩阵，最终实现了生命游戏的状态转换。
