LeetCode 生命游戏,不用新数组的方式

原文链接: 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],
//   ])
// );

评论

暂无评论