LeetCode题解

第289题生命游戏

根据百度百科，生命游戏，简称为生命，是英国数学家约翰·何顿·康威(老爷子前段时间因为新冠肺炎去世，唉，缅怀)在 1970 年发明的细胞自动机。

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

如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；

如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；

如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；

如果死细胞周围正好有三个活细胞，则该位置死细胞复活；

根据当前状态，写一个函数来计算面板上所有细胞的下一个（一次更新后的）状态。下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的，其中细胞的出生和死亡是同时发生的。

示例：

输入：
[
[0,1,0],
[0,0,1],
[1,1,1],
[0,0,0]
]
输出：
[
[0,0,0],
[1,0,1],
[0,1,1],
[0,1,0]
]

原题如上，代码如下：

python版本

class Solution(object):
    def check(self,i,j,board):
        if i == len(board) or i == -1 or j == len(board[0]) or j == -1:
            return 0
        return board[i][j]
    def environment(self,i,j,board):
        return self.check(i-1,j-1,board)+self.check(i-1,j,board)+self.check(i-1,j+1,board)+self.check(i,j-1,board)+self.check(i,j+1,board)+self.check(i+1,j-1,board)+self.check(i+1,j,board)+self.check(i+1,j+1,board)
    def now(self,i,j,k,board):
        if board[i][j] == 1:
            if k == 2 or k== 3:
                return 1
        if board[i][j] == 0 and k == 3:
            return 1
        return 0       
    def gameOfLife(self, board):
        """
        :type board: List[List[int]]
        :rtype: None Do not return anything, modify board in-place instead.
        """
        new = []
        for i in range(len(board)):
            subnew = []
            for j in range(len(board[0])):
                subnew.append(self.now(i,j,self.environment(i,j,board),board))
            new.append(subnew)
        for i in range(len(new)):
            for j in range(len(new[0])):
                board[i][j] = new[i][j]

解析：

这道题的大致思路就是遍历二维数据的每一个元素，查询一下周围的元素状态，看他们符合条件的哪一种，来决定当前元素的变化，值得注意的是：

对于边界元素的处理。
对于改变元素的值是全部元素同时发生，不要出现异步处理的情况。

对于第一个问题，我使用了check函数来检查当前元素是否符合规范，对于不合规范的值我视为0，这是因为在对周围元素处理处理的过程中，元素死为0，活为1，来统计周围元素环境的时候，我可以对周围元素的值进行加和，利用加和值判定条件，这里也是environment函数的工作原理，也就因为当不合规范的值置为0时，才对加和值无影响。

check 函数：

def check(self,i,j,board):
    if i == len(board) or i == -1 or j == len(board[0]) or j == -1:
            return 0
    return board[i][j]

environment函数：(这里写的粗糙了，可以用位移数组来进行优化)

1
2

def environment(self,i,j,board):
    return self.check(i-1,j-1,board)+self.check(i-1,j,board)+self.check(i-1,j+1,board)+self.check(i,j-1,board)+self.check(i,j+1,board)+self.check(i+1,j-1,board)+self.check(i+1,j,board)+self.check(i+1,j+1,board)

最后，关于当前元素的变化规则，我也用了now函数来返回：

def now(self,i,j,k,board):
    if board[i][j] == 1:
        if k == 2 or k== 3:
            return 1
    if board[i][j] == 0 and k == 3:
        return 1
    return 0

在这个算法中的时间复杂度O(mn)，空间复杂度也是O(mn)。

其实可以使空间复杂度为O(1)，那就是使用原数组的内存空间(一个int类型为32位大小，仅仅存储0和1两种状态还有大部分空间没有被用到)，但是要保证其元素的变化是同步进行的，也就是说不会产生异步影响，即当前元素变化导致其他元素对该变化在这次变化中进行变化(有点绕，其实也好理解，就是说，大家状态值要变就一起变，不要我变了，你才变)。

那么这时候可以引进新的状态值，即2和3，自定义2为0 -->1和3为1-->0，对于上一次变化来说碰到2就当作0来处理，碰到3就当作1来处理，最后对于下一次变化，碰到2设置为1，碰到3设置为0。

这个方法极大的减少了当二位数组太大的情况下的内存空间的浪费(PS:我懒得写这个方法的代码了，思路就是上面的思路)