跳到主要内容

289. 生命游戏

1. 题目简介​

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

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

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

  1. 如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞数变为 死细胞 。
  2. 如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞数不变。
  3. 如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞数变为 死细胞 。
  4. 如果死细胞周围八个位置恰好有三个活细胞，则该位置死细胞变为活细胞；否则保持死亡。

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

示例： 输入：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、1 两种取值，一共存在四种变化：

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

其中 -1 表示原来活着、下一轮死亡，-2 表示原来死亡、下一轮复活。统计活邻居时，只把 1 和 -1 计入数量；0 和 -2 都按原来的死细胞处理。这样，即使邻居已经被更新，也仍然能读出它的旧状态。

第一次遍历时，after 检查周围八个位置，跳过越界位置和细胞自身，再按活邻居数量返回状态标记。全部细胞都计算完以后，第二次遍历把 -1 转成 0、-2 转成 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. 关联问题​

复用输入空间之前，要先看题目是否允许修改输入，以及后续计算还需要保留哪些信息：

来源：Coding 101 原文 · 免费阅读，引用请保留出处。内容使用说明