Problem: 289. 生命游戏

思路

难点在于题目要求根据当前情况直接得出变化后的情况，但程序肯定需要一个个遍历。 考虑四种状态：0-死细胞，1-活细胞，MAX_VALUE-要活的死细胞，MIN_VALUE-要死的活细胞

解题过程

先遍历一个位置的8个方位，判断细胞所处的状态。 再遍历每个位置的状态，转变不稳定状态的细胞。

复杂度

  • 时间复杂度: $ O(n*m) $
  • 空间复杂度: $O(1)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
    public void gameOfLife(int[][] board) {
        int[][] dir = new int[][]{{-1,-1},{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1}};
        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[] d : dir){
                    int ni = d[0] + i;
                    int nj = d[1] + j;
                    if(ni >= 0 && nj >= 0 && ni < m && nj < n) {
                        if(board [ni][nj] == 1 || board [ni][nj] == Integer.MIN_VALUE) {
                            cnt++;
                        }
                    }
                }
                if((cnt < 2 || cnt > 3) && board [i][j] == 1) {
                    board [i][j] = Integer.MIN_VALUE;
                } else if((cnt == 2 || cnt == 3) && board [i][j] == 1) {
                    board [i][j] = 1;
                } else if(cnt == 3 && board [i][j] == 0) {
                    board [i][j] = Integer.MAX_VALUE;
                }
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(board [i][j] == Integer.MIN_VALUE){
                    board [i][j] = 0;
                } else if(board [i][j] == Integer.MAX_VALUE) {
                    board [i][j] = 1;
                }
            }
        }
    }
}