289. 生命游戏

Medium

题目描述

根据维基百科的描述：“生命游戏，简称为生命，是英国数学家约翰·霍顿·康威在1970年设计的细胞自动机。”

游戏板由 m x n 个细胞组成，每个细胞都有一个初始状态：活细胞（用 1 表示）或死细胞（用 0 表示）。每个细胞与其八个相邻细胞（水平、垂直、对角线）相互作用，遵循以下四个规则（摘自上述维基百科文章）：

任何活细胞如果邻居中的活细胞少于两个，就会因人口不足而死亡。
任何活细胞如果邻居中有两个或三个活细胞，就能存活到下一代。
任何活细胞如果邻居中的活细胞多于三个，就会因人口过多而死亡。
任何死细胞如果邻居中恰好有三个活细胞，就会因繁殖而成为活细胞。

棋盘的下一个状态是通过将上述规则同时应用于当前状态的 m x n 网格棋盘中的每个细胞来确定的。在这个过程中，出生和死亡是同时发生的。

给定棋盘的当前状态，更新棋盘以反映其下一个状态。

注意你不需要返回任何东西。

示例 1：

输入：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：

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

提示：

m == board.length
n == board[i].length
1 <= m, n <= 25
board[i][j] 是 0 或 1

进阶：

你能否用原地算法解决这个问题？记住棋盘需要同时更新：你不能先更新某些细胞，然后使用它们的更新值去更新其他细胞。
在这个问题中，我们使用 2D 数组来表示棋盘。原则上，棋盘是无限的，这会在活跃区域接近数组边界时引起问题（即活细胞到达边界）。你将如何解决这些问题？

解题思路

这是一道经典的数组模拟题，核心挑战在于需要同时更新所有细胞的状态。

核心思路：

由于需要同时更新所有细胞，我们不能在遍历过程中直接修改数组值，否则会影响后续细胞状态的判断。有两种主要解决方案：

额外空间法：创建一个新数组存储下一代状态，最后复制回原数组
原地更新法：使用状态编码，用额外的位来记录下一代状态

推荐解法：原地更新法

我们可以使用状态编码来实现原地更新：

0: 死细胞 → 死细胞
1: 活细胞 → 活细胞
2: 活细胞 → 死细胞
3: 死细胞 → 活细胞

这样在统计邻居时，我们用 board[i][j] % 2 来获取当前状态，同时可以用新的编码值记录下一代状态。

算法步骤：

遍历每个细胞，统计其活邻居数量
根据游戏规则确定下一代状态，用编码值记录
最后遍历数组，将编码值转换为最终状态（除以2取整）

时间复杂度O(mn)，空间复杂度O(1)。

代码实现

class Solution {
public:
    void gameOfLife(vector<vector<int>>& board) {
        int m = board.size(), n = board[0].size();
        vector<int> dx = {-1, -1, -1, 0, 0, 1, 1, 1};
        vector<int> dy = {-1, 0, 1, -1, 1, -1, 0, 1};
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int liveCount = 0;
                
                // 统计8个方向的活邻居
                for (int k = 0; k < 8; k++) {
                    int nx = i + dx[k];
                    int ny = j + dy[k];
                    if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
                        liveCount += (board[nx][ny] % 2);
                    }
                }
                
                // 应用游戏规则
                if (board[i][j] == 1) {
                    if (liveCount < 2 || liveCount > 3) {
                        board[i][j] = 2; // 活→死
                    }
                } else {
                    if (liveCount == 3) {
                        board[i][j] = 3; // 死→活
                    }
                }
            }
        }
        
        // 更新为最终状态
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                board[i][j] /= 2;
            }
        }
    }
};

class Solution:
    def gameOfLife(self, board: List[List[int]]) -> None:
        m, n = len(board), len(board[0])
        directions = [(-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1)]
        
        for i in range(m):
            for j in range(n):
                live_count = 0
                
                # 统计8个方向的活邻居
                for dx, dy in directions:
                    nx, ny = i + dx, j + dy
                    if 0 <= nx < m and 0 <= ny < n:
                        live_count += (board[nx][ny] % 2)
                
                # 应用游戏规则
                if board[i][j] == 1:
                    if live_count < 2 or live_count > 3:
                        board[i][j] = 2  # 活→死
                else:
                    if live_count == 3:
                        board[i][j] = 3  # 死→活
        
        # 更新为最终状态
        for i in range(m):
            for j in range(n):
                board[i][j] //= 2

public class Solution {
    public void GameOfLife(int[][] board) {
        int m = board.Length, n = board[0].Length;
        int[][] directions = new int[][] {
            new int[]{-1,-1}, new int[]{-1,0}, new int[]{-1,1},
            new int[]{0,-1}, new int[]{0,1},
            new int[]{1,-1}, new int[]{1,0}, new int[]{1,1}
        };
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int liveCount = 0;
                
                // 统计8个方向的活邻居
                foreach (var dir in directions) {
                    int nx = i + dir[0];
                    int ny = j + dir[1];
                    if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
                        liveCount += (board[nx][ny] % 2);
                    }
                }
                
                // 应用游戏规则
                if (board[i][j] == 1) {
                    if (liveCount < 2 || liveCount > 3) {
                        board[i][j] = 2; // 活→死
                    }
                } else {
                    if (liveCount == 3) {
                        board[i][j] = 3; // 死→活
                    }
                }
            }
        }
        
        // 更新为最终状态
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                board[i][j] /= 2;
            }
        }
    }
}

var gameOfLife = function(board) {
    const m = board.length;
    const n = board[0].length;
    
    const directions = [[-1,-1],[-1,0],[-1,1],[0,-1],[0,1],[1,-1],[1,0],[1,1]];
    
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            let liveNeighbors = 0;
            
            for (let [dx, dy] of directions) {
                const newRow = i + dx;
                const newCol = j + dy;
                
                if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n) {
                    if (board[newRow][newCol] === 1 || board[newRow][newCol] === 2) {
                        liveNeighbors++;
                    }
                }
            }
            
            if (board[i][j] === 1) {
                if (liveNeighbors < 2 || liveNeighbors > 3) {
                    board[i][j] = 2;
                }
            } else {
                if (liveNeighbors === 3) {
                    board[i][j] = 3;
                }
            }
        }
    }
    
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (board[i][j] === 2) {
                board[i][j] = 0;
            } else if (board[i][j] === 3) {
                board[i][j] = 1;
            }
        }
    }
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	复杂度	说明
时间复杂度	O(m×n)	需要遍历每个细胞两次，每次统计邻居需要常数时间
空间复杂度	O(1)	只使用了常数级别的额外空间，实现了原地更新

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目