289.生命游戏

链接：289.生命游戏
难度：Medium
标签：数组、矩阵、模拟
简介：根据 百度百科 ，生命游戏，简称为生命，是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。

题解 1 - javascript

• 编辑时间：2020-04-09
• 执行用时：60ms
• 内存消耗：34MB
• 编程语言：javascript
• 解法介绍：判断周围 8 个位置的活细胞个数进行新数组赋值

/**
 * @param {number[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
var gameOfLife = function (board) {
  function lifeOrDead(arr, now) {
    let result = 0;
    for (let item of arr) if (item === 1) result++;
    if (result === 2) return now;
    else if (result === 3) return 1;
    else return 0;
  }
  const res = [];
  for (let i = 0, len1 = board.length; i < len1; i++) res[i] = [];
  for (let i = 0, len1 = board.length; i < len1; i++) {
    for (let j = 0, len2 = board[i].length; j < len2; j++) {
      const arr = [];
      if (i > 0 && j > 0) arr.push(board[i - 1][j - 1]);
      if (i > 0) arr.push(board[i - 1][j]);
      if (j > 0) arr.push(board[i][j - 1]);
      if (i < len1 - 1 && j < len2 - 1) arr.push(board[i + 1][j + 1]);
      if (i < len1 - 1) arr.push(board[i + 1][j]);
      if (j < len2 - 1) arr.push(board[i][j + 1]);
      if (i < len1 - 1 && j > 0) arr.push(board[i + 1][j - 1]);
      if (j < len2 - 1 && i > 0) arr.push(board[i - 1][j + 1]);
      res[i][j] = lifeOrDead(arr, board[i][j]);
    }
  }
  for (let i = 0, len1 = board.length; i < len1; i++) board[i] = res[i];
};

题解 2 - typescript

• 编辑时间：2021-12-12
• 执行用时：68ms
• 内存消耗：39.4MB
• 编程语言：typescript
• 解法介绍：生成周围有几个活细胞的数组进行赋值。

function getCntArr(board: number[][]) {
  const n = board.length;
  const m = board[0].length;
  const ans = new Array(n).fill(0).map(_ => new Array(m).fill(0));
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
      if (board[i][j] === 0) continue;
      if (i > 0) ans[i - 1][j]++;
      if (i < n - 1) ans[i + 1][j]++;
      if (j > 0) ans[i][j - 1]++;
      if (j < m - 1) ans[i][j + 1]++;
      if (i > 0 && j > 0) ans[i - 1][j - 1]++;
      if (i > 0 && j < m - 1) ans[i - 1][j + 1]++;
      if (i < n - 1 && j > 0) ans[i + 1][j - 1]++;
      if (i < n - 1 && j < m - 1) ans[i + 1][j + 1]++;
    }
  }
  return ans;
}
function gameOfLife(board: number[][]): void {
  const n = board.length;
  const m = board[0].length;
  const cntArr = getCntArr(board);
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
      const cnt = cntArr[i][j];
      const state = board[i][j];
      if (state === 1 && (cnt < 2 || cnt > 3)) board[i][j] = 0;
      else if (state === 0 && cnt === 3) board[i][j] = 1;
    }
  }
}

题解 3 - typescript

• 编辑时间：2021-12-12
• 执行用时：68ms
• 内存消耗：39.6MB
• 编程语言：typescript
• 解法介绍：优化上一题解。

const dirs = [
  [0, 1],
  [0, -1],
  [1, 0],
  [-1, 0],
  [1, 1],
  [-1, -1],
  [1, -1],
  [-1, 1],
];
function getCntArr(board: number[][]) {
  const n = board.length;
  const m = board[0].length;
  const ans = new Array(n).fill(0).map(_ => new Array(m).fill(0));
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
      for (let k = 0; k < 8; k++) {
        const x = i + dirs[k][0];
        const y = j + dirs[k][1];
        if (x < 0 || x >= n || y < 0 || y >= m) continue;
        ans[x][y] += board[i][j];
      }
    }
  }
  return ans;
}
function gameOfLife(board: number[][]): void {
  const n = board.length;
  const m = board[0].length;
  const cntArr = getCntArr(board);
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
      const cnt = cntArr[i][j];
      const state = board[i][j];
      if (state === 1 && (cnt < 2 || cnt > 3)) board[i][j] = 0;
      else if (state === 0 && cnt === 3) board[i][j] = 1;
    }
  }
}