289. Game of Life

Calc

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
class Solution {
    private static final int[][] DIRECTIONS = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {-1, -1}, {1, 1}, {-1, 1}, {1, -1}};

    public void gameOfLife(int[][] board) {
        int m = board.length, n = board[0].length;

        int[][] nextBoard = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                nextBoard[i][j] = getLife(board, i, j);
            }
        }

        System.arraycopy(nextBoard, 0, board, 0, m);
    }

    private int getLife(int[][] board, int i, int j) {
        int m = board.length, n = board[0].length;
        int liveCells = 0;

        for (int[] direction : DIRECTIONS) {
            int nextI = i + direction[0];
            int nextJ = j + direction[1];
            if (nextI >= 0 && nextI < m && nextJ >= 0 && nextJ < n && board[nextI][nextJ] == 1) {
                liveCells++;
            }
        }

        if (board[i][j] == 0) {
            return liveCells == 3 ? 1 : 0;
        } else {
            return liveCells == 2 || liveCells == 3 ? 1 : 0;
        }
    }
}

此解法申请了额外空间，空间复杂度为 O(mn)。

Bit

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
38
39
class Solution {
    private static final int[][] DIRECTIONS = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {-1, -1}, {1, 1}, {-1, 1}, {1, -1}};

    public void gameOfLife(int[][] board) {
        int m = board.length, n = board[0].length;

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

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int liveCells = board[i][j] >> 1;
                if ((board[i][j] & 1) == 1) {
                    board[i][j] = liveCells == 2 || liveCells == 3 ? 1 : 0;
                } else {
                    board[i][j] = liveCells == 3 ? 1 : 0;
                }
            }
        }
    }

    private int mixLiveCellCountToBit(int[][] board, int i, int j) {
        int m = board.length, n = board[0].length;
        int liveCells = 0;

        for (int[] direction : DIRECTIONS) {
            int nextI = i + direction[0];
            int nextJ = j + direction[1];
            if (nextI >= 0 && nextI < m && nextJ >= 0 && nextJ < n && (board[nextI][nextJ] & 1) == 1) {
                liveCells++;
            }
        }

        return board[i][j] | (liveCells << 1);
    }
}

单个细胞周围的活细胞数量最高为 8，用二进制表示的话仅需使用三个比特位，我们使用 int 中的三个比特位暂存活细胞数量即可避免额外空间分配。

References

287. Find the Duplicate Number