Python solution, easy to understand..


  • 15
    Z

    0,2 are "dead", and "dead->live"
    1,3 are "live", and "live->dead"

    def gameOfLife(self, board):
        m,n = len(board), len(board[0])
        for i in range(m):
            for j in range(n):
                if board[i][j] == 0 or board[i][j] == 2:
                    if self.nnb(board,i,j) == 3:
                        board[i][j] = 2
                else:
                    if self.nnb(board,i,j) < 2 or self.nnb(board,i,j) >3:
                        board[i][j] = 3
        for i in range(m):
            for j in range(n):
                if board[i][j] == 2: board[i][j] = 1
                if board[i][j] == 3: board[i][j] = 0
                
    def nnb(self, board, i, j):
        m,n = len(board), len(board[0])
        count = 0
        if i-1 >= 0 and j-1 >= 0:   count += board[i-1][j-1]%2
        if i-1 >= 0:                count += board[i-1][j]%2
        if i-1 >= 0 and j+1 < n:    count += board[i-1][j+1]%2
        if j-1 >= 0:                count += board[i][j-1]%2
        if j+1 < n:                 count += board[i][j+1]%2
        if i+1 < m and j-1 >= 0:    count += board[i+1][j-1]%2
        if i+1 < m:                 count += board[i+1][j]%2
        if i+1 < m and j+1 < n:     count += board[i+1][j+1]%2
        return count

  • 2
    R

    Thanks a lot your sharing.

    The nnb function may not be necessary. Here is how I did it. It seems list comprehension is quite efficient in python. It takes 40ms and beat 100%

    class Solution(object):
        def gameOfLife(self, board):
            """
            :type board: List[List[int]], int = 0 dead,1 live
            " 2 dead -> live ; 3 live -> dead
            :rtype: void Do not return anything, modify board in-place instead.
            m = len(board)
            n = len(board[0])
            if m == 0 or n == 0:
                return 
            for iM in range(m):
                for iN in range(n):
                    numNeighbor = sum([board[i][j]%2 for i in range(iM-1,iM+2) for j in range(iN-1,iN+2) if 0 <= i < m and 0<= j < n]) - board[iM][iN]
                    if board[iM][iN] == 0 and numNeighbor == 3:
                        board[iM][iN] = 2
                    if board[iM][iN] == 1 and ( numNeighbor < 2 or numNeighbor >  3):
                        board[iM][iN] = 3
            for iM in range(m):
                for iN in range(n):
                    if board[iM][iN] == 2:
                        board[iM][iN] = 1
                    if board[iM][iN] == 3:
                        board[iM][iN] = 0

  • 0
    A

    @zhuyinghua1203 I wish you could explain this solution. Just offering the code doesn't help much.


  • 0
    H

    So this is the solution that use o(n) space but same O(m*n) time?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.