解法一：直接模拟

复制原数组的状态，然后根据规则进行模拟来计算下一步状态。

  1. class Solution {
  2.     public void gameOfLife(int[][] board) {
  3.         int i, j;
  4.         int m = board.length, n = board[0].length;
  5.         // 复制原矩阵的状态
  6.         int[][] copyBoard = new int[m][n];
  7.         for (i = 0; i < m; ++i) {
  8.             copyBoard[i] = board[i].clone();
  9.         }
  10.         // 统计周围活细胞的数量
  11.         int count;
  12.         int r, c;
  13.         int row, col;
  14.         for (i = 0; i < m; ++i) {
  15.             for (j = 0; j < n; ++j) {
  16.                 // 统计活细胞数量
  17.                 count = 0;
  18.                 for (r = -1; r <= 1; ++r) {
  19.                     for (c = -1; c <= 1; ++c) {
  20.                         if ((r | c) == 0) {
  21.                             continue;
  22.                         }
  23.                         row = i + r;
  24.                         col = j + c;
  25.                         if ((row < 0) || (row >= m) || (col < 0) || (col >= n)) {
  26.                             continue;
  27.                         }
  28.                         count += copyBoard[row][col];
  29.                     }
  30.                 }
  31.                 // 规则一、二、三
  32.                 if (copyBoard[i][j] == 1) {
  33.                     if ((count == 2) || (count == 3)) {
  34.                         board[i][j] = 1;
  35.                     } else {
  36.                         board[i][j] = 0;
  37.                     }
  38.                 } else { // 规则四
  39.                     if (count == 3) {
  40.                         board[i][j] = 1;
  41.                     }
  42.                 }
  43.             }
  44.         }
  45.     }
  46. }

解法二：位运算

用位运算对解法一进行优化，末位存储旧状态，倒数第二位存储新状态，这样就可以原地更新而不需要额外开辟新数组。

  1. class Solution {
  2.     public void gameOfLife(int[][] board) {
  3.         int i, j;
  4.         int m = board.length, n = board[0].length;
  5.         // 统计周围活细胞的数量
  6.         int count;
  7.         int r, c;
  8.         int row, col;
  9.         // 末位存储旧状态，倒数第二位存储新状态
  10.         for (i = 0; i < m; ++i) {
  11.             for (j = 0; j < n; ++j) {
  12.                 // 统计活细胞数量
  13.                 count = 0;
  14.                 for (r = -1; r <= 1; ++r) {
  15.                     for (c = -1; c <= 1; ++c) {
  16.                         if ((r | c) == 0) {
  17.                             continue;
  18.                         }
  19.                         row = i + r;
  20.                         col = j + c;
  21.                         if ((row < 0) || (row >= m) || (col < 0) || (col >= n)) {
  22.                             continue;
  23.                         }
  24.                         count += board[row][col] & 0b1;
  25.                     }
  26.                 }
  27.                 // 规则一、二、三
  28.                 if ((board[i][j] & 1) == 1) {
  29.                     if ((count == 2) || (count == 3)) {
  30.                         // 新状态为1
  31.                         board[i][j] |= 0b10;
  32.                     } else {
  33.                         // 新状态为0
  34.                         board[i][j] |= 0b00;
  35.                     }
  36.                 } else { // 规则四
  37.                     if (count == 3) {
  38.                         // 新状态为1
  39.                         board[i][j] |= 0b10;
  40.                     }
  41.                 }
  42.             }
  43.         }
  44.         for (i = 0; i < m; ++i) {
  45.             for (j = 0; j < n; ++j) {
  46.                 board[i][j] >>= 1;
  47.             }
  48.         }
  49.     }
  50. }