原文链接: LeetCode 生命游戏,不用新数组的方式
https://leetcode-cn.com/problems/game-of-life/
主要思想是将下一次的状态存储在高位, 因为只需要一个位就能表示生死两种状态
/**
如果活细胞周围八个位置的活细胞数少于两个,则该位置活细胞死亡;
如果活细胞周围八个位置有两个或三个活细胞,则该位置活细胞仍然存活;
如果活细胞周围八个位置有超过三个活细胞,则该位置活细胞死亡;
如果死细胞周围正好有三个活细胞,则该位置死细胞复活;
* @param {number[][]} board
* @return {void} Do not return anything, modify board in-place instead.
*/
var gameOfLife = function (board) {
const path = [
[-1, -1],
[-1, 0],
[-1, 1],
[1, -1],
[1, 0],
[1, 1],
[0, -1],
[0, 1],
];
const pathLength = path.length;
const h = board.length;
if (!h) return;
const w = board[0].length;
let i, j, k, n, v, nx, ny, dx, dy;
for (let i = 0; i < h; i++) {
for (let j = 0; j < w; j++) {
n = 0;
v = board[i][j] & 1;
for (k = 0; k < pathLength; k++) {
dx = path[k][0];
dy = path[k][1];
nx = dx + i;
ny = dy + j;
if (nx < 0 || ny < 0 || nx >= h || ny >= w) {
continue;
}
if (board[nx][ny] & 1) n++;
}
if (v & 1) {
// 活细胞
if (n < 2 || n > 3) {
// 死亡
// board[i][j] = v | 2;
} else if (n <= 3) {
// 存活
board[i][j] = v | 2;
}
} else if ((v & 1) === 0 && n === 3) {
// 死细胞
board[i][j] = v | 2;
}
// console.log("n", { v, i, j, n });
}
}
for (i = 0; i < h; i++) {
for (j = 0; j < w; j++) {
board[i][j] = board[i][j] >> 1;
}
}
// return board;
};
// 输入:board = [[0,1,0],[0,0,1],[1,1,1],[0,0,0]]
// 输出:[[0,0,0],[1,0,1],[0,1,1],[0,1,0]]
// 输入:board = [[1,1],[1,0]]
// 输出:[[1,1],[1,1]]
// console.log(
// gameOfLife([
// [0, 1, 0],
// [0, 0, 1],
// [1, 1, 1],
// [0, 0, 0],
// ])
// );
// console.log(
// gameOfLife([
// [1, 1],
// [1, 0],
// ])
// );