118 lines
4.5 KiB
JavaScript
118 lines
4.5 KiB
JavaScript
/**
|
||
* https://leetcode.cn/problems/game-of-life/?envType=study-plan-v2&envId=top-interview-150
|
||
* @param {number[][]} board
|
||
* @return {void} Do not return anything, modify board in-place instead.
|
||
*/
|
||
const gameOfLife = function (board) {
|
||
|
||
};
|
||
|
||
/*
|
||
模拟：按照题目要求模拟，遍历所有的细胞，通过细胞周围的8个细胞来判断它下一次更新的状态，细胞的状态由下面的条件决定
|
||
1.细胞是活的，会有三种情况，如果周围活细胞数量小于2，那么这个细胞死亡，如果周围活细胞数量为2个或3个，那么这个细胞维持
|
||
存活状态，如果这个细胞周围的活细胞超过了三个，那么这个细胞死亡.
|
||
2.细胞是死的，如果周围正好有三个活细胞那么就复活这个细胞。
|
||
按照上面的要求我们可以把问题拆分为这样，如果这个细胞是活的 并且周围的活细胞少于两个，或者周围的活细胞大于三个，那么这个细胞死亡；
|
||
如果这个细胞是死的，周围正好有三个活细胞，那么就复活这个细胞
|
||
*/
|
||
function f1(board) {
|
||
const m = board.length - 1;
|
||
const n = board[0].length - 1;
|
||
let lives = 0; // 表示当前细胞周围的活细胞数量
|
||
const updates = []; // 细胞下一次要更新的状态
|
||
|
||
for (let i = 0; i <= m; i++) {
|
||
for (let j = 0; j <= n; j++) {
|
||
// 查看左上角的细胞是否存活
|
||
if (i > 0 && j > 0 && board[i - 1][j - 1] === 1) lives++;
|
||
// 查看上面的细胞是否存活
|
||
if (i > 0 && board[i - 1][j] === 1) lives++;
|
||
// 查看右上角的细胞是否存活
|
||
if (i > 0 && j < n && board[i - 1][j + 1] === 1) lives++;
|
||
// 查看右边的细胞是否存活
|
||
if (j < n && board[i][j + 1] === 1) lives++;
|
||
// 查看右下角的细胞是否存活
|
||
if (i < m && j < n && board[i + 1][j + 1] === 1) lives++;
|
||
// 查看下面的细胞是否存活
|
||
if (i < m && board[i + 1][j] === 1) lives++;
|
||
// 查看左下角的细胞是否存活
|
||
if (i < m && j > 0 && board[i + 1][j - 1] === lives) lives++;
|
||
// 查看左边的细胞是否存活
|
||
if (j > 0 && board[i][j - 1] === 1) lives++;
|
||
|
||
// 如果当前细胞是活的，只要它周围存活的细胞小于二，或者大于三，那么下一次更新的状态是死亡，把更新状态存入更新数组
|
||
if (board[i][j] === 1 && (lives < 2 || lives > 3)) {
|
||
updates.push(0);
|
||
continue;
|
||
}
|
||
|
||
// 如果当前细胞是死的, 只要周围存活的细胞恰好等于3,那么下次更新的状态就是复活，把更新状态存入更新数组
|
||
if (board[i][j] === 0 && lives === 3) {
|
||
updates.push(1);
|
||
continue;
|
||
}
|
||
|
||
// 如果细胞状态无需变化往更新数组插入数据-1,表示无需更新
|
||
updates.push(-1);
|
||
}
|
||
}
|
||
|
||
// 通过updates更新数组来更新整个board
|
||
|
||
let k = 0;
|
||
for (let i = 0; i <= m; i++) {
|
||
for (let j = 0; j <= n; j++) {
|
||
if (updates[k] >= 0) board[i][j] = updates[k];
|
||
k++;
|
||
}
|
||
}
|
||
}
|
||
|
||
/*
|
||
利用次低位来保存下一次更新的状态，省去了updates更新数组的空间
|
||
*/
|
||
function f2(board) {
|
||
const dx = [-1, 0, 1, -1, 1, -1, 0, 1];
|
||
const dy = [-1, -1, -1, 0, 0, 1, 1, 1];
|
||
|
||
for (let i = 0; i < board.length; i++) {
|
||
for (let j = 0; j < board[0].length; j++) {
|
||
let sum = 0;
|
||
|
||
// 计算周围8个邻居的活细胞数
|
||
for (let k = 0; k < 8; k++) {
|
||
const nx = i + dx[k];
|
||
const ny = j + dy[k];
|
||
if (nx >= 0 && nx < board.length && ny >= 0 && ny < board[0].length) {
|
||
sum += (board[nx][ny] & 1); // 累加邻居细胞的最低位（表示当前活或死）
|
||
}
|
||
}
|
||
|
||
// // 根据规则设置细胞的未来状态
|
||
// if (board[i][j] === 1) {
|
||
// // 如果当前细胞是活的
|
||
// if (sum === 2 || sum === 3) {
|
||
// board[i][j] |= 2; // 设次低位为1，表示细胞将在下一轮继续存活
|
||
// }
|
||
// } else {
|
||
// // 如果当前细胞是死的
|
||
// if (sum === 3) {
|
||
// board[i][j] |= 2; // 设次低位为1，表示细胞将在下一轮复活
|
||
// }
|
||
// }
|
||
|
||
// 根据规则设置细胞的未来状态
|
||
if (sum === 3 || (board[i][j] === 1 && (sum === 2 || sum === 3))) {
|
||
board[i][j] |= 2; // 设次低位为1，表示细胞将在下一轮存活或复活
|
||
}
|
||
}
|
||
}
|
||
|
||
// 第二次遍历，更新细胞的状态
|
||
for (let i = 0; i < board.length; i++) {
|
||
for (let j = 0; j < board[i].length; j++) {
|
||
board[i][j] >>= 1; // 右移1位，更新状态为新的细胞状态
|
||
}
|
||
}
|
||
}
|