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;
                }
            }
        }

        //根据标记的过渡状态更新board
        for(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;
    }
}