解法一:直接模拟
复制原数组的状态,然后根据规则进行模拟来计算下一步状态。
class Solution {
public void gameOfLife(int[][] board) {
int i, j;
int m = board.length, n = board[0].length;
// 复制原矩阵的状态
int[][] copyBoard = new int[m][n];
for (i = 0; i < m; ++i) {
copyBoard[i] = board[i].clone();
}
// 统计周围活细胞的数量
int count;
int r, c;
int row, col;
for (i = 0; i < m; ++i) {
for (j = 0; j < n; ++j) {
// 统计活细胞数量
count = 0;
for (r = -1; r <= 1; ++r) {
for (c = -1; c <= 1; ++c) {
if ((r | c) == 0) {
continue;
}
row = i + r;
col = j + c;
if ((row < 0) || (row >= m) || (col < 0) || (col >= n)) {
continue;
}
count += copyBoard[row][col];
}
}
// 规则一、二、三
if (copyBoard[i][j] == 1) {
if ((count == 2) || (count == 3)) {
board[i][j] = 1;
} else {
board[i][j] = 0;
}
} else { // 规则四
if (count == 3) {
board[i][j] = 1;
}
}
}
}
}
}
解法二:位运算
用位运算对解法一进行优化,末位存储旧状态,倒数第二位存储新状态,这样就可以原地更新而不需要额外开辟新数组。
class Solution {
public void gameOfLife(int[][] board) {
int i, j;
int m = board.length, n = board[0].length;
// 统计周围活细胞的数量
int count;
int r, c;
int row, col;
// 末位存储旧状态,倒数第二位存储新状态
for (i = 0; i < m; ++i) {
for (j = 0; j < n; ++j) {
// 统计活细胞数量
count = 0;
for (r = -1; r <= 1; ++r) {
for (c = -1; c <= 1; ++c) {
if ((r | c) == 0) {
continue;
}
row = i + r;
col = j + c;
if ((row < 0) || (row >= m) || (col < 0) || (col >= n)) {
continue;
}
count += board[row][col] & 0b1;
}
}
// 规则一、二、三
if ((board[i][j] & 1) == 1) {
if ((count == 2) || (count == 3)) {
// 新状态为1
board[i][j] |= 0b10;
} else {
// 新状态为0
board[i][j] |= 0b00;
}
} else { // 规则四
if (count == 3) {
// 新状态为1
board[i][j] |= 0b10;
}
}
}
}
for (i = 0; i < m; ++i) {
for (j = 0; j < n; ++j) {
board[i][j] >>= 1;
}
}
}
}