★ FEATURED ARTICLE 1. 项目概述生命游戏Game of Life是英国数学家约翰·康威在1970年发明的一款零玩家游戏。它通过简单的规则模拟了细胞群体的演化过程展现了令人着迷的复杂行为。这个题目在LeetCode上被标记为中等难度主要考察对二维数组的操作和状态转换的处理能力。我最近在刷LeetCode时遇到了这个题目发现它非常适合用来练习原地算法in-place algorithm和状态标记技巧。传统的解法往往会使用额外的空间来存储中间状态但这道题要求我们在不复制整个数组的情况下完成状态更新这就需要一些巧妙的处理方式。2. 核心需求解析2.1 题目要求题目给定一个m×n的二维数组board其中每个元素代表一个细胞的状态1表示活细胞0表示死细胞每个细胞的下一个状态由其周围的8个邻居细胞的当前状态决定遵循摩尔邻域规则任何活细胞如果周围活细胞数少于2个则死亡模拟人口稀少任何活细胞如果周围有2个或3个活细胞则继续存活任何活细胞如果周围超过3个活细胞则死亡模拟过度拥挤任何死细胞如果周围正好有3个活细胞则复活模拟繁殖2.2 挑战点这道题的主要难点在于必须原地修改数组不能使用额外的存储空间所有细胞的状态需要同时更新不能逐个更新否则会影响后续判断边界条件的处理边缘和角落的细胞邻居较少3. 解决方案设计3.1 状态标记法为了解决同时更新的问题我们需要一种方法能够在遍历过程中记录细胞的未来状态同时不影响当前轮次的其他细胞判断。这里我们采用状态标记法如果一个细胞要从活变死我们不立即把它设为0而是暂时标记为-1如果一个细胞要从死变活我们不立即把它设为1而是暂时标记为2这样在遍历时我们仍然可以通过绝对值判断细胞的原始状态最后再统一将-1改为0将2改为13.2 算法步骤遍历整个二维数组对每个细胞统计其8个邻居中活细胞的数量注意处理边界根据当前状态和邻居数量决定下一个状态如果需要改变状态使用特殊标记-1或2记录完成第一遍遍历后进行第二遍遍历将所有标记转换为最终状态4. 代码实现详解4.1 核心函数实现void gameOfLife(int** board, int boardSize, int* boardColSize) { if (board NULL || boardSize 0 || boardColSize NULL) return; int rows boardSize; int cols boardColSize[0]; // 定义8个方向的偏移量 int directions[8][2] {{-1,-1}, {-1,0}, {-1,1}, {0,-1}, {0,1}, {1,-1}, {1,0}, {1,1}}; // 第一遍遍历标记状态变化 for (int i 0; i rows; i) { for (int j 0; j cols; j) { int liveNeighbors 0; // 统计活邻居数量 for (int k 0; k 8; k) { int ni i directions[k][0]; int nj j directions[k][1]; if (ni 0 ni rows nj 0 nj cols) { if (abs(board[ni][nj]) 1) { liveNeighbors; } } } // 应用规则 if (board[i][j] 1 (liveNeighbors 2 || liveNeighbors 3)) { board[i][j] -1; // 活细胞将死亡 } if (board[i][j] 0 liveNeighbors 3) { board[i][j] 2; // 死细胞将复活 } } } // 第二遍遍历更新最终状态 for (int i 0; i rows; i) { for (int j 0; j cols; j) { if (board[i][j] -1) { board[i][j] 0; } else if (board[i][j] 2) { board[i][j] 1; } } } }4.2 关键点解析边界处理在检查邻居时需要确保索引不越界ni和nj的检查状态判断使用abs()函数可以统一处理原始活细胞(1)和将死亡的活细胞(-1)方向数组使用8个方向的偏移量数组使代码更简洁避免重复写8个if语句原地修改通过两次遍历实现状态更新空间复杂度为O(1)5. 复杂度分析时间复杂度O(m×n)其中m和n分别是board的行数和列数。我们需要遍历整个数组两次。空间复杂度O(1)除了输入数组外我们只使用了固定大小的额外空间方向数组。6. 测试用例与验证6.1 标准测试用例// 测试用例1振荡器blinker int board1[3][3] { {0,1,0}, {0,1,0}, {0,1,0} }; // 预期结果横向变为纵向 // 测试用例2静态结构block int board2[4][4] { {0,0,0,0}, {0,1,1,0}, {0,1,1,0}, {0,0,0,0} }; // 预期结果保持不变6.2 边界条件测试单细胞板1×1单行板1×n单列板m×1全活板全死板7. 优化与扩展7.1 可能的优化并行计算由于每个细胞的状态更新只依赖于当前状态可以并行处理稀疏矩阵优化对于大部分细胞为死细胞的情况可以只跟踪活细胞位置位运算优化使用位操作来压缩状态存储7.2 扩展思路无限网格实现可以自动扩展的无限网格图形化展示添加可视化界面观察演化过程自定义规则允许用户自定义生存和繁殖的邻居数量条件8. 常见问题与解决8.1 为什么需要两次遍历因为所有细胞的状态需要同时更新。如果一边遍历一边修改后面的细胞判断时会使用已经修改过的状态导致错误。8.2 如何处理网格边缘的细胞边缘细胞只有5个邻居角落只有3个在统计邻居数量时需要检查数组边界避免越界访问。8.3 为什么使用-1和2作为中间状态选择这些值是为了能够通过简单的绝对值判断原始状态与0和1有足够区分度便于最后统一转换9. 实际应用场景生命游戏虽然是一个理论模型但在多个领域有实际应用并行计算研究作为简单的并行计算模型细胞自动机研究复杂系统行为艺术创作生成有趣的图案和动态艺术密码学某些规则可以用于伪随机数生成10. 个人实现心得在实现这个算法时我最初尝试了使用额外数组存储下一状态虽然简单但不符合题目要求。后来想到可以用特殊标记来记录状态变化这种原地修改标记的技巧在很多类似问题中都很有用。调试时遇到的一个典型问题是忘记处理边界条件导致数组越界访问。解决方法是在访问邻居前总是先检查索引是否有效。另一个收获是方向数组的使用技巧它让代码更加简洁避免了重复的索引计算。这种技巧在网格类问题如迷宫、岛屿计数等中也非常实用。
阅读完成 · 觉得有帮助？
