289. Game of Life

Idea

題目要求將生存遊戲 boards 的格點置換為下一個狀態
先不考慮空間複雜度
最直覺的解法是

1. 創建一個儲存下一個狀態的二維陣列 results
2. 遍歷每個格點把下一個狀態存取到 results (要小心處理訪問陣列的上下界)
3. 再遍歷一次將 boards 的格點取代為 results 的格點

時間複雜度為 O( m _ n )
空間複雜度為 O( m _ n )

function gameOfLife(board) {
  const m = board.length,
    n = board[0].length,
    results = Array.from(Array(m), (_) => Array(n))
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      results[i][j] = setStatus(board, i, j, m, n)
    }
  }
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      board[i][j] = results[i][j]
    }
  }
}

function setStatus(board, x, y, m, n) {
  let liveCount = 0
  for (let i = Math.max(0, x - 1); i <= Math.min(m - 1, x + 1); i++) {
    for (let j = Math.max(0, y - 1); j <= Math.min(n - 1, y + 1); j++) {
      if (i !== x || j !== y) liveCount += board[i][j] === 1
    }
  }
  return Number(
    board[x][y] === 1 ? liveCount >= 2 && liveCount <= 3 : liveCount === 3
  )
}

Refactor

因為實際狀態本身很單純只有生存或死亡
可以透過自定義拓展狀態來最佳化空間的利用
我們定義每個格點的假想狀態含有時間變化的意義(變化前 → 變化後)

• status = 1, 生存 → 生存
• status = 2, 死亡 → 生存
• status = 3, 生存 → 死亡
• status = 4, 死亡 → 死亡

有了定義的認知後 想法跟前面的思路大體一致 只需要留意以下兩點

1. 在計算各點的假想狀態時將假想狀態的變化前實際狀態考慮進去
2. 遍歷將全部假想狀態正確轉換回實際狀態

時間複雜度為 O( m * n )
空間複雜度為 O( 1 )

function gameOfLife(board) {
  /*
    status of board definition:
      0 = dead before, dead after.
      1 = alive before, alive after.
      2 = alive before, dead after.
      3 = dead before, alive after.
   */
  const m = board.length,
    n = board[0].length
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      board[i][j] = setStatus(board, i, j, m, n)
    }
  }
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      board[i][j] %= 2
    }
  }
}

function setStatus(board, x, y, m, n) {
  let liveCount = 0
  for (let i = Math.max(0, x - 1); i <= Math.min(m - 1, x + 1); i++) {
    for (let j = Math.max(0, y - 1); j <= Math.min(n - 1, y + 1); j++) {
      if (i !== x || j !== y) {
        if (board[i][j] === 2) liveCount += 1
        else if (board[i][j] === 3) liveCount += 0
        else liveCount += board[i][j]
      }
    }
  }
  if (board[x][y] === 1 && (liveCount < 2 || liveCount > 3)) return 2
  else if (board[x][y] === 0 && liveCount === 3) return 3
  else return board[x][y]
}

tags: Leetcode JavaScript