289.md

289. Game of Life

Leetcode link

解题思路

本题非常有意思，我特别去找了一下还有对应的游戏，可以迭代出很多有意思的图案，感兴趣的同学可以玩玩看😆

本题的难点在于如何在不构造另一个数组的情况下“同步”改变细胞的状态。

突破点在于构造出包含上一代信息的“伪状态”，考虑到题目给出的 int 数组只用了 1 个 bit，我们约定有如下的状态：

第 0 位表示当前的状态，第1位表示下一代的状态（注意这里是 bits）

• 00: 现在是死的，下一代还是死的
• 01: 现在是活的，下一代死了
• 10: 现在是死的，下一代活了
• 11: 现在是活的，下一代还是活的

接下来我们就遍历数组，把元素与 1 相与 & 就可以得到当前状态，把元素跟 2 相或 | 就可以记录下一代的状态（如果下一代死了就不用管，因为本来就是 0）

最后记得把所有元素右移 >> 一位就能得到下一代的状态了

C++

class Solution {
 public:
  // 计算当前活着的邻居
  int countLifeNeighbor(vector<vector<int>>& board, int row, int col) {
    int count = 0;
    // ↖️
    count += (row == 0 || col == 0) ? 0 : board[row - 1][col - 1] & 1;
    // ⬆️
    count += (row == 0) ? 0 : board[row - 1][col] & 1;
    // ↗️
    count += (row == 0 || col == board[0].size() - 1)
                 ? 0
                 : board[row - 1][col + 1] & 1;
    // ⬅️
    count += (col == 0) ? 0 : board[row][col - 1] & 1;
    // ➡️
    count += (col == board[0].size() - 1) ? 0 : board[row][col + 1] & 1;
    // ↙️
    count +=
        (row == board.size() - 1 || col == 0) ? 0 : board[row + 1][col - 1] & 1;
    // ⬇️
    count += (row == board.size() - 1) ? 0 : board[row + 1][col] & 1;
    // ↘️
    count += (row == board.size() - 1 || col == board[0].size() - 1)
                 ? 0
                 : board[row + 1][col + 1] & 1;

    return count;
  }
  void gameOfLife(vector<vector<int>>& board) {
    for (int row = 0; row < board.size(); row++) {
      for (int col = 0; col < board[0].size(); col++) {
        int liveNeighbor = countLifeNeighbor(board, row, col);
        // 如果本来是死的，并且活的邻居刚好有 3 个，则变成 10
        if (!(board[row][col] & 1) && liveNeighbor == 3) {
          board[row][col] |= 2;
        } else if (board[row][col] & 1) {
          // 本来是活的，且活的邻居刚好是 2 个或者 3 个，则变成 11
          if (liveNeighbor == 2 || liveNeighbor == 3) {
            board[row][col] |= 2;
          }
          // 其余保持原样
        }
      }
    }
    for (int row = 0; row < board.size(); row++) {
      for (int col = 0; col < board[0].size(); col++) {
        // 遍历完一次之后把全体右移一位（把旧状态洗掉）
        board[row][col] >>= 1;
      }
    }
  }
};

Javascript

/**
 * @param {number[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
var gameOfLife = function (board) {
	for (let row = 0; row < board.length; row++) {
		for (let col = 0; col < board[0].length; col++) {
			let liveNeighbor = countLifeNeighbor(board, row, col);
			// 如果本来是死的，并且活的邻居刚好有 3 个，则变成 10
			if (!(board[row][col] & 1) && liveNeighbor === 3) {
				board[row][col] |= 2;
			} else if (board[row][col] & 1) {
				// 本来是活的，且活的邻居刚好是 2 个或者 3 个，则变成 11
				if (liveNeighbor === 2 || liveNeighbor === 3) {
					board[row][col] |= 2;
				}
				// 其余保持原样
			}
		}
	}
	for (let row = 0; row < board.length; row++) {
		for (let col = 0; col < board[0].length; col++) {
			// 遍历完一次之后把全体右移一位（把旧状态洗掉）
			board[row][col] >>= 1;
		}
	}
};

// 计算当前活着的邻居
function countLifeNeighbor(board, row, col) {
	let count = 0;
	// ↖️
	count += row === 0 || col === 0 ? 0 : board[row - 1][col - 1] & 1;
	// ⬆️
	count += row === 0 ? 0 : board[row - 1][col] & 1;
	// ↗️
	count +=
		row === 0 || col === board[0].length - 1 ? 0 : board[row - 1][col + 1] & 1;
	// ⬅️
	count += col === 0 ? 0 : board[row][col - 1] & 1;
	// ➡️
	count += col === board[0].length - 1 ? 0 : board[row][col + 1] & 1;
	// ↙️
	count +=
		row === board.length - 1 || col === 0 ? 0 : board[row + 1][col - 1] & 1;
	// ⬇️
	count += row === board.length - 1 ? 0 : board[row + 1][col] & 1;
	// ↘️
	count +=
		row === board.length - 1 || col === board[0].length - 1
			? 0
			: board[row + 1][col + 1] & 1;

	return count;
}