LeetCode 289. 生命游戏

◎

本节目标

用额外整数状态同时保存格子的旧值与新值，在原矩阵中完成同步更新。

这道题是数组与矩阵综合框架中的同步状态母题。所有格子必须根据同一时刻的旧状态更新，不能让前面写入的新状态影响后面的邻居统计。

查看原题

题意与约束

矩阵中的 1 表示活细胞，0 表示死细胞。每个格子的下一状态由八个邻居中的活细胞数量决定：

• 活细胞邻居少于两个或多于三个时死亡；
• 活细胞有两个或三个活邻居时存活；
• 死细胞恰有三个活邻居时复活。

要求直接在输入矩阵中更新下一代。

第一反应：复制旧矩阵

复制一份旧矩阵最直观：从副本读取，向原矩阵写入。空间复杂度是 O(mn)。

如果要原地更新，必须让一个整数同时表达“旧状态”和“新状态”。本题只需四种组合：

编码	旧状态	新状态
0	死	死
1	活	活
2	活	死
3	死	活

统计邻居时，把 1 和 2 都视为旧状态下的活细胞。全部格子编码完成后，再统一对 2、3 解码。

原地修改

函数没有返回值，而是在原矩阵中完成两轮处理。第一轮用状态编码保留每个格子的旧状态并写入新状态，第二轮统一取模还原为 0 或 1；调用者最终读取的仍是同一个原矩阵。

代码实现

邻居循环跳过中心格，并在读取前检查行列边界。解码阶段使用对 2 取模得 0、对 3 取模得 1。

C++

C++17

#include <vector>
using namespace std;

class Solution {
public:
    void gameOfLife(vector<vector<int>>& board) {
        if (board.empty() || board[0].empty()) {
            return;
        }

        int rows = static_cast<int>(board.size());
        int cols = static_cast<int>(board[0].size());
        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < cols; col++) {
                int liveNeighbors = 0;
                for (int rowOffset = -1; rowOffset <= 1; rowOffset++) {
                    for (int colOffset = -1; colOffset <= 1; colOffset++) {
                        if (rowOffset == 0 && colOffset == 0) {
                            continue;
                        }
                        int nextRow = row + rowOffset;
                        int nextCol = col + colOffset;
                        if (
                            nextRow >= 0 &&
                            nextRow < rows &&
                            nextCol >= 0 &&
                            nextCol < cols &&
                            (board[nextRow][nextCol] == 1 ||
                             board[nextRow][nextCol] == 2)
                        ) {
                            liveNeighbors++;
                        }
                    }
                }

                if (board[row][col] == 1 &&
                    (liveNeighbors < 2 || liveNeighbors > 3)) {
                    board[row][col] = 2;
                } else if (board[row][col] == 0 && liveNeighbors == 3) {
                    board[row][col] = 3;
                }
            }
        }

        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < cols; col++) {
                board[row][col] %= 2;
            }
        }
    }
};

Python

Python 3

class Solution:
    def gameOfLife(self, board):
        if not board or not board[0]:
            return

        rows = len(board)
        cols = len(board[0])
        for row in range(rows):
            for col in range(cols):
                live_neighbors = 0
                for row_offset in range(-1, 2):
                    for col_offset in range(-1, 2):
                        if row_offset == 0 and col_offset == 0:
                            continue
                        next_row = row + row_offset
                        next_col = col + col_offset
                        if (
                            0 <= next_row < rows
                            and 0 <= next_col < cols
                            and board[next_row][next_col] in (1, 2)
                        ):
                            live_neighbors += 1

                if board[row][col] == 1 and (
                    live_neighbors < 2 or live_neighbors > 3
                ):
                    board[row][col] = 2
                elif board[row][col] == 0 and live_neighbors == 3:
                    board[row][col] = 3

        for row in range(rows):
            for col in range(cols):
                board[row][col] %= 2

复杂度分析

• 时间复杂度：O(mn)。每个格子检查固定八个邻居，再统一解码一次。
• 空间复杂度：O(1)，不计循环变量，没有创建同规模副本。

易错点

• 更新一个格子后直接写成新 0/1，导致后续读取到新状态。
• 统计时只把 1 视为旧活，漏掉编码 2。
• 把编码 3 当作旧活细胞。
• 邻居循环没有跳过当前格子，或没有检查边界。

模式迁移

原地状态编码适用于“必须同步更新、旧状态种类少、数值还能容纳过渡状态”的问题。设计编码时要保证两件事：处理中随时能读取旧状态，结束后能无歧义地还原新状态。