打卡力扣题目四

目录

一、题目 

二、解题代码

 三、解题思路

 关于 ARTS 的释义 —— 每周完成一个 ARTS：
● Algorithm: 每周至少做一个 LeetCode 的算法题
● Review: 阅读并点评至少一篇英文技术文章
● Tips: 学习至少一个技术技巧
● Share: 分享一篇有观点和思考的技术文章

希望通过此次活动能聚集一波热爱技术的人，延续好奇、探索、实践、分享的精神。
 

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

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

如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；
如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；
如果死细胞周围正好有三个活细胞，则该位置死细胞复活；
下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的，其中细胞的出生和死亡是同时发生的。给你 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]]

二、解题代码
def gameOfLife(board):
    def getNextBoard(board):
        m, n = len(board), len(board[0])
        nextBoard = [[0] * n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                liveNeighbors = sum([board[x][y] for x in range(max(i-1, 0), min(i+2, m)) for y in range(max(j-1, 0), min(j+2, n))]) - board[i][j]
                if board[i][j] == 1:
                    if liveNeighbors < 2 or liveNeighbors > 3:
                        nextBoard[i][j] = 0
                    else:
                        nextBoard[i][j] = 1
                elif liveNeighbors == 3:
                    nextBoard[i][j] = 1
        return nextBoard
 
    while True:
        newBoard = getNextBoard(board)
        if newBoard == board:
            break
        board = newBoard
    return board

 三、解题思路
这段代码实现了一个名为 `gameOfLife` 的函数，用于解决生命游戏问题。

生命游戏是一种基于细胞自动机的离散模型，它由一个二维矩阵表示，每个元素代表一个细胞，初始状态为 0 或 1。每个细胞的状态根据其周围八个邻居的状态来更新，具体规则如下：

- 如果一个活细胞周围有少于两个活细胞，则该细胞死亡；
- 如果一个活细胞周围有两个或三个活细胞，则该细胞仍然存活；
- 如果一个活细胞周围有超过三个活细胞，则该细胞死亡；
- 如果一个死细胞周围正好有三个活细胞，则该细胞复活。

`gameOfLife` 函数接受一个二维列表 `board` 作为参数，表示当前的生命游戏状态。函数内部定义了一个辅助函数 `getNextBoard`,用于计算下一个生命游戏状态。这个辅助函数首先创建一个新的二维列表 `nextBoard`,用于存储下一个状态。然后遍历当前状态的每一个元素(即每一个细胞),根据上述规则计算出该细胞在下一个状态下的状态，并将其保存到 `nextBoard` 中。最后返回 `nextBoard` 作为结果。

在 `gameOfLife` 函数中，使用了一个 while 循环来不断计算下一个状态，直到下一个状态与当前状态相同为止。这是因为生命游戏是一个迭代过程，每次迭代后状态都会发生变化，因此需要一直进行下去才能得到最终结果。