Game of Life

解题思路

  1. 最粗暴的解法自然是copy一份数组，赋值到新数组上。

  2. 不过要原地算法的话，自然而然想到需要携带更多信息。

  3. 我的解法是用 -1 代表 0 -> 1；2 代表 1 -> 0.

  4. 在 Discuss 里看到更聪明和简练的解法，通过第二个 bit 来存储变化后的状态，同时在计算周围 8 个的时候把自己也统计进去，利用规则的特殊性来计算变化值，代码如下：

代码


class Solution {
public:
    void gameOfLife(vector<vector<int>>& board) {
        int m = board.size(), n = m ? board[0].size() : 0;
        for (int i=0; i<m; ++i) {
            for (int j=0; j<n; ++j) {
                int count = 0;
                for (int I=max(i-1, 0); I<min(i+2, m); ++I)
                    for (int J=max(j-1, 0); J<min(j+2, n); ++J)
                        count += board[I][J] & 1;
                if (count == 3 || count - board[i][j] == 3)
                    board[i][j] |= 2;
            }
        }
        for (int i=0; i<m; ++i) {
            for (int j=0; j<n; ++j) {
                board[i][j] >>= 1;
            }
        }
    }
};