解题思路

1.我们用最低位保存当前的状态，1为活，0为死，用倒数第二位保存更新后的状态
2.board[i][j] & 1获取当前的状态
3.board[i][j] >> 1获取下一个状态
4.board[i][j] |= 2表示将倒数第二位置为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
class Solution {
public:
    void gameOfLife(vector<vector<int>>& board) {
        int DX[] = {-1,0,1,-1,1,-1,0,1};
        int DY[] = {1,1,1,0,0,-1,-1,-1};
        int m = board.size(), n = board[0].size();
        for(int i = 0; i < m; ++i)
            for(int j = 0; j < n; ++j)
            {
                int live = 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)    continue;     //判断越界
                    live += board[x][y] & 1;         
                }
                if(live == 3)   board[i][j] |= 2;                           //更新后要想存活只存在两种情况
                else if(live == 2 && board[i][j] == 1)   board[i][j] |= 2;           
            }
        for(int i = 0; i < m; ++i)
            for(int j = 0; j < n; ++j)
                board[i][j] >>= 1;              //更新状态
    }
};