Leetcode 生命游戏

devtools/2024/11/25 23:11:48/

在这里插入图片描述
以下是上述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/devtools/136960.html

相关文章

【网络安全设备系列】3、IPS(入侵防御系统)

0x00 定义&#xff1a; 入侵防御系统是一部能够监视网络或网络设备的网络资料传输行为的计算机网络安全设备&#xff0c;能够即时的中断、调整或隔离一些不正常或是具有伤害性的网络资料传输行为。 0x01 产生背景 &#xff1a; 1、串行部署的防火墙可以拦截低层攻击行为&a…

如何在React中服务器操作提交表单后(不)重置表单?

在 React 中使用服务器操作提交表单时&#xff0c;你可能会遇到这样一个问题&#xff1a;如何在服务器操作执行后&#xff08;不&#xff09;重置表单。这取决于你在 React 之上使用的框架&#xff0c;表单可能会自动重置&#xff0c;也可能需要你手动重置。 在 React 中&…

SQLAlchemy,ORM的Python标杆!

嗨&#xff0c;Python的小伙伴们&#xff01;今天咱们来了解 SQLAlchemy&#xff0c;这可是对象关系映射&#xff08;ORM&#xff09;里的超级标杆哦&#xff01;它就像一座神奇的桥梁&#xff0c;能让我们用 Python 代码轻松地和数据库打交道&#xff0c;不用写复杂的 SQL 语句…

HBase 原理

一、HBase系统架构 HBase采用主从架构&#xff0c;主要由以下几个组件组成&#xff1a; Client&#xff1a;客户端&#xff0c;可以是HBase Shell、Java API客户端、Rest API等&#xff0c;提供访问接口&#xff0c;并维护对应的缓存以加速HBase的访问。客户端缓存Region的位…

android 实现答题功能

一、效果 二、实现思路 1、界面实现 实现起来其实不难&#xff0c;首先我们可以看到&#xff0c;界面是由答题进度、题目、选项ABCD组成&#xff0c;现在就是要考虑实现方式&#xff0c;答题进度可以使用Textviewprogressbar实现&#xff0c;题目直接使用Textview&#xff0c;…

鸿蒙开发Hvigor插件动态生成代码

Hvigor允许开发者实现自己的插件&#xff0c;开发者可以定义自己的构建逻辑&#xff0c;并与他人共享。Hvigor主要提供了两种方式来实现插件&#xff1a;基于hvigorfile脚本开发插件、基于typescript项目开发。下面以基于hvigorfile脚本开发插件进行介绍。 基于hvigorfile脚本…

代码随想录算法训练营第五十四天|Day54 图论

冗余连接 https://www.programmercarl.com/kamacoder/0108.%E5%86%97%E4%BD%99%E8%BF%9E%E6%8E%A5.html 思路 #include <stdio.h> #include <stdlib.h>#define MAX_N 1000// 并查集结构体 typedef struct {int parent[MAX_N 1]; // 存储每个节点的父节点int rank…

RHCE——DNS域名解析服务器

1、DNS简介 DNS是互联网上的一项服务&#xff0c;它作为将域名和IP地址相互映射的一个分布式 数据库&#xff0c;能够使人更方便的访问互联网。 &#xff08;1&#xff09;因特网的域名结构 因特网在命名时采用的是层次树状结构的命名方法。任何一个连接在 因特网上的主机或路…