題目描述:給定一個 m×n 的二維矩陣 board,每個格子為 0(死)或 1(活)。根據 Conway's Game of Life 的四條規則,同時(simultaneously)更新所有格子的狀態:(1) 活細胞若鄰居少於 2 個活細胞則死亡;(2) 活細胞若有 2 或 3 個活細胞鄰居則存活;(3) 活細胞若鄰居多於 3 個活細胞則死亡;(4) 死細胞若恰好有 3 個活細胞鄰居則復活。要求在原地(in-place)修改矩陣。
解題思路:難點在於「同時」更新——若直接修改格子,後續格子的鄰居計算會讀到已修改的值,導致結果錯誤。解決方式是利用額外的位元編碼在原值上同時記錄「舊狀態」與「新狀態」:
2(二進位 10):原本死亡(bit0=0),新狀態為活(bit1=1)。3(二進位 11):原本存活(bit0=1),新狀態為死(bit1=1 表示「曾存活」但即將死)。第一輪掃描時,計算每個格子的活鄰居數時只看 cell & 1(取最低位元即原始狀態),再依規則將需要改變的格子標記為 2 或 3。第二輪掃描將每個格子右移一位(cell >> 1)取得最終狀態,恢復為標準的 0/1 值。
時間複雜度:O(mn) — 對矩陣進行兩次完整掃描,每次掃描中每個格子最多檢查 8 個鄰居(常數),整體為 O(mn)。
空間複雜度:O(1) — 所有狀態編碼直接儲存在原矩陣的位元中,不需要額外的輔助矩陣,僅使用常數量的指標與計數器。
1. Define 8 directional offsets for neighbor traversal.
2. First pass — encode next state in-place:
For each cell (i, j):
a. Count live neighbors using (board[ni][nj] & 1) to read original state.
b. If cell is currently alive (board[i][j] & 1 == 1):
- If liveNeighbors == 2 or 3: set board[i][j] = 3 (stays alive, encode 11).
- Else: leave as 1 (alive -> dead, encode 01).
c. If cell is currently dead (board[i][j] & 1 == 0):
- If liveNeighbors == 3: set board[i][j] = 2 (dead -> alive, encode 10).
- Else: leave as 0 (stays dead, encode 00).
3. Second pass — extract final state:
For each cell (i, j): board[i][j] >>= 1 (shift right to get bit1 as new state).方法一:複製矩陣 O(m*n) 空間
建立一份 board 的複本 copy,第一輪根據 copy 中的原始狀態計算每格新狀態,直接寫回 board。邏輯最直觀,但額外使用 O(m*n) 空間。
方法二:位元編碼原地修改 O(1) 空間(本題主要解法) 利用整數的高位元儲存新狀態、低位元保留舊狀態,避免額外空間,需要兩次掃描。空間複雜度 O(1)。
方法三:記錄變動列表 O(k) 空間 第一輪掃描時,將所有需要改變狀態的格子座標記錄到一個列表中(最多 O(mn) 個),第二輪再批次更新這些格子。空間複雜度與需要變動的格子數 k 成正比,最差仍為 O(mn),但在稀疏矩陣情境下可比複製整個矩陣節省空間。