当前位置：首页 > news >正文

leetcode-289：生命游戏

news 来源：原创 2024/5/13 21:52:15

leetcode-289：生命游戏

题目
解题
- 方法一：
- 方法二：原地替换-位运算

题目

题目连接

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

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

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

下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的，其中细胞的出生和死亡是同时发生的。给你 m x n 网格面板 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]]

解题

方法一：

class Solution {
public:
    vector<vector<int>> dirs={{-1,0},{-1,-1},{0,-1},{1,-1},{1,0},{1,1},{0,1},{-1,1}};
    void gameOfLife(vector<vector<int>>& board) {
        int m=board.size(),n=board[0].size();
        vector<vector<int>> res(m,vector<int>(n));
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                int count=0;
                for(vector<int>& dir:dirs){
                    int x=i+dir[0];
                    int y=j+dir[1];
                    if(x<0||x>=m||y<0||y>=n) continue;
                    count+=board[x][y];
                }
                if(board[i][j]==1){
                    if(count<2||count>3) res[i][j]=0;
                    else res[i][j]=1;
                }else{
                    if(count==3) res[i][j]=1;
                    else res[i][j]=0;
                }
            }
        }
        board=res;
    }
};

方法二：原地替换-位运算

int类型有32位，而原board中，只有 0、1,只占用一个位。因此可以将第2个位，用于存储结果。最后将第2个位刷新成最低位

class Solution {
public:
    vector<vector<int>> dirs={{-1,0},{-1,-1},{0,-1},{1,-1},{1,0},{1,1},{0,1},{-1,1}};
    void gameOfLife(vector<vector<int>>& board) {
        int m=board.size(),n=board[0].size();
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                int count=0;
                for(vector<int>& dir:dirs){
                    int x=i+dir[0];
                    int y=j+dir[1];
                    if(x<0||x>=m||y<0||y>=n) continue;
                    count+=board[x][y]&1;//只累加最低位
                }
                if(board[i][j]==1){
                    if(count<2||count>3) board[i][j]|=0;
                    else board[i][j]|=2;
                }else{
                    if(count==3) board[i][j]|=2;
                    else board[i][j]|=0;
                }
            }
        }
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                board[i][j]>>=1;
            }
        }
    }
};