GameOfLife

这道题第一印象是直接开一个额外matrix保存下一时刻状态, 然而要求in place, 这个时候可以在matrix的value上做文章. 因为每个细胞有'0' 和 '1' 两种状态, 所以可以用"00" "01" "10" "11" 来表示, 第一个bit代表下一时刻状态, 第二个bit代表当前状态.

public class Solution {
    public void gameOfLife(int[][] board) {
        int m = board.length; int n = board[0].length;
        int[] dx = {-1, -1, -1, 0, 1, 1, 1, 0};
        int[] dy = {-1, 0, 1, 1, 1, 0, -1, -1};
        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]; int y = j + dy[k];
                    if(x>=0 && x<m && y>=0 && y<n && (board[x][y]&1)==1)
                        cnt++;
                }
                if (board[i][j] ==1 && cnt >= 2 && cnt <= 3) board[i][j] = 3;
                else if (board[i][j] == 0 && cnt == 3) board[i][j] = 2;
            }
        }

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

    }
}