Leetcode 生命游戏

embedded/2024/11/24 8:08:38/

在这里插入图片描述
以下是上述Java代码的算法思想及其逻辑的中文解释:


算法思想

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

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

    • 通过引入额外的状态值(23)来表示细胞的过渡状态。
    • 避免使用额外的存储空间(如创建新矩阵),提高了空间效率。
  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;}
}

http://www.ppmy.cn/embedded/140070.html

相关文章

springmvc 用了 @RequestMapping 是不是可以不用

springmvc 用了 RequestMapping 是不是可以不用 Controller 关系 RequestMapping 是用来映射请求的&#xff0c;可以注解在类或方法上。当注解在类上时&#xff0c;表示该类中的所有响应请求的方法都是以该地址作为父路径&#xff1b;当注解在方法上时&#xff0c;表示该方法响…

程序地址空间

程序地址空间 研究平台 kernel2.6.3232位平台 程序地址空间 除了栈会向下递减空间大小 程序地址空间更应该叫做进程地址空间或者虚拟地址空间&#xff0c;它是一个系统的概念而不是语言层的概念 特别需要注意的是程序地址空间不是内存&#xff01;&#xff01;&#xff01;…

开源生态发展合作倡议

在信息技术发展的浪潮中&#xff0c;开源已成为全球创新的强劲引擎&#xff0c;深刻影响着各行各业的发展。今天&#xff0c;我们站在新的历史起点上&#xff0c;肩负着推动开源生态发展的重任。在此&#xff0c;开源欧拉&#xff08;openEuler&#xff09;、龙蜥&#xff08;O…

unity使用笔记

Build and Run, Player settings里面的设置或需要修改的内容如下&#xff1a; unityhub license过期解决办法&#xff1a;先登录账号&#xff0c;然后打开项目&#xff0c;跳转选择get free personal license即可使用&#xff0c;总之&#xff0c;要先登录&#xff0c;再弄li…

论文翻译 | RECITATION-AUGMENTED LANGUAGE MODELS

摘要 我们提出了一种新范式&#xff0c;称为RECITation-augmented gEneration&#xff08;RECITE&#xff09;&#xff0c;以帮助大型语言模型&#xff08;LLMs&#xff09;在不从外部语料库检索的情况下生成更准确的事实知识。与在生成输出前检索相关文档的检索增强型语言模型…

库卡机器人维护需要注意哪些事项

库卡机器人维护时需要注意以下关键事项&#xff0c;以确保维护工作的有效性和安全性 安全第一&#xff1a;在进行任何维护操作之前&#xff0c;务必断开机器人的电源&#xff0c;并确认所有能量源&#xff08;如气压、液压等&#xff09;都已关闭。遵守机器人操作手册中的安全…

MySQL数据库-SQLyoung的使用

sql很灵活&#xff0c;先写一个最简单的语句&#xff0c;然后再加过滤条件 1.MySQL安装 找一个详细的安装教程从头装到尾&#xff0c;注意my.ini文件中的路径一定要是自己的路径&#xff01;&#xff01;&#xff01; 2.命令行连接MySQL 3.MySQL三层结构 4.创建数据库 5.查询…

详细描述一下Elasticsearch更新和删除文档的过程?

大家好&#xff0c;我是锋哥。今天分享关于【详细描述一下Elasticsearch更新和删除文档的过程&#xff1f;】面试题。希望对大家有帮助&#xff1b; 详细描述一下Elasticsearch更新和删除文档的过程&#xff1f; 1000道 互联网大厂Java工程师 精选面试题-Java资源分享网 在 E…