Skip to content

289 game of life

289. Game of Life

题目: https://leetcode.com/problems/game-of-life/

难度 : Medium

直接一上来就没有考虑solve it in-place,考虑的是便利,简直是born for 便利

首先我把board拓宽了,宽,高各增加了两排。

因为这样求neighbor方便,针对原来的borad,现在新的big 对于 1 -> n-1 的部分

全都有八个neighbor,用了一个2d array来记录nbrs,再根据当下的nbr来判断更新,因为不能一边在board上loop一边更新.

AC的效率还ok:

class Solution(object):
    def gameOfLife(self, board):
        """
        :type board: List[List[int]]
        :rtype: void Do not return anything, modify board in-place instead.
        """
        def liveNeighbors(i,j):
            return big[i-1][j-1] + big[i-1][j] + big[i-1][j+1] + big[i][j-1] + big[i][j+1] + big[i+1][j-1] + big[i+1][j] + big[i+1][j+1]

        if board == [[]] : return
        row = len(board)
        col = len(board[0]) 

        nbrs = [[0 for j in range(col)] for i in range(row)]
        big = [[ 0 for j in range(col+2) ] for i in range(row+2)]
        for i in range(1,row+1):
            for j in range(1,col+1):
                big[i][j] = board[i-1][j-1]

        for i in range(1,row+1):
            for j in range(1,col+1):
                nbrs[i-1][j-1] = liveNeighbors(i,j)

        for i in range(row):
            for j in range(col):
                if board[i][j] == 1:                
                    if nbrs[i][j] < 2:
                        board[i][j] = 0
                    elif nbrs[i][j] == 2 or nbrs[i][j] == 3:
                        board[i][j] = 1
                    else:
                        board[i][j] = 0
                else:
                    if nbrs[i][j] == 3:
                        board[i][j] = 1

谷歌了一下,大家都用到了temp 2d array嘛,哼(ˉ(∞)ˉ)唧。好吧,空间复杂度比我小。

很多的解法都是一样开了一个二维数组,即使没有像我一样扩展board.因为问题在于不能一边更新board 一边来做。

看了一下这边的思路:

https://www.hrwhisper.me/leetcode-game-of-life/

http://www.cnblogs.com/grandyang/p/4854466.html

不开数组

我们可以使用状态机转换 o(╯□╰)o 感觉不知道在听什么 还是很迷茫的感觉, in-place AC代码

class Solution(object):
    def gameOfLife(self, board):
        """
        :type board: List[List[int]]
        :rtype: void Do not return anything, modify board in-place instead.
        """
        row = len(board)
        col = len(board[0]) if row else 0

        dx = [-1,-1,-1,0,1,1,1,0]
        dy = [-1,0,1,1,1,0,-1,-1]

        for i in range(row):
            for j in range(col):
                cnt = 0
                for k in range(8):
                    x, y = i + dx[k], j + dy[k]
                    if x >=0 and x < row and y >=0 and y < col and (board[x][y] == 1  or board[x][y] == 2):
                        cnt += 1

                if board[i][j] and (cnt < 2 or cnt > 3):
                    board[i][j] = 2
                elif board[i][j] == 0 and cnt == 3:
                    board[i][j] = 3

        for i in range(row):
            for j in range(col):
                board[i][j] %= 2




回到顶部