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

原文链接: LeetCode 生命游戏,不用新数组的方式

https://leetcode-cn.com/problems/game-of-life/

主要思想是将下一次的状态存储在高位, 因为只需要一个位就能表示生死两种状态

1/**
2如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
3如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；
4如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；
5如果死细胞周围正好有三个活细胞，则该位置死细胞复活；
6 * @param {number[][]} board
7 * @return {void} Do not return anything, modify board in-place instead.
8 */
9var gameOfLife = function (board) {
10  const path = [
11    [-1, -1],
12    [-1, 0],
13    [-1, 1],
14    [1, -1],
15    [1, 0],
16    [1, 1],
17    [0, -1],
18    [0, 1],
19  ];
20  const pathLength = path.length;
21  const h = board.length;
22  if (!h) return;
23  const w = board[0].length;
24  let i, j, k, n, v, nx, ny, dx, dy;
25  for (let i = 0; i < h; i++) {
26    for (let j = 0; j < w; j++) {
27      n = 0;
28      v = board[i][j] & 1;
29      for (k = 0; k < pathLength; k++) {
30        dx = path[k][0];
31        dy = path[k][1];
32        nx = dx + i;
33        ny = dy + j;
34        if (nx < 0 || ny < 0 || nx >= h || ny >= w) {
35          continue;
36        }
37        if (board[nx][ny] & 1) n++;
38      }
39      if (v & 1) {
40        // 活细胞
41        if (n < 2 || n > 3) {
42          // 死亡
43          // board[i][j] = v | 2;
44        } else if (n <= 3) {
45          // 存活
46          board[i][j] = v | 2;
47        }
48      } else if ((v & 1) === 0 && n === 3) {
49        // 死细胞
50        board[i][j] = v | 2;
51      }
52      //   console.log("n", { v, i, j, n });
53    }
54  }
55  for (i = 0; i < h; i++) {
56    for (j = 0; j < w; j++) {
57      board[i][j] = board[i][j] >> 1;
58    }
59  }
60  //   return board;
61};
62
63// 输入：board = [[0,1,0],[0,0,1],[1,1,1],[0,0,0]]
64// 输出：[[0,0,0],[1,0,1],[0,1,1],[0,1,0]]
65
66// 输入：board = [[1,1],[1,0]]
67// 输出：[[1,1],[1,1]]
68
69// console.log(
70//   gameOfLife([
71//     [0, 1, 0],
72//     [0, 0, 1],
73//     [1, 1, 1],
74//     [0, 0, 0],
75//   ])
76// );
77// console.log(
78//   gameOfLife([
79//     [1, 1],
80//     [1, 0],
81//   ])
82// );