Leetcode 289. 生命游戏

Author: Carissa 🎀

Date: Dec.26 2023 🎄

Link: 289. 生命游戏 - 力扣（LeetCode）

1 题目

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

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

  1. 如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
  2. 如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；
  3. 如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；
  4. 如果死细胞周围正好有三个活细胞，则该位置死细胞复活；

下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的，其中细胞的出生和死亡是同时发生的。给你 m x n 网格面板 board 的当前状态，返回下一个状态。

提示：

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

示例 1：

img

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

img

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

输出： [[1,1],[1,1]]

2 思路

本题用暴力解法非常简单，在刚做时，我一直在思考怎么样可以把前面格子对周围活细胞数的统计直接运用到后面的格子中，但实际上每次统计只需要看周围的8个格子，时间复杂度为 O(1), 陷入了优化误区。

本题的考点在于, 一个位置的新值依赖于其他位置：

​ ==- 我们使用二维数组来表示面板，如何界定边界外的细胞呢==

​ ==- 是否能使用原地算法解决本题==

对于第一个问题，我们认为边界外的细胞均为死细胞，这样不会对边界内细胞统计产生影响。

2.1 原地算法

细胞无非四种状态：

原来活着的仍然活着，原来死的现在仍然死亡，原来活着的死了，原来死亡的活了

后面两种 board 上的值会由(1->0 或 0->1)

那么我们不妨引入新状态来暂存这个变化：

  • 原来活着的死了：1 -> -1

  • 原来死亡的活了：0 -> 2

这样，最后只要再遍历一边 board 做修正即可

在判断时，可以采用 Math.abs(board[r][c]) == 1 判断原来位置上的细胞是否存活

3 复杂度分析

时间复杂度：

​ O(mn)，其中 mmm，nnn 分别为 board 的行数和列数。

空间复杂度：O(∣Σ∣∣T∣)

​ O(1)，除原数组外只需要常数的空间存放若干变量。

4 完整解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public void gameOfLife(int[][] board) {
        int m = board.length, n = board[0].length;
        int[] neighbours = {-1, 0, 1};
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                int live = 0;
                for(int x = 0; x < 3; x++) {
                    for(int y = 0; y < 3; y++) {
                        int r = i + neighbours[x], c = j + neighbours[y];
                        if(r == i && c == j) continue;
                        
                        if((r >= 0 && r < m) && (c >= 0 && c < n) && (Math.abs(board[r][c]) == 1)) live += 1;
                    }
                }
                if(live == 3 && board[i][j] == 0) board[i][j] = 2;
                if((live < 2 || live > 3) && board[i][j] == 1) board[i][j] = -1;
            }
        }
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(board[i][j] == -1) board[i][j] = 0;
                if(board[i][j] == 2) board[i][j] = 1;
            }
        }
        return;
    }
}