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

相关文章

哈希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在线转文字是一款提供在线录音转文字服务的工具,它以其高效、便捷的特点受到用户的青睐。用户无需下载安装任何软件,只

2024网安周今日开幕,亚信安全亮相30城

2024年国家网络安全宣传周今天在广州拉开帷幕。今年网安周继续以“网络安全为人民,网络安全靠人民”为主题。2024年国家网络安全宣传周涵盖了1场开幕式、1场高峰论坛、5个重要活动、15场分论坛/座谈会/闭门会、6个主题日活动和网络安全“六进”活动。亚信安全出席2024年国家网络安全宣传周开幕式和主论坛,并将通过线下宣讲、创意科普、成果展示等多种形式,让广大民众看得懂、记得住安全知识,同时还

国产游戏崛起:技术革新与文化自信的双重推动

近年来,国产游戏行业发展迅猛,技术水平和作品质量均得到了显著提升。特别是以《黑神话:悟空》为代表的一系列优秀作品,成功打破了过去中国游戏市场以手游和网游为主的局限,向全球玩家展示了中国在单机游戏领域的实力与潜力。随着中国开发者在画面渲染、物理引擎、AI 技术和服务器架构等方面取得了显著进展,国产游戏正逐步赢得国际市场的认可。然而,面对全球游戏行业的激烈竞争,国产游戏技术依然面临诸多挑战,未来的

2024/9/8 c++ smart

1.通过自己编写的class来实现unique_ptr指针的功能 #include <iostream> using namespace std; template<class T> class unique_ptr { public:         //无参构造函数         unique_ptr();         //有参构造函数         unique_ptr(

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L

leetcode-23Merge k Sorted Lists

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode mergeKLists

论文翻译:arxiv-2024 Benchmark Data Contamination of Large Language Models: A Survey

Benchmark Data Contamination of Large Language Models: A Survey https://arxiv.org/abs/2406.04244 大规模语言模型的基准数据污染:一项综述 文章目录 大规模语言模型的基准数据污染:一项综述摘要1 引言 摘要 大规模语言模型(LLMs),如GPT-4、Claude-3和Gemini的快