当前位置: 首页 > news >正文

289.生命游戏

目录

  • 题目
  • 解法
      • 代码说明:
  • 每一个各自去搜寻他周围的信息,肯定存在冗余,如何优化这个过程?
    • 如何遍历每一个元素的邻域?
    • 方向数组如何表示方向?
  • auto dir : directions这是什么用法
  • board[i][j]一共有几种状态,为什么要设置这么多种,不是0和1代表生存和死亡就行?

题目

根据 百度百科 , 生命游戏 ,简称为 生命 ,是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。

给定一个包含 m × n 个格子的面板,每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态: 1 即为 活细胞 (live),或 0 即为 死细胞 (dead)。每个细胞与其八个相邻位置(水平,垂直,对角线)的细胞都遵循以下四条生存定律:

如果活细胞周围八个位置的活细胞数少于两个,则该位置活细胞死亡;
如果活细胞周围八个位置有两个或三个活细胞,则该位置活细胞仍然存活;
如果活细胞周围八个位置有超过三个活细胞,则该位置活细胞死亡;
如果死细胞周围正好有三个活细胞,则该位置死细胞复活;
下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的,其中细胞的出生和死亡是同时发生的。给你 m x n 网格面板 board 的当前状态,返回下一个状态。
示例 1:

在这里插入图片描述

输入:board = [[0,1,0],[0,0,1],[1,1,1],[0,0,0]]
输出:[[0,0,0],[1,0,1],[0,1,1],[0,1,0]]
示例 2:
在这里插入图片描述

输入:board = [[1,1],[1,0]]
输出:[[1,1],[1,1]]

解法

下面是使用C++实现“生命游戏”的代码,它根据给定的网格状态计算下一个状态:

#include <vector>
using namespace std;class Solution {
public:void gameOfLife(vector<vector<int>>& board) {int m = board.size();int n = board[0].size();// 创建一个方向数组来表示相邻的八个方向vector<vector<int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};// 遍历每个细胞,计算其下一个状态for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {int liveNeighbors = 0;// 统计当前细胞周围的活细胞数for (auto dir : directions) {int ni = i + dir[0];int nj = j + dir[1];if (ni >= 0 && ni < m && nj >= 0 && nj < n && abs(board[ni][nj]) == 1) {liveNeighbors++;}}// 根据规则判断细胞的下一个状态if (board[i][j] == 1 && (liveNeighbors < 2 || liveNeighbors > 3)) {// 如果活细胞的邻居少于2个或多于3个,变成死细胞board[i][j] = -1;  // -1表示活细胞变成死细胞}if (board[i][j] == 0 && liveNeighbors == 3) {// 如果死细胞有正好3个邻居活细胞,复活board[i][j] = 2;  // 2表示死细胞变成活细胞}}}// 更新细胞的状态for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (board[i][j] == -1) {board[i][j] = 0;  // -1变为0(死)} else if (board[i][j] == 2) {board[i][j] = 1;  // 2变为1(活)}}}}
};

代码说明:

  1. 方向数组 directions: 用来表示每个细胞相邻的八个位置。
  2. 邻居活细胞统计: 遍历每个细胞的八个相邻位置,统计活细胞的个数。
  3. 规则判断:
    • 如果是活细胞且邻居活细胞少于2个或多于3个,则标记为死亡(暂时用-1表示)。
    • 如果是死细胞且正好有3个活细胞,则标记为复活(暂时用2表示)。
  4. 状态更新: 将标记的状态(-12)更新回最终的状态(01)。

这个实现可以处理 m x n 大小的任意网格,时间复杂度为 O(m * n),适用于一般规模的输入。

每一个各自去搜寻他周围的信息,肯定存在冗余,如何优化这个过程?

这是进一步的探索,目前实现方法就是遍历每一个。而如何遍历一个元素邻域也是个问题

如何遍历每一个元素的邻域?

 // 创建一个方向数组来表示相邻的八个方向vector<vector<int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};

使用一个方向数组

方向数组如何表示方向?

在生命游戏的实现中,方向数组用来表示一个细胞的周围八个邻居的位置。方向数组中的 01 是通过表示相对的行和列偏移来确定方向的。

方向数组中的 01 解释

假设当前的细胞在网格中的位置是 (i, j),我们可以通过对行 i 和列 j 进行加减操作来确定相邻的八个位置:

  • {0, 1} 表示:行不变(0),列加1(1),即向右移动。
  • {1, 0} 表示:行加1(1),列不变(0),即向下移动。
  • {0, -1} 表示:行不变(0),列减1(-1),即向左移动。
  • {-1, 0} 表示:行减1(-1),列不变(0),即向上移动。

这些偏移可以扩展到斜方向:

  • {1, 1} 表示:行加1(1),列加1(1),即向右下角移动。
  • {1, -1} 表示:行加1(1),列减1(-1),即向左下角移动。
  • {-1, 1} 表示:行减1(-1),列加1(1),即向右上角移动。
  • {-1, -1} 表示:行减1(-1),列减1(-1),即向左上角移动。

在遍历每个细胞时,我们可以根据这些方向数组中的偏移量来检查该细胞周围的邻居。例如,若当前细胞在位置 (i, j),我们可以这样遍历其邻居:

int ni = i + dir[0];
int nj = j + dir[1];

使用行或列的平移操作

auto dir : directions这是什么用法

在 C++ 中,auto 是一种用于自动类型推导的关键字。它可以让编译器根据变量的初始值自动推导出该变量的类型,而不需要显式地声明类型。

在你的例子里,for (auto dir : directions) 使用了范围-based for 循环,auto 让编译器自动推导出 dir 的类型。directions 是一个二维的 vector<vector<int>>,其中每个元素是一个 vector<int>(表示一个方向)。因此,auto dir 实际上被推导为 vector<int> 类型。

详细说明:

for (auto dir : directions)

这个代码的意思是,依次遍历 directions 中的每一个元素,auto 让编译器自动推导出 dir 的类型。由于 directionsvector<vector<int>>,所以每一个 dir 实际上是一个 vector<int>,表示某一个方向(比如 {0, 1},表示向右)。

使用 auto 的优点:

  1. 减少代码冗长:不需要手动写出每个变量的确切类型,编译器可以自动推导。

    • 如果不用 auto,代码可能需要写成:
      for (vector<int> dir : directions)
      
      使用 auto 则更简洁:
      for (auto dir : directions)
      
  2. 防止类型错误:在某些情况下,复杂类型的声明可能容易出错,使用 auto 可以让编译器直接根据上下文推导出正确的类型。

总结:
auto 是 C++11 引入的一种方便的特性,它让编译器根据上下文推导出变量的类型,减少了手动声明类型的繁琐,同时可以提高代码的可读性和可维护性。在你的代码中,auto 推导出的类型是 vector<int>

board[i][j]一共有几种状态,为什么要设置这么多种,不是0和1代表生存和死亡就行?

多种状态的设置,就不需要再创建一个辅助矩阵来存储每个细胞的下一时刻过程。
且对于一个细胞,当前为1正存活,使用-1来表示它的未来状态,但是通过绝对值仍然可以获取当前状态,这是很精妙的地方
四种状态的含义
在这种实现中,board[i][j] 可以有四种状态:

0:当前是死细胞,下一状态也保持为死细胞。
1:当前是活细胞,下一状态也保持为活细胞。
-1:当前是活细胞,但下一状态变为死细胞。
2:当前是死细胞,但下一状态变为活细胞。

abs(board[ni][nj]) == 1

这个绝对值用的太妙了,直接减少了空间复杂度

相关文章:

289.生命游戏

目录 题目解法代码说明&#xff1a; 每一个各自去搜寻他周围的信息&#xff0c;肯定存在冗余&#xff0c;如何优化这个过程&#xff1f;如何遍历每一个元素的邻域&#xff1f;方向数组如何表示方向&#xff1f; auto dir : directions这是什么用法board[i][j]一共有几种状态&am…...

如何保证Redis和数据库的数据一致性

文章目录 0. 前言1. 补充知识&#xff1a;CP和AP2. 什么情况下会出现Redis与数据库数据不一致3. 更新缓存还是删除缓存4. 先操作缓存还是先操作数据库4.1 先操作缓存4.1.1 数据不一致的问题是如何产生的4.1.2 解决方法&#xff08;延迟双删&#xff09;4.1.3 最终一致性和强一致…...

Android Framework AMS(06)startActivity分析-3(补充:onPause和onStop相关流程解读)

该系列文章总纲链接&#xff1a;专题总纲目录 Android Framework 总纲 本章关键点总结 & 说明&#xff1a; 说明&#xff1a;本章节主要解读AMS通过startActivity启动Activity的整个流程的补充&#xff0c;更新了startActivity流程分析部分。 一般来说&#xff0c;有Activ…...

【LangChain系列2】【Model I/O详解】

目录 前言一、LangChain1-1、介绍1-2、LangChain抽象出来的核心模块1-3、特点1-4、langchain解决的一些行业痛点1-5、安装 二、Model I/O模块2-0、Model I/O模块概要2-1、Format&#xff08;Prompts Template&#xff09;2-1-1、Few-shot prompt templates2-1-2、Chat模型的少样…...

动态规划-子数组系列——1567.乘积为正数的最长子数组

1.题目解析 题目来源&#xff1a;1567.乘积为正数的最长子数组——力扣 测试用例 2.算法原理 1.状态表示 因为数组中存在正数与负数&#xff0c;如果求乘积为正数的最长子数组&#xff0c;那么存在两种情况使得乘积为正数&#xff0c;第一种就是正数乘以正数&#xff0c;第…...

Linux 运行执行文件并将日志输出保存到文本文件中

在 Linux 系统中运行可执行文件并将日志输出保存到文本文件中&#xff0c;可以使用以下几种方法&#xff1a; 方法一&#xff1a;使用重定向符号 > 或 >> 覆盖写入&#xff08;>&#xff09;&#xff1a; ./your_executable > logfile.txt这会将可执行文件的输…...

注册安全分析报告:北外网校

前言 由于网站注册入口容易被黑客攻击&#xff0c;存在如下安全问题&#xff1a; 暴力破解密码&#xff0c;造成用户信息泄露短信盗刷的安全问题&#xff0c;影响业务及导致用户投诉带来经济损失&#xff0c;尤其是后付费客户&#xff0c;风险巨大&#xff0c;造成亏损无底洞…...

预警期刊命运逆袭到毕业好刊,仅45天!闭眼冲速度,发文量暴增!

选刊发表不迷路&#xff0c;就找科检易学术 期刊官网&#xff1a;Sustainability | An Open Access Journal from MDPI 1、期刊信息 期刊简介&#xff1a; Sustainability 是一本国际性的、同行评审的开放获取期刊&#xff0c;由MDPI出版社每半月在线出版。该期刊专注于人类…...

【LeetCode每日一题】——523.连续的子数组和

文章目录 一【题目类别】二【题目难度】三【题目编号】四【题目描述】五【题目示例】六【题目提示】七【解题思路】八【时间频度】九【代码实现】十【提交结果】 一【题目类别】 前缀和 二【题目难度】 中等 三【题目编号】 523.连续的子数组和 四【题目描述】 给你一个…...

leetcode54:螺旋矩阵

给你一个 m 行 n 列的矩阵 matrix &#xff0c;请按照 顺时针螺旋顺序 &#xff0c;返回矩阵中的所有元素。 示例 1&#xff1a; 输入&#xff1a;matrix [[1,2,3],[4,5,6],[7,8,9]] 输出&#xff1a;[1,2,3,6,9,8,7,4,5]示例 2&#xff1a; 输入&#xff1a;matrix [[1,2,3,…...

全方面熟悉Maven项目管理工具(三)认识mvn的各类构建命令并创建、打包Web工程

1. POM&#xff08;核心概念&#xff09; 1.1 含义 POM&#xff1a; Project Object Model&#xff0c;项目对象模型。 DOM&#xff1a; Document Object Model&#xff0c;文档对象模型&#xff0c;和 POM 类似 它们都是模型化思想的具体体现 1.2 模型化思想 POM 表示将…...

MySQL中查询语句的执行流程

文章目录 前言流程图概述最后 前言 你好&#xff0c;我是醉墨居士&#xff0c;今天我们一起探讨一下执行一条查询的SQL语句在MySQL内部都发生了什么&#xff0c;让你对MySQL内部的架构具备一个宏观上的了解 流程图 概述 对于查询语句的SQL的执行流程&#xff0c;主要可以分为…...

【代码随想录Day47】单调栈Part02

42. 接雨水 题目链接/文章讲解&#xff1a;代码随想录 视频讲解&#xff1a;单调栈&#xff0c;经典来袭&#xff01;LeetCode:42.接雨水_哔哩哔哩_bilibili 思路概述 问题理解&#xff1a;我们需要计算在给定柱子高度之间可以接住的雨水总量。雨水的量取决于柱子的高度和它们…...

Java全栈经典面试题剖析3】JavaSE面向对象2

目录 面试题2.12 Overload和Override的区别 面试题2.13 Overload方法是否可以改变返回值的类型&#xff1f; 面试题2.14 为什么方法不能根据返回类型来区分重载&#xff1f; 面试题2.15 构造器可不可以被重载或重写&#xff1f; 面试题2.16 在 Java 中定义⼀个不做事且没有…...

@JsonIgnoreProperties做接口对接时使用带来的好处

最近看到有个同事&#xff0c;在代码里面加了JsonIgnoreProperties这个注解&#xff0c;以前还真没有经常去用过&#xff0c;接口对接尤其是跟金蝶、用友等第三方&#xff0c;这个注解在接收数据是非常好用的&#xff1b;接下来带大家一起了解下具体的特性和使用方式 JsonIgno…...

SpringBoot整合mybatisPlus实现批量插入并获取ID

背景&#xff1a;需要实现批量插入并且得到插入后的ID。 使用for循环进行insert这里就不说了&#xff0c;在海量数据下其性能是最慢的。数据量小的情况下&#xff0c;没什么区别。 【1】saveBatch(一万条数据总耗时&#xff1a;2478ms) mybatisplus扩展包提供的&#xff1a;…...

实战RAG第一天——llama_index向量索引,查询引擎,搜索知识库问答,全部代码,保姆级教学

一、llama_index简介 llama_index(以前称为 GPT Index)是一个用于构建、查询、索引大型文档和数据集的开源框架。它的核心功能是帮助开发者将大语言模型(LLM)与自己的数据集无缝集成,从而进行知识库的构建、查询等任务。llama_index 使用 Python 编写,并结合了多种大语言…...

大数据治理

大数据治理是指对大数据的管理和控制,以确保数据的质量、可用性、安全性和合规性。随着大数据技术的不断发展,企业和组织面临着越来越多的数据管理挑战,如数据质量问题、数据安全问题、数据合规问题等。大数据治理成为了企业和组织应对这些挑战的重要手段。 一、大数据治理…...

云计算作业

关闭防火墙 停用Linux 挂载 下载nginx程序 启动nginx程序 连接网卡配置文件并且修改 更改模式为静态手动&#xff0c;并且分别修改ip地址&#xff0c;网关地址&#xff0c;dns 激活 创建自定义文件 定义server模块 监听地址 设置目录 匹配 激活网址根目录 创建目录文…...

复制文件到U盘提示:对于目标文件系统,文件过大

查看U盘属性的文件系统是否为FAT32&#xff0c;需将其改为NTFS 方法一 Win R 输入cmd打开命令行&#xff0c;输入以下命令&#xff08;注&#xff1a;f为U盘盘符&#xff09; convert f: /fs:ntfs /x方法二 格式化U盘&#xff0c;右键点击U盘进行格式化&#xff0c;文件系…...

LeetCode - 394. 字符串解码

题目 394. 字符串解码 - 力扣&#xff08;LeetCode&#xff09; 思路 使用两个栈&#xff1a;一个存储重复次数&#xff0c;一个存储字符串 遍历输入字符串&#xff1a; 数字处理&#xff1a;遇到数字时&#xff0c;累积计算重复次数左括号处理&#xff1a;保存当前状态&a…...

关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案

问题描述&#xff1a;iview使用table 中type: "index",分页之后 &#xff0c;索引还是从1开始&#xff0c;试过绑定后台返回数据的id, 这种方法可行&#xff0c;就是后台返回数据的每个页面id都不完全是按照从1开始的升序&#xff0c;因此百度了下&#xff0c;找到了…...

macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用

文章目录 问题现象问题原因解决办法 问题现象 macOS启动台&#xff08;Launchpad&#xff09;多出来了&#xff1a;Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显&#xff0c;都是Google家的办公全家桶。这些应用并不是通过独立安装的…...

【配置 YOLOX 用于按目录分类的图片数据集】

现在的图标点选越来越多&#xff0c;如何一步解决&#xff0c;采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集&#xff08;每个目录代表一个类别&#xff0c;目录下是该类别的所有图片&#xff09;&#xff0c;你需要进行以下配置步骤&#x…...

unix/linux,sudo,其发展历程详细时间线、由来、历史背景

sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...

AI编程--插件对比分析:CodeRider、GitHub Copilot及其他

AI编程插件对比分析&#xff1a;CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展&#xff0c;AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者&#xff0c;分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...

人工智能(大型语言模型 LLMs)对不同学科的影响以及由此产生的新学习方式

今天是关于AI如何在教学中增强学生的学习体验&#xff0c;我把重要信息标红了。人文学科的价值被低估了 ⬇️ 转型与必要性 人工智能正在深刻地改变教育&#xff0c;这并非炒作&#xff0c;而是已经发生的巨大变革。教育机构和教育者不能忽视它&#xff0c;试图简单地禁止学生使…...

4. TypeScript 类型推断与类型组合

一、类型推断 (一) 什么是类型推断 TypeScript 的类型推断会根据变量、函数返回值、对象和数组的赋值和使用方式&#xff0c;自动确定它们的类型。 这一特性减少了显式类型注解的需要&#xff0c;在保持类型安全的同时简化了代码。通过分析上下文和初始值&#xff0c;TypeSc…...

【前端异常】JavaScript错误处理:分析 Uncaught (in promise) error

在前端开发中&#xff0c;JavaScript 异常是不可避免的。随着现代前端应用越来越多地使用异步操作&#xff08;如 Promise、async/await 等&#xff09;&#xff0c;开发者常常会遇到 Uncaught (in promise) error 错误。这个错误是由于未正确处理 Promise 的拒绝&#xff08;r…...

聚六亚甲基单胍盐酸盐市场深度解析:现状、挑战与机遇

根据 QYResearch 发布的市场报告显示&#xff0c;全球市场规模预计在 2031 年达到 9848 万美元&#xff0c;2025 - 2031 年期间年复合增长率&#xff08;CAGR&#xff09;为 3.7%。在竞争格局上&#xff0c;市场集中度较高&#xff0c;2024 年全球前十强厂商占据约 74.0% 的市场…...