跳到主要内容

289. 生命游戏

1. 题目简介​

难度：中等，原题链接：289. 生命游戏。

根据 百度百科 ， 生命游戏 ，简称为 生命游戏 或 康威生命游戏 ，是英国数学家约翰·康威在 1970 年发明的细胞自动机。

给定一个包含 m × n 个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态： 1 即为 活细胞 （live），或 0 即为 死细胞 （dead）。每个细胞与其八个相邻位置（水平，垂直，对角线）的细胞都遵循以下四条生存定律：

  1. 如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞数变为 死细胞 。
  2. 如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞数不变。
  3. 如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞数变为 死细胞 。
  4. 如果死细胞周围八个位置有两个或三个活细胞，则该位置死细胞变为 活细胞 。
  5. 如果死细胞周围八个位置的活细胞数不到两个，则该位置死细胞仍然为 死细胞 。

根据当前状态，写一个函数来计算面板上所有细胞的下一个（一次更新后的）状态。下一个状态是通过将上述规则同时应用于整个当前状态下的面板而生成的。

示例： 输入：board = [[0,1,0],[0,0,1],[1,1,1],[0,0,0]] 输出：[[0,0,0],[1,0,1],[0,1,1],[0,1,0]]

2. 问题分析​

细胞仅会处于0和1两种状态，另外更新后依然会处于这两种状态。因此细胞状态的更新是一个有限状态机，我们可以列举出所有可能的状态转移：

  • 0 -> 0
  • 1 -> 0
  • 0 -> 1
  • 1 -> 1

观察上述状态转移，我们可以发现，0 -> 1 和 1 -> 0 这两种状态转移，改变了细胞的初始状态。

我们需要同时维护细胞的「初始状态」和「更新后的状态」。「初始状态」用于帮助其他细胞进行状态的更新，「更新后的状态」用于返回最后的结果。

一种简单的实现方式是，维护另一个「更新后的状态」数组，遍历原始数组，根据规则更新「更新后的状态」数组。全部更新后即为最后的结果。

让我们加大难度。题目中要求原地更新。那么难点就变成如何去维护 0 -> 1 和 1 -> 0 这两种状态转移。

原始数组是 int[][] 类型，因此我们可以引入其他的数字来表示状态转移：

  • 0 -> 0 保持不变
  • 1 -> 0 用 -1 表示
  • 0 -> 1 用 -2 表示
  • 1 -> 1 保持不变

在遍历数组时，如果遇到 -1 或 -2，则按照其更新前的状态，对周边的细胞进行状态的更新。

更新完全部细胞后，再将数组中所有 -1 和 -2 更新为 0 和 1，即为最后的结果。

状态转移示意图：

0 -----> 0  (保持不变)
1 -----> 0  (标记为 -1)
0 -----> 1  (标记为 -2)
1 -----> 1  (保持不变)

3. 代码实现​

class Solution {
    public void gameOfLife(int[][] board) {
        // 第一次遍历：根据规则更新状态
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                board[i][j] = after(board, i, j);
            }
        }
        
        // 第二次遍历：将临时状态转换为最终状态
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == -1) {
                    board[i][j] = 0;
                } else if (board[i][j] == -2) {
                    board[i][j] = 1;
                }
            }
        }
    }
    
    // 计算细胞的下一个状态
    private int after(int[][] board, int m, int n) {
        int count = 0;
        for (int i = m - 1; i <= m + 1; i++) {
            for (int j = n - 1; j <= n + 1; j++) {
                if (i < 0 || j < 0 || i >= board.length || j >= board[0].length) {
                    continue;
                }
                if (i == m && j == n) {
                    continue;
                }
                if (board[i][j] == 1 || board[i][j] == -1) {
                    count++;
                }
            }
        }
        if (count < 2 || count > 3) {
            return board[m][n] == 1 ? -1 : 0;
        } else if (count == 3) {
            return board[m][n] == 0 ? -2 : 1;
        } else {
            return board[m][n];
        }
    }
}

4. 复杂度分析​

  • 时间复杂度：O(m * n)，其中 m 是矩阵的行数，n 是矩阵的列数。
  • 空间复杂度：O(1)，原地更新，仅使用常数空间。

5. 总结​

原地更新问题，通常需要引入其他数字来表示状态转移，或者对一些特殊的位置进行标记。本题的关键点是：

  1. 使用负数（-1，-2）作为临时状态来追踪细胞的变化
  2. 两次遍历实现原地更新：第一次标记状态转移，第二次完成最终转换
  3. 在检查邻居状态时，需要将临时状态(-1)还原为原始状态(1)进行判断

类似的原地更新问题有：