LeetCode 289.生命游戏————2024 春招冲刺百题计划

2024-04-10 01:44

本文主要是介绍LeetCode 289.生命游戏————2024 春招冲刺百题计划,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

根据 百度百科 , 生命游戏 ,简称为 生命 ,是英国数学家约翰·何顿·康威在 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]]
思路
一年多没做人都傻了啊啊啊啊啊
本题主要用
原地算法:基本不占用额外空间,在不改变原本数据附带的信息的条件下,为数据附上新的信息。
答案
好像会比一般的多跑4ms,为什么为什么?

class Solution {
public:void gameOfLife(vector<vector<int>>& board) {//00:死死,01:活死,10:死活,11活活 改变后改变前int n = board.size();int m = board[0].size();int d[8][2] = {{1,0},{0,1},{1,1},{-1,0},{0,-1},{-1,-1},{1,-1},{-1,1}};for(int i = 0; i < n; i ++){for(int j = 0; j < m; j++){int cnt = 0;        	for(int k = 0; k < 8; k++){if((i+d[k][0] >= 0)&&(i+d[k][0] < n)&&(j+d[k][1] >= 0)&&(j+d[k][1] < m)){cnt += board[i+d[k][0]][j+d[k][1]]&1;//只考虑最末位,即上一个状态} }if(board[i][j]) board[i][j] = (cnt == 2||cnt == 3)?3:1;else board[i][j] = cnt == 3?2:0;}}for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){board[i][j] >>= 1;}}}
};

官方答案

class Solution {// 状态用2bit表示,最末位为0表示现在死亡,倒数第二位为0表示下一时刻死亡// 00:死 01:活变死 10:死变活 11:活int rows;int cols;public void gameOfLife(int[][] board) {if (board == null || board[0] == null) {return;}rows = board.length;cols = board[0].length;// 第一轮遍历:计算每个细胞下一时刻状态for (int row = 0; row < rows; row++) {for (int col = 0; col < cols; col++) {int liveNum = getLiveNum(board, row, col);if (board[row][col] == 1) {  // 规则1、2、3,即判断活细胞下一时刻状态board[row][col] += (liveNum == 2 || liveNum == 3) ? 2 : 0;}else {  // 规则4,即判断死细胞下一时刻状态board[row][col] += liveNum == 3 ? 2 : 0;}}}// 第二轮遍历:变更每个细胞的状态for (int row = 0; row < rows; row++) {for (int col = 0; col < cols; col++) {board[row][col] >>= 1;}}}private int getLiveNum(int[][] board, int row, int col) {int liveNum = 0;int[][] posList = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};for (int[] pos : posList) {int x = row + pos[0];int y = col + pos[1];if (x < 0 || x >= rows || y < 0 || y >= cols){continue;}liveNum += board[x][y] & 1;  // 只考虑最末位,即当前状态}return liveNum;}
}

这篇关于LeetCode 289.生命游戏————2024 春招冲刺百题计划的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/889767

相关文章

Linux之计划任务和调度命令at/cron详解

《Linux之计划任务和调度命令at/cron详解》:本文主要介绍Linux之计划任务和调度命令at/cron的使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录linux计划任务和调度命令at/cron一、计划任务二、命令{at}介绍三、命令语法及功能 :at

Linux中的计划任务(crontab)使用方式

《Linux中的计划任务(crontab)使用方式》:本文主要介绍Linux中的计划任务(crontab)使用方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、前言1、linux的起源与发展2、什么是计划任务(crontab)二、crontab基础1、cro

Python基于火山引擎豆包大模型搭建QQ机器人详细教程(2024年最新)

《Python基于火山引擎豆包大模型搭建QQ机器人详细教程(2024年最新)》:本文主要介绍Python基于火山引擎豆包大模型搭建QQ机器人详细的相关资料,包括开通模型、配置APIKEY鉴权和SD... 目录豆包大模型概述开通模型付费安装 SDK 环境配置 API KEY 鉴权Ark 模型接口Prompt

使用Python实现生命之轮Wheel of life效果

《使用Python实现生命之轮Wheeloflife效果》生命之轮Wheeloflife这一概念最初由SuccessMotivation®Institute,Inc.的创始人PaulJ.Meyer... 最近看一个生命之轮的视频,让我们珍惜时间,因为一生是有限的。使用python创建生命倒计时图表,珍惜时间

Oracle数据库执行计划的查看与分析技巧

《Oracle数据库执行计划的查看与分析技巧》在Oracle数据库中,执行计划能够帮助我们深入了解SQL语句在数据库内部的执行细节,进而优化查询性能、提升系统效率,执行计划是Oracle数据库优化器为... 目录一、什么是执行计划二、查看执行计划的方法(一)使用 EXPLAIN PLAN 命令(二)通过 S

Python开发围棋游戏的实例代码(实现全部功能)

《Python开发围棋游戏的实例代码(实现全部功能)》围棋是一种古老而复杂的策略棋类游戏,起源于中国,已有超过2500年的历史,本文介绍了如何用Python开发一个简单的围棋游戏,实例代码涵盖了游戏的... 目录1. 围棋游戏概述1.1 游戏规则1.2 游戏设计思路2. 环境准备3. 创建棋盘3.1 棋盘类

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题

题库来源:安全生产模拟考试一点通公众号小程序 2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题是由安全生产模拟考试一点通提供,流动式起重机司机证模拟考试题库是根据流动式起重机司机最新版教材,流动式起重机司机大纲整理而成(含2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题参考答案和部分工种参考解析),掌握本资料和学校方法,考试容易。流动式起重机司机考试技

【专题】2024飞行汽车技术全景报告合集PDF分享(附原数据表)

原文链接: https://tecdat.cn/?p=37628 6月16日,小鹏汇天旅航者X2在北京大兴国际机场临空经济区完成首飞,这也是小鹏汇天的产品在京津冀地区进行的首次飞行。小鹏汇天方面还表示,公司准备量产,并计划今年四季度开启预售小鹏汇天分体式飞行汽车,探索分体式飞行汽车城际通勤。阅读原文,获取专题报告合集全文,解锁文末271份飞行汽车相关行业研究报告。 据悉,业内人士对飞行汽车行业

高效录音转文字:2024年四大工具精选!

在快节奏的工作生活中,能够快速将录音转换成文字是一项非常实用的能力。特别是在需要记录会议纪要、讲座内容或者是采访素材的时候,一款优秀的在线录音转文字工具能派上大用场。以下推荐几个好用的录音转文字工具! 365在线转文字 直达链接:https://www.pdf365.cn/ 365在线转文字是一款提供在线录音转文字服务的工具,它以其高效、便捷的特点受到用户的青睐。用户无需下载安装任何软件,只