【leetcode面试经典150题】38. 生命游戏(C++)

【leetcode面试经典150题】专栏系列将为准备暑期实习生以及秋招的同学们提高在面试时的经典面试算法题的思路和想法。本专栏将以一题多解和精简算法思路为主,题解使用C++语言。(若有使用其他语言的同学也可了解题解思路,本质上语法内容一致)

【题目描述】

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

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

  1. 如果活细胞周围八个位置的活细胞数少于两个,则该位置活细胞死亡;
  2. 如果活细胞周围八个位置有两个或三个活细胞,则该位置活细胞仍然存活;
  3. 如果活细胞周围八个位置有超过三个活细胞,则该位置活细胞死亡;
  4. 如果死细胞周围正好有三个活细胞,则该位置死细胞复活;

下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的,其中细胞的出生和死亡是同时发生的。给你 m x n 网格面板 board 的当前状态,返回下一个状态。

【示例一】

输入: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]]

【示例二】

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

【提示及数据范围】

  • m == board.length
  • n == board[i].length
  • 1 <= m, n <= 25
  • board[i][j] 为 0 或 1

【代码】

// 复制一份原始数组
// 根据复制数组中邻居细胞的状态来更新 board 中的细胞状态。

class Solution {
public:
    void gameOfLife(vector<vector<int>>& board) {
        int neighbors[3] = {0, 1, -1};

        int rows = board.size();
        int cols = board[0].size();

        // 创建复制数组 copyBoard
        vector<vector<int> >copyBoard(rows, vector<int>(cols, 0));

        // 从原数组复制一份到 copyBoard 中
        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < cols; col++) {
                copyBoard[row][col] = board[row][col];
            }
        }

        // 遍历面板每一个格子里的细胞
        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < cols; col++) {

                // 对于每一个细胞统计其八个相邻位置里的活细胞数量
                int liveNeighbors = 0;

                for (int i = 0; i < 3; i++) {
                    for (int j = 0; j < 3; j++) {

                        if (!(neighbors[i] == 0 && neighbors[j] == 0)) {
                            int r = (row + neighbors[i]);
                            int c = (col + neighbors[j]);

                            // 查看相邻的细胞是否是活细胞
                            if ((r < rows && r >= 0) && (c < cols && c >= 0) && (copyBoard[r][c] == 1)) {
                                liveNeighbors += 1;
                            }
                        }
                    }
                }

                // 规则 1 或规则 3      
                if ((copyBoard[row][col] == 1) && (liveNeighbors < 2 || liveNeighbors > 3)) {
                    board[row][col] = 0;
                }
                // 规则 4
                if (copyBoard[row][col] == 0 && liveNeighbors == 3) {
                    board[row][col] = 1;
                }
            }
        }
    }
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/532683.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

蓝桥杯第九届省赛真题代码——彩灯控制器-附详细讲解思路

1. 比赛题目要求 2. 功能实现推荐步骤 首先&#xff0c;添加头文件&#xff0c;搭建最底层的代码&#xff0c;实现基本的流水灯运转与数码管显示rb2的电阻值 然后&#xff0c;进行pwm脉宽调制&#xff0c;实现rb2数值不同&#xff0c;从而灯光亮度不同。并作出数码管的多窗口…

Java GC了解

Jstack找到线程的快照 jvm提供其他命令作用 jps&#xff1a; 虚拟机进程状况工具&#xff0c;类似linux的ps命令 jstat&#xff1a;虚拟机统计信息监视工具&#xff0c;经常看gc情况的会使用到 jinfo: java配置信息工具 jmap&#xff1a; java内存映射工具&#xff0c;dump&am…

别催了!超真实格行5G随身WiFi问答它来了!格行5G随身WiFi靠谱吗? 看完这篇文章你就懂了?

总让我测格行5G随身WiFi&#xff0c;一直催催催。这下别催了&#xff0c;你们要的格行5G随身WiFi真实测评它来了&#xff01;这次着重回答大家最关心&#xff0c;问的最多的几个问题&#xff01; 一、问&#xff1a;格行5G随身WiFi网速怎么样&#xff1f; 答&#xff1a;格行5G…

网络编程套接字(一)

目录 一、源IP和目的IP 二、端口号 三、UDP协议和TCP协议 四、网络字节序 五、socket编程 1、socket 常见接口 2、struct sockaddr结构体 一、源IP和目的IP IP地址是IP协议提供的一种统一的地址格式&#xff0c;它为互联网上的每一个网络和每一台主机分配一个逻辑地址&am…

原子操作和竞争条件

所有系统调用都是以原子操作方式执行的。之所以这么说&#xff0c;是指内核保证了某系统调用中的所有步骤会作为独立操作而一次性加以执行&#xff0c;其间不会为其他进程或线程所中断。原子性是某些操作得以圆满成功的关键所在。特别是它规避了竞争状态&#xff08;race condi…

解决ModuleNotFoundError: No module named ‘exceptions‘

一、问题描述 使用python语言处理docx文档&#xff0c;在安装docx库时出现问题&#xff0c;No module named ‘exceptions‘ 二、解决方法 卸载docx&#xff0c;安装python-docx。 pip uninstall docx pip install python-docx 问题解决&#xff01;

SSRF靶场

SSRF概述 ​ 强制服务器发送一个攻击者的请求 ​ 互联网上的很多web应用提供了从其他服务器&#xff08;也可以是本地)获取数据的功能。使用用户指定的URL&#xff0c;web应用可以获取图片&#xff08;载入图片&#xff09;、文件资源&#xff08;下载或读取)。如下图所示&…

[lesson17]对象的构造(上)

对象的构造(上) 对象的初始化 从程序设计的角度&#xff0c;对象只是变量&#xff0c;因此&#xff1a; 在栈上常见对象时&#xff0c;成员变量初始为随机值在堆上创建对象时&#xff0c;成员变量初始为随机值在静态存储区创建对象时&#xff0c;成员变量初始为0值 生活中的对…

算法打卡day41|动态规划篇09| Leetcode198.打家劫舍、213.打家劫舍II、337.打家劫舍 III

算法题 Leetcode 198.打家劫舍 题目链接:198.打家劫舍 大佬视频讲解&#xff1a;198.打家劫舍视频讲解 个人思路 偷还是偷&#xff0c;这取决于前一个和前两个房是否被偷了&#xff0c;这种存在依赖关系的题目可以用动态规划解决。 解法 动态规划 动规五部曲&#xff1a;…

生鲜蔬果配送小程序开发攻略

随着互联网的快速发展&#xff0c;电商行业也在不断壮大。生鲜蔬果作为日常生活必需品&#xff0c;在线销售的需求也在不断增加。为了满足这一需求&#xff0c;开发一款生鲜蔬果配送小程序成为了必要的事情。下面就给大家介绍开发这款小程序的攻略。 1. 确定开发需求 首先&…

Java Swing游戏开发学习23

内容来自RyiSnow视频讲解 这一节讲的是Character Status角色状态或属性。 前言 这一节讲的是实现角色状态或属性的显示&#xff0c;就有点像RPG游戏中&#xff0c;人物属性显示的面板&#xff0c;其中有玩家的装备、玩家的等级&#xff0c;各种防御值、闪避值、跑速什么的。…

基于BP神经网络的分类预测模型matlab代码

基于BP神经网络的分类预测模型matlab代码&#xff0c;该数据集下&#xff0c;本模型的表现优异&#xff0c;训练集准确率可达97%&#xff0c;测试集准确率可达93.5%&#xff0c;表现优异。注释十分齐全适合新手学习。 代码获取链接&#xff1a;基于BP神经网络的分类预测模型ma…

SpringBoot3 + uniapp 对接 阿里云0SS 实现上传图片视频到 0SS 以及 0SS 里删除图片视频的操作(最新)

SpringBoot3 uniapp 对接 阿里云0SS 实现上传图片视频到 0SS 以及 0SS 里删除图片视频的操作 最终效果图uniapp 的源码UpLoadFile.vuedeleteOssFile.jshttp.js SpringBoot3 的源码FileUploadController.javaAliOssUtil.java 最终效果图 uniapp 的源码 UpLoadFile.vue <tem…

第十一届蓝桥杯省赛真题(C/C++大学B组)

试题A &#xff1a;门牌制作 #include <bits/stdc.h> using namespace std;const int N 100000; int arr[N];int main() {int ans 0,t;for(int i 1;i < 2020;i){t i;while(t > 0){if(t % 10 2) ans;t / 10;}}cout<<ans<<endl;return 0; } 试题B …

操作系统(第四周 第一堂)

目录 回顾 进程调度&#xff08;process schedule&#xff09; 进程角度 计算机整体——调度队列 队列图 调度程序 总结 回顾 上一篇文章的重点只有一个————进程 对进程的了解包含以下几个方面&#xff1a;1、程序如何变为进程 2、进程在内存中的存储形式 3、进…

Centos7配置秘钥实现集群免密登录

设备&#xff1a;MacBook Pro、多台Centos7.4服务器(已开启sshd服务) 大体流程&#xff1a;本机生成秘钥&#xff0c;将秘钥上传至服务器即可实现免密登录 1、本地电脑生成秘钥&#xff1a; ssh-keygen -t rsa -C "邮箱地址 例&#xff1a;*****.163.com"一路回车…

Bezier曲线的绘制 matlab

式中&#xff1a; 称为基函数。 。 因为n表示次数&#xff0c;点数为n1&#xff0c;显然i表示第i个控制点。 显然在Matlab中可以同矩阵的形式来计算C(u)。 关键代码为&#xff1a; clc clear % 假设控制点P取值为&#xff1a; P [4,7;13,12;19,4;25,12;30,3]; % 因此&a…

Vue2创建过程记录

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 一、搭建node二、安装Vue CLI三、搭建新项目四、Elemet安装&#xff08;参照官网步骤[Element官网](https://element.eleme.cn/#/zh-CN/component/installation)&am…

Hibernate多事务同时调用update(T t) ,字段被覆盖问题

前言 今天现网有个订单卡单了&#xff0c;经过排查发现没有任何异常日志&#xff0c;根据日志定位发现本应该更新的一个状态&#xff0c;也sql肯定执行了(使用了Hibernate的ORM框架)&#xff0c;但是数据库里面的状态没有更新。大概逻辑如下 String hql from orderInfo where…

Could not resolve all files for configuration

关于作者&#xff1a;CSDN内容合伙人、技术专家&#xff0c; 从零开始做日活千万级APP。 专注于分享各领域原创系列文章 &#xff0c;擅长java后端、移动开发、商业变现、人工智能等&#xff0c;希望大家多多支持。 未经允许不得转载 目录 一、导读二、概览三、 推荐阅读 一、导…