Game of Life

O(1)的空间都好解决，无非两个状态合并一起再解开，关键没办法写出很简洁的代码

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

        m = len(board[0])
        if not m:
            return 

        for i in xrange(n):
            for j in xrange(m):
                board[i][j] = [board[i][j], 0]

        dirs = [[0, 1], [1, 0], [-1, 0], [0, -1], [1, -1], [1, 1], [-1, 1], [-1, -1]]
        for i in xrange(n):
            for j in xrange(m):
                countLive, countDead = 0, 0
                for row, col in dirs:
                    curRow, curCol = i + row, j + col
                    if 0 <= curRow < n and 0 <= curCol < m:
                        if board[curRow][curCol][0]:
                            countLive += 1
                        else:
                            countDead += 1
                if board[i][j][0]:
                    if 2 <= countLive <= 3:
                        board[i][j][1] = 1
                    else:
                        board[i][j][1] = 0
                elif countLive == 3:
                    board[i][j][1] = 1


        for i in xrange(n):
            for j in xrange(m):
                board[i][j] = board[i][j][1]

如果不像上面这么麻烦的修改，我们还可以看到0，1状态只有一个bit位，我们可以再引入一个bit位表示下一个状态，比如2(10)代表当前是死亡，下一轮复活，3(11)代表当前和下一轮都是存活状态，这时我们需要查当前状态与1就行，需要改成下个状态>> 1就行

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

        m = len(board[0])
        if not m:
            return 

        dirs = ((0, 1,), (0, -1,), (1, -1), (1, 0), (1, 1), \
                (-1, -1), (-1, 0), (-1, 1))
        for i in xrange(n):
            for j in xrange(m):
                countOfLive = self.detect(board, i, j, n, m, dirs)
                if board[i][j] and 2 <= countOfLive <= 3:
                    board[i][j] = 3
                elif not board[i][j] and countOfLive == 3:
                    board[i][j] = 2

        for i in xrange(n):
            for j in xrange(m):
                board[i][j] = board[i][j] >> 1

    def detect(self, board, row, col, n, m, dirs):
        result = 0
        for i, j in dirs:
            curRow, curCol = row + i, col + j
            if 0 <= curRow < n and 0 <= curCol < m:    
                if board[curRow][curCol] & 1:
                    result += 1
        return result