Game of Life

289. 生命游戏

分析

原地更新（不额外开辟空间）：
- 直接在原矩阵 board 上更新，但在更新过程中要避免影响到邻居细胞的判断
状态编码（利用位运算存储两种状态）：
- 最低位（第 0 位）：当前细胞的状态（0 = 死，1 = 活）
- 次低位（第 1 位）：细胞的下一状态（0 = 死，1 = 活）
计算邻居活细胞数：
- 邻居遍历（避免越界）
  - x ∈ [max(0, i - 1), min(i + 1, n - 1)]
  - y ∈ [max(0, j - 1), min(j + 1, m - 1)]
  - 跳过自己：(x != i || y != j)
- 遍历细胞的八个邻居，board[i][j] & 1 提取当前状态，统计当前活细胞数
按规则更新下一状态：
- 活细胞 → 存活（2~3 个邻居活细胞），否则死亡
- 死细胞 → 恰好 3 个邻居活细胞复活
- board[i][j] |= (next << 1) 将下一状态存入次低位
更新完成后右移一位：
- board[i][j] >>= 1，将下一状态更新为当前状态

时间复杂

总时间复杂度 O(n * m)

空间复杂度

空间复杂度为 O(1)

C++代码

 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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55


class Solution
{
public:
    void gameOfLife(vector<vector<int>>& board)
    {
        int n = board.size(), m = board[0].size();
        if (n == 0 || m == 0)
            return;

        // 遍历每个细胞，计算下一状态
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < m; ++j)
            {
                int live = 0;  // 统计周围活细胞数

                // 遍历周围 8 个方向
                for (int x = max(0, i - 1); x <= min(i + 1, n - 1); ++x)
                {
                    for (int y = max(0, j - 1); y <= min(j + 1, m - 1); ++y)
                    {
                        if ((x != i || y != j) && (board[x][y] & 1))
                            ++live;  // 只看当前状态（最低位）
                    }
                }

                int cur = board[i][j];  // 当前状态
                int next = 0;           // 下一状态

                // 按规则更新下一状态
                if (cur & 1)
                {  // 当前是活细胞
                    if (live == 2 || live == 3)
                        next = 1;  // 继续存活
                    else
                        next = 0;  // 死亡
                }
                else
                {  // 当前是死细胞
                    if (live == 3)
                        next = 1;  // 复活
                    else
                        next = 0;  // 继续死亡
                }

                board[i][j] |= (next << 1);  // 更新下一状态到次低位
            }
        }

        // 右移 1 位，更新到当前状态
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j)
                board[i][j] >>= 1;
    }
};