Leetcode 生命游戏

以下是上述Java代码的算法思想及其逻辑的中文解释：

---

算法思想

这段代码实现了LeetCode第289题“生命游戏”的解决方案。核心思想是：

1. 利用原地修改的方式（in-place）存储下一状态的变化：

   • 通过引入额外的状态值（2 和 3）来表示细胞的过渡状态。
   • 避免使用额外的存储空间（如创建新矩阵），提高了空间效率。

2. 两步处理逻辑：

   • 第一步：根据当前状态和邻居情况标记下一状态（过渡状态）。
   • 第二步：将过渡状态转换为最终状态。

3. 状态定义：

   • 0：死亡细胞，下一状态仍然死亡。
   • 1：存活细胞，下一状态仍然存活。
   • 2：存活细胞，下一状态变为死亡（过渡状态）。
   • 3：死亡细胞，下一状态变为存活（过渡状态）。

---

代码逻辑详解

第一步：遍历每个细胞，计算其活邻居数并标记过渡状态

for (int row = 0; row < rows; row++) {for (int col = 0; col < cols; col++) {int liveNeighbors = countLiveNeighbors(board, row, col);// 规则 1 和 3：存活细胞由于邻居过少(<2)或过多(>3)而死亡if (board[row][col] == 1 && (liveNeighbors < 2 || liveNeighbors > 3)) {board[row][col] = 2; // 标记为死亡}// 规则 4：死亡细胞由于正好有 3 个活邻居而复活if (board[row][col] == 0 && liveNeighbors == 3) {board[row][col] = 3; // 标记为复活}}
}

• 遍历二维数组的每个细胞。
• 调用辅助方法 countLiveNeighbors 来统计当前细胞的活邻居数。
• 根据规则：
  • 如果当前细胞是存活的(1)，但活邻居数少于2或多于3，则变为死亡(2)。
  • 如果当前细胞是死亡的(0)，但活邻居数正好为3，则变为存活(3)。

---

第二步：将过渡状态更新为最终状态

for (int row = 0; row < rows; row++) {for (int col = 0; col < cols; col++) {if (board[row][col] == 2) {board[row][col] = 0; // 过渡状态 2 变为死亡} else if (board[row][col] == 3) {board[row][col] = 1; // 过渡状态 3 变为存活}}
}

• 遍历整个数组，将细胞的过渡状态转化为最终状态：
  • 2 表示的“存活→死亡”变为 0。
  • 3 表示的“死亡→存活”变为 1。

---

辅助方法：统计当前细胞的活邻居数量

private int countLiveNeighbors(int[][] board, int row, int col) {int[] directions = {-1, 0, 1};int liveCount = 0;for (int dr : directions) {for (int dc : directions) {if (dr == 0 && dc == 0) continue; // 跳过当前细胞int newRow = row + dr;int newCol = col + dc;// 判断邻居是否在边界范围内，并检查其是否为活细胞if (newRow >= 0 && newRow < board.length && newCol >= 0 && newCol < board[0].length) {if (board[newRow][newCol] == 1 || board[newRow][newCol] == 2) {liveCount++;}}}}return liveCount;
}

• 通过方向数组 {-1, 0, 1} 遍历当前细胞的8个邻居。
• 检查邻居是否越界，以及是否是活细胞。
• 注意：过渡状态 2 仍然被视为活细胞。

---

复杂度分析

1. 时间复杂度：

   • 遍历矩阵 (O(m \times n))，每个细胞计算8个邻居的活细胞数 (O(1))。
   • 总时间复杂度为 (O(m \times n))。

2. 空间复杂度：

   • 使用原地修改，无需额外存储空间，空间复杂度为 (O(1))。

---

总结

• 该算法通过原地修改矩阵，利用额外的状态值来避免使用额外空间。
• 遵循了题目要求，按规则逐步更新细胞的状态，最终输出下一状态的生命游戏棋盘。

class Solution {public void gameOfLife(int[][] board) {int rows = board.length;int cols = board[0].length;//首先遍历每个细胞,统计其存活邻居数量,并标记过渡状态for(int i = 0; i < rows; i++) {for(int j = 0; j < cols; j++) {int liveneighbors = countLiveNeighbors(board, i, j);if((liveneighbors < 2 || liveneighbors > 3) && board[i][j] == 1) {board[i][j] = 2;}if(countLiveNeighbors(board, i, j) == 3 && board[i][j] == 0) {board[i][j] = 3;}}}//根据标记的过渡状态更新boardfor(int i = 0; i < rows; i++) {for(int j = 0; j < cols; j++) {if(board[i][j] == 2) {board[i][j] = 0;}else if(board[i][j] == 3) {board[i][j] = 1;}}}}private int countLiveNeighbors(int[][] board, int row, int col) {int[] directions = {-1, 0, 1};int livecount = 0;for(int dr : directions) {for(int dc : directions) {if(dr == 0 && dc == 0) continue; //跳过原地int newrow = row + dr;int newcol = col + dc;//判断邻居是否越界或存活if(newrow >= 0 && newrow < board.length && newcol >= 0 && newcol < board[0].length) {if(board[newrow][newcol] == 1 || board[newrow][newcol] == 2) {livecount++;}}}}return livecount;}
}