题目描述

给定一个包含 m × n 个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态：1 即为活细胞（live），或 0 即为死细胞（dead）。每个细胞与其八个相邻位置（水平，垂直，对角线）的细胞都遵循以下四条生存定律：

如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；
如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；
如果死细胞周围正好有三个活细胞，则该位置死细胞复活；
根据当前状态，写一个函数来计算面板上所有细胞的下一个（一次更新后的）状态。下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的，其中细胞的出生和死亡是同时发生的。

样例

输入： 
[
  [0,1,0],
  [0,0,1],
  [1,1,1],
  [0,0,0]
]
输出：
[
  [0,0,0],
  [1,0,1],
  [0,1,1],
  [0,1,0]
]

算法

(原地算法+位运算)

• 如何做到不用额外的空间，且把所有位置细胞的状态同时改变呢？因为想到只有0和1两个状态，可以用二进制中的第二位来存储变化后的状态。
  • $00$：一开始是死细胞，后来还是死细胞
  • $01$：一开始是活细胞，后来变成死细胞
  • $10$：一开始是死细胞，后来变成活细胞
  • $11$：一开始是活细胞，后来还是活细胞
• 最后把第二位全部右移一位就是结果数组了

时间复杂度：$O(mn)$

时间复杂度：$O(1)$

Java 代码

class Solution {
    private int[] dx = {-1, 0, 1, -1, 1, -1, 0, 1};
    private int[] dy = {-1, -1, -1, 0, 0, 1, 1, 1};
    public void gameOfLife(int[][] board) {
        if(board.length == 0 || board[0].length == 0) return;
        int m = board.length;
        int n = board[0].length;
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                int cnt = 0;//统计活细胞的个数
                for(int k = 0; k < 8; k++){
                    int x = i + dx[k], y = j + dy[k];
                    if(x >= 0 && x < m && y >= 0 && y < n){
                        cnt += board[x][y] & 1;
                    }
                }
                if((board[i][j] & 1) == 1){
                    if(cnt == 2 || cnt == 3){
                        board[i][j] = 0b11;
                    }
                }else if(cnt == 3){
                    board[i][j] = 0b10;
                }
            }
        }

        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                board[i][j] >>= 1;
            }
        }
    }
}