[LeetCode] 289. Game of Life

According to Wikipedia's article: "The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970."

The board is made up of an m x n grid of cells, where each cell has an initial state: live (represented by a 1) or dead (represented by a 0). Each cell interacts with its eight neighbors (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article):

1. Any live cell with fewer than two live neighbors dies as if caused by under-population.
2. Any live cell with two or three live neighbors lives on to the next generation.
3. Any live cell with more than three live neighbors dies, as if by over-population.
4. Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.

The next state is created by applying the above rules simultaneously to every cell in the current state, where births and deaths occur simultaneously. Given the current state of the m x n grid board, return the next state.

Example 1:

Input: board = [[0,1,0],[0,0,1],[1,1,1],[0,0,0]]
Output: [[0,0,0],[1,0,1],[0,1,1],[0,1,0]]

Example 2:

Input: board = [[1,1],[1,0]]
Output: [[1,1],[1,1]]

Constraints:

• m == board.length
• n == board[i].length
• 1 <= m, n <= 25
• board[i][j] is 0 or 1.

Follow up:

• Could you solve it in-place? Remember that the board needs to be updated simultaneously: You cannot update some cells first and then use their updated values to update other cells.
• In this question, we represent the board using a 2D array. In principle, the board is infinite, which would cause problems when the active area encroaches upon the border of the array (i.e., live cells reach the border). How would you address these problems?

生命游戏。

题意是给一个board，上面所有的元素表示细胞，细胞的死或活用0或1表示。并且有如下规则，对于每个细胞周围的八个细胞，

1. 如果小于两个活细胞，则当前细胞死亡；

2. 如果有两个或者三个活细胞，则当前细胞存活；

3. 如果大于三个活细胞，则当前细胞死亡；

4. 如果当前细胞死亡但是周围有三个活细胞，则当前细胞可以复活；

根据如上规则请更新这个board的存活情况。要求是in-place做。

思路没有什么特别的，但是这个题又是数组但是要求不使用额外空间。不用额外空间的题目还有73题。这个题因为要求是in-place做所以在不能创造额外空间的情况下，只能通过一个叫做状态机的东西来记录每个cell的状态改变。这里我再次引用grandyang大神的解释。

状态0： 死细胞转为死细胞

状态1： 活细胞转为活细胞

状态2： 活细胞转为死细胞

状态3： 死细胞转为活细胞

按照这个状态的分布，可以把状态用二进制数标记。遍历input，如果当前坐标是1的话（活细胞，01），看下他的count，如果count是2或3，则+2，变成11。如果当前坐标是0（死细胞，00）但是count是3的话，也+2，变成10。按照这个思路就可以写代码了。需要遍历input两次，第一次需要遍历input的每一个cell，先算出每个cell周围的八个cell有几个是活的，以得出当前cell的存活情况。第二次遍历的时候对每个位置上的数字除以2，如果是状态1和3，第二次遍历的时候依然是1，依然会存活；但是0和2在第二次遍历的时候就会变为0而死亡。

时间O(mn)

空间O(1)

Java实现，34行需要continue是因为那是当前坐标。

class Solution {
    public void gameOfLife(int[][] board) {
        // corner case
        if (board == null || board.length == 0) {
            return;
        }

        // normal case
        int m = board.length;
        int n = board[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int count = helper(board, i, j);
                if (board[i][j] == 1) {
                    if (count == 2 || count == 3) {
                        board[i][j] += 2;
                    }
                } else if (count == 3) {
                    board[i][j] += 2;
                }
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                board[i][j] = board[i][j] >> 1;
            }
        }
    }

    private int helper(int[][] board, int i, int j) {
        int count = 0;
        for (int row = Math.max(0, i - 1); row <= Math.min(i + 1, board.length - 1); row++) {
            for (int col = Math.max(0, j - 1); col <= Math.min(j + 1, board[0].length - 1); col++) {
                if (row == i && col == j) {
                    continue;
                }
                // 这里1,3和1做AND操作的结果都会是1
                if ((board[row][col] & 1) == 1) {
                    count++;
                }
            }
        }
        return count;
    }
}

JavaScript实现

/**
 * @param {number[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
var gameOfLife = function(board) {
    // corner case
    if (board == null || board.length == 0) {
        return;
    }

    // normal case
    let m = board.length;
    let n = board[0].length;
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            let count = helper(board, i, j);
            if (board[i][j] == 1) {
                if (count == 2 || count == 3) {
                    board[i][j] += 2;
                }
            } else if (count == 3) {
                board[i][j] += 2;
            }
        }
    }
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            board[i][j] = board[i][j] >> 1;
        }
    }
};

var helper = function(board, i, j) {
    let count = 0;
    for (
        let row = Math.max(0, i - 1);
        row <= Math.min(i + 1, board.length - 1);
        row++
    ) {
        for (
            let col = Math.max(0, j - 1);
            col <= Math.min(j + 1, board[0].length - 1);
            col++
        ) {
            if (row == i && col == j) {
                continue;
            }
            if ((board[row][col] & 1) == 1) {
                count++;
            }
        }
    }
    return count;
};

相关题目

73. Set Matrix Zeroes

289. Game of Life

LeetCode 题目总结