LeetCode 面试经典 150_矩阵_生命游戏（38_289_C++

LeetCode 面试经典 150_矩阵_生命游戏（38_289_C++_中等）

题目描述：

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

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

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

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

给定当前 board 的状态，更新 board 到下一个状态。

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

输入输出样例：

示例 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

题解：

解题思路：

思路一（暴力破解）：

1、遍历一遍数组，对每个细胞进行判断，使用一个额外数组来存储细胞将要变化的状态，再将额外的数组赋值给原数组。

活细胞 < 2 死亡
活细胞 = 2或3 存活
活细胞 > 3 活细胞死亡
活细胞 = 3 死细胞复活

2、复杂度分析：
① 时间复杂度：O(mn)，其中 m 和 n 分别为 board 的行数和列数,遍历了一遍数组。
② 空间复杂度：O(mn)，为复制数组占用的空间。

思路二（额外状态）：

1、使用额外的状态来记录细胞的变换，这样此细胞状态的转换不会对相邻细胞的状态产生额外的影响。

活->活无需其他状态表示
死->死无需其他状态表示
活->死使用额外状态 -1 表示
死->活使用额外状态 2 表示

之前是活的abs(当前状态)==1

2、复杂度分析
① 时间复杂度：时间复杂度：O(mn)，其中 m 和 n 分别为 board 的行数和列数,遍历了两遍数组。
② 空间复杂度：空间复杂度：O(1)。

代码实现

代码实现（思路一（暴力破解））：

class Solution1 {
public:
    void gameOfLife(vector<vector<int>>& board) {
        // 获取board的行数和列数
        int rowSize = board.size();
        int colSize = board[0].size();

        // 创建一个与board相同的临时二维数组tmp，用于存储下一状态的变化
        vector<vector<int>> tmp(board);

        // 遍历整个board中的每个单元格
        for (int i = 0; i < rowSize; i++) {
            for (int j = 0; j < colSize; j++) {
                // 统计周围8个方向的邻居的活跃状态
                int sum = 0;
                for (int x = -1; x <= 1; x++) {
                    for (int y = -1; y <= 1; y++) {
                        // 跳过当前的单元格
                        if (x == 0 && y == 0) continue;
                        
                        // 计算当前单元格周围的邻居坐标
                        int ni = i + x, nj = j + y;

                        // 如果邻居的坐标在有效范围内，累加该邻居的值（活跃为1，死亡为0）
                        if (ni >= 0 && nj >= 0 && ni < rowSize && nj < colSize) {
                            sum += board[ni][nj];
                        }
                    }
                }

                // 根据生命游戏的规则来决定当前单元格的下一状态
                if (sum > 3 || sum < 2) {
                    // 如果邻居活跃细胞数小于2或者大于3，当前细胞死亡
                    tmp[i][j] = 0;
                } else if (sum == 2) {
                    // 如果邻居活跃细胞数正好为2，当前细胞保持原状态
                    tmp[i][j] = board[i][j];
                } else {
                    // 如果邻居活跃细胞数正好为3，当前细胞复活
                    tmp[i][j] = 1;
                }
            }
        }

        // 将计算得到的新状态赋值回原board
        board = tmp;
    }
};

代码实现（思路二（额外状态））：

class Solution2 {
public:
    void gameOfLife(vector<vector<int>>& board) {
        // 获取board的行数和列数
        int rowSize = board.size();  // 行数
        int colSize = board[0].size();  // 列数

        // 遍历整个board中的每个单元格
        for (int i = 0; i < rowSize; i++) {
            for (int j = 0; j < colSize; j++) {
                // 统计当前细胞周围8个方向的邻居的活跃状态
                int sum = 0;
                for (int x = -1; x <= 1; x++) {
                    for (int y = -1; y <= 1; y++) {
                        // 跳过当前的单元格
                        if (x == 0 && y == 0) continue;
                        
                        // 计算当前单元格周围邻居的坐标
                        int ni = i + x, nj = j + y;

                        // 如果邻居的坐标在有效范围内，并且邻居是活跃的细胞（board值为1或-1）
                        // 使用abs(board[ni][nj]) == 1，确保计算过程中也考虑死亡细胞的中间状态（-1）
                        if (ni >= 0 && nj >= 0 && ni < rowSize && nj < colSize && abs(board[ni][nj]) == 1) {
                            sum += 1;  // 累加活跃的邻居细胞数
                        }
                    }
                }

                // 根据生命游戏的规则更新当前细胞的状态：
                
                // 1. 活细胞变为死亡（如果活细胞邻居数小于2或大于3）
                if (board[i][j] == 1 && (sum > 3 || sum < 2)) {
                    board[i][j] = -1;  // 标记为-1，表示临时死细胞
                } 
                
                // 2. 死细胞复活（如果死细胞邻居数正好为3）
                else if (sum == 3 && board[i][j] == 0) {
                    board[i][j] = 2;  // 标记为2，表示临时复活细胞
                } 
            }
        }

        // 遍历board并更新每个细胞的最终状态：
        for (int i = 0; i < rowSize; i++) {
            for (int j = 0; j < colSize; j++) {
                // -1表示当前细胞应死亡，更新为0
                if (board[i][j] == -1) board[i][j] = 0;
                
                // 2表示当前细胞应复活，更新为1
                if (board[i][j] == 2) board[i][j] = 1;
            }
        }
    }
};

以思路二为例进行调试

#include<iostream>
#include<vector>
using namespace std;

class Solution2 {
public:
    void gameOfLife(vector<vector<int>>& board) {
        // 获取board的行数和列数
        int rowSize = board.size();  // 行数
        int colSize = board[0].size();  // 列数

        // 遍历整个board中的每个单元格
        for (int i = 0; i < rowSize; i++) {
            for (int j = 0; j < colSize; j++) {
                // 统计当前细胞周围8个方向的邻居的活跃状态
                int sum = 0;
                for (int x = -1; x <= 1; x++) {
                    for (int y = -1; y <= 1; y++) {
                        // 跳过当前的单元格
                        if (x == 0 && y == 0) continue;
                        
                        // 计算当前单元格周围邻居的坐标
                        int ni = i + x, nj = j + y;

                        // 如果邻居的坐标在有效范围内，并且邻居是活跃的细胞（board值为1或-1）
                        // 使用abs(board[ni][nj]) == 1，确保计算过程中也考虑死亡细胞的中间状态（-1）
                        if (ni >= 0 && nj >= 0 && ni < rowSize && nj < colSize && abs(board[ni][nj]) == 1) {
                            sum += 1;  // 累加活跃的邻居细胞数
                        }
                    }
                }

                // 根据生命游戏的规则更新当前细胞的状态：
                
                // 1. 活细胞变为死亡（如果活细胞邻居数小于2或大于3）
                if (board[i][j] == 1 && (sum > 3 || sum < 2)) {
                    board[i][j] = -1;  // 标记为-1，表示临时死细胞
                } 
                
                // 2. 死细胞复活（如果死细胞邻居数正好为3）
                else if (sum == 3 && board[i][j] == 0) {
                    board[i][j] = 2;  // 标记为2，表示临时复活细胞
                } 
            }
        }

        // 遍历board并更新每个细胞的最终状态：
        for (int i = 0; i < rowSize; i++) {
            for (int j = 0; j < colSize; j++) {
                // -1表示当前细胞应死亡，更新为0
                if (board[i][j] == -1) board[i][j] = 0;
                
                // 2表示当前细胞应复活，更新为1
                if (board[i][j] == 2) board[i][j] = 1;
            }
        }
    }
};

int main(int argc, char const *argv[])
{
    vector<vector<int>> board={{0,1,0},{0,0,1},{1,1,1},{0,0,0}};
    Solution2 s;
    s.gameOfLife(board);
    for (int i = 0; i < board.size(); i++){
        for (int j = 0; j < board[0].size(); j++){
            cout<<board[i][j]<<" ";
        }
        cout<<endl;
    }
    
    return 0;
}

LeetCode 面试经典 150_矩阵_生命游戏（38_289)原题链接
欢迎大家和我沟通交流(✿◠‿◠)

LeetCode 面试经典 150_矩阵_生命游戏（38_289_C++_中等）(额外状态)