[LeetCode 289] Game of Life (Med

Solution

参考https://leetcode.com/problems/game-of-life/solution/

Solution 1, Space O(M x N)

1. 需要一个copy of board，所有的计算都基于这个unmodified copy of board，然后应用规则，更改board

Solution2，Space O(1)

1. 用不同的两个状态分别表示 曾经是live --> die ，或者 曾经是die --> live，然后最后再根据这两个状态update最终的状态
2. 比如曾经是live --> 现在die，那么此cell表示为-1； 曾经是die --> 现在live，那么此cell表示为2
3. 最后扫描一次board，根据每个cell的值决定最终的状态

Code 1, Space O (M x N)

class Solution {
    public void gameOfLife(int[][] board) {
        if (board == null || board.length == 0 || board[0].length == 0)
            return;
        
        int[][] newBoard = new int[board.length][board[0].length];
        
        for (int row = 0; row < board.length; row ++) {
            for (int col = 0; col < board[0].length; col ++) {
                int currentCell = board[row][col];
                
                int rowStart = row == 0 ? row : row - 1;
                int colStart = col == 0 ? col : col - 1;
                
                int liveCount = 0;
                int dieCount = 0;
                
                int[][] directions = {{-1, -1}, {0, -1}, {1, -1}, {-1, 0}, {1, 0}, {-1, 1}, {0, 1}, {1, 1}};
                
                for (int[] direction : directions) {
                    int x = row + direction[0];
                    int y = col + direction[1];
                    
                    if (x == row && y == col) {
                        continue;
                    } else if (x >= board.length || x < 0 || y >= board[0].length || y < 0) {
                        continue;
                    }
                    
                    if (board[x][y] == 1) {
                        liveCount ++;
                    } else if (board[x][y] == 0) {
                        dieCount ++;
                    }
                }
                
                if (currentCell == 1) {
                    if ((liveCount == 2 || liveCount == 3)) {
                        newBoard[row][col] = 1;
                    }

                    else if (liveCount < 2 || liveCount > 3) {
                        newBoard[row][col] = 0;
                    }

                }

                else if (currentCell == 0) {
                    if ((liveCount == 3))
                        newBoard[row][col] = 1;
                }
                
                
            }
        }
        
       for (int row = 0; row < board.length; row ++) {
            for (int col = 0; col < board[0].length; col ++) {
                board [row][col] = newBoard[row][col];
            }
       }
    }
}