289. Game of Life

这一题因为要同时修改，所以我用了一个数组来记录要不要修改。。嗯就这样：

class Solution(object):
    def gameOfLife(self, board):
        """
        :type board: List[List[int]]
        :rtype: void Do not return anything, modify board in-place instead.
        """
        m = len(board)
        n = len(board[0])
        flag = [[0 for i in range(n)] for j in range(m)]
        for i in range(m):
            for j in range(n):
                if self.check(i,j,board):
                    flag[i][j] = 1
        for i in range(m):
            for j in range(n):
                if flag[i][j] == 1:
                    board[i][j] = 1 - board[i][j]
        
    def check(self, i, j, board):
        
        count = 0
            #up
        if i - 1 >= 0 and board[i-1][j] == 1:
            count +=1
        if i - 1 >= 0 and j - 1 >= 0 and board[i-1][j-1] == 1:
            count += 1
        if i - 1 >= 0 and j + 1 < len(board[0]) and board[i-1][j+1] == 1:
            count += 1
            #down
        if i + 1 < len(board) and board[i+1][j] == 1:
            count += 1
        if i + 1 < len(board) and j - 1 >= 0 and board[i+1][j-1] == 1:
            count += 1
        if i + 1 < len(board) and j + 1 <len(board[0]) and board[i+1][j+1] == 1:
            count += 1
            #left
        if j - 1 >= 0 and board[i][j-1] == 1:
            count += 1
            #right
        if j + 1 < len(board[0]) and board[i][j+1] == 1:
            count += 1
            
        if board[i][j] == 1:
            if count < 2:
                return True
            if count == 2 or count == 3:
                return False
            if count > 3:
                return True
        else:
            if count == 3:
                return True
            else:
                return False

这时看到的答案中一个很奇妙的做法，通过位运算实现的，充分利用了原题目中1bit存储的特点，人家是天才啊，代码：

class Solution(object):
    def gameOfLife(self, board):
        """
        :type board: List[List[int]]
        :rtype: void Do not return anything, modify board in-place instead.
        """
        m = len(board)
        n = len(board[0])
        for i in range(m):
            for j in range(n):
                count = 0
                for k in range(max(i-1, 0), min(i+2, m)):
                    for h in range(max(j-1, 0), min(j+2, n)):
                        count += board[k][h] & 1
                if count == 3 or count - board[i][j] == 3:
                    board[i][j] = board[i][j] | 2
        for i in range(m):
            for j in range(n):
                board[i][j] = int(board[i][j] > 1)