289. 生命游戏

Problem: 289. 生命游戏

思路

用O(1)的额外空间来解决这个问题，关键是利用现有的空间，使用额外的状态标志来标记现在、以前的状态。

如何利用现有的空间？有的题目可以压缩数组状态，本题有点类似于脑筋急转弯，给定的类型是int而原状态只有两个，因此我们可以利用int的空间来额外存储更多的状态。

Code

class Solution {
    public void gameOfLife(int[][] board) {
        // 题目提供的是int类型，而原状态只有01，因此可以多定义几个状态。
        int n = board.length;
        int m = board[0].length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int count = 0;
                for (int p = -1; p < 2; p++) {
                    for (int q = -1; q < 2; q++) {
                        int row = i + p;
                        int col = j + q;
                        if (row >= 0 && row < n && col >= 0 && col < m && !(p == 0 && q == 0) && Math.abs(board[row][col]) == 1) {
                            count++;
                        }
                    }
                }
                if ((count < 2 || count > 3) && board[i][j] == 1) {
                    board[i][j] = -1;
                }
                if (count == 3 && board[i][j] == 0) {
                    board[i][j] = 2;
                }
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {        
                if (board[i][j] == -1) board[i][j] = 0;
                if (board[i][j] == 2) board[i][j] = 1;
            }
        }
    }
}