Leetcode 289.生命游戏
2024-08-30 14:13:46
生命游戏
根据百度百科,生命游戏,简称为生命,是英国数学家约翰·何顿·康威在1970年发明的细胞自动机。
给定一个包含 m × n 个格子的面板,每一个格子都可以看成是一个细胞。每个细胞具有一个初始状态 live(1)即为活细胞, 或 dead(0)即为死细胞。每个细胞与其八个相邻位置(水平,垂直,对角线)的细胞都遵循以下四条生存定律:
- 如果活细胞周围八个位置的活细胞数少于两个,则该位置活细胞死亡;
- 如果活细胞周围八个位置有两个或三个活细胞,则该位置活细胞仍然存活;
- 如果活细胞周围八个位置有超过三个活细胞,则该位置活细胞死亡;
- 如果死细胞周围正好有三个活细胞,则该位置死细胞复活;
根据当前状态,写一个函数来计算面板上细胞的下一个(一次更新后的)状态。下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的,其中细胞的出生和死亡是同时发生的。
示例:
输入:
[
[0,1,0],
[0,0,1],
[1,1,1],
[0,0,0]
]
输出:
[
[0,0,0],
[1,0,1],
[0,1,1],
[0,1,0]
]
进阶:
- 你可以使用原地算法解决本题吗?请注意,面板上所有格子需要同时被更新:你不能先更新某些格子,然后使用它们的更新后的值再更新其他格子。
- 本题中,我们使用二维数组来表示面板。原则上,面板是无限的,但当活细胞侵占了面板边界时会造成问题。你将如何解决这些问题?
于题目中要求所有点的状态需要一次性发生改变,而且不用额外的空间,这是本题的最大难点。
既然需要"就地解决",我们不妨分析一下borad的特性:board上的元素有两种状态,生(1)和死(0)。这两种状态存在了一个int型里面。所以我们可以有效利用除最低位的其它位,去保存更新后的状态,这样就不需要有额外的空间了。
具体而言,我们可以用最低位表示当前状态,次低位表示更新后状态:
- 00(0):表示当前是死,更新后是死;
- 01(1):表示当前是生,更新后是死;
- 10(2):表示当前是死,更新后是生;
- 11(3):表示当前是神,更新后是生。
class Solution {
public void gameOfLife(int[][] board) {
int row=board.length;
if(row<1) return;
int col=board[0].length;
if(col<1) return;
int[][] move={{-1,-1},{0,-1},{1,-1},{-1,0},{1,0},{-1,1},{0,1},{1,1}};
for(int i=0;i<row;i++){
for(int j=0;j<col;j++){
int live=0;
for(int k=0;k<8;k++){
int x=i+move[k][0];
int y=j+move[k][1];
if(x<0||y<0||x>=row||y>=col) continue;
if((board[x][y]&1)==1) ++live;
}
if((board[i][j]&1)==1){
if(live<2||live>3) board[i][j]=1;
else board[i][j]=3;
}else{
if(live==3) board[i][j]=2;
}
}
}
for(int i=0;i<row;i++){
for(int j=0;j<col;j++){
board[i][j]>>=1;
}
}
}
}
最新文章
- 查看外网出口IP &;&; Traceroute
- git - 简易指南
- Spring Autowiring @Qualifier example
- C#IEnumerator.MoveNext 方法 ()
- 【推荐】JavaScript的那些书
- Navicat for MySQL导出表结构脚本的方法
- SQL Server中是否可以准确获取最后一次索引重建的时间?
- Winform 加载datagridview
- multipart/form-data和application/x-www-form-urlencoded区别
- 2019浙大校赛--G--Postman(简单思维题)
- 使用jQuery+huandlebars遍历数组嵌套数组
- 前端错误监控,sentry入门配置详细教程
- Codeforces Round #341 (Div. 2) E - Wet Shark and Blocks
- JSP页面java代码报错:Purgoods cannot be resolved to a type
- python基础学习5----字典
- POWERSHELL 计划任务的创建,收集DC中失败的登录信息并邮件通知
- 查看java进程启动的详细参数和过程
- eclipse热部署配置
- python 修改文件编码方式
- POJ1222 EXTENDED LIGHTS OUT 高斯消元 XOR方程组
热门文章
- 题解报告:zoj 3261 Connections in Galaxy War(离线并查集)
- 18.3.2从Class上获取信息(注解)
- Myisamchk使用
- SonarQube+Svn+Jenkins环境搭建----问题总结
- .net 音频转换 .amr 转 .mp3 (ffmpeg转换法)
- WARN警告:Going to buffer response body of large or unknown size. Using getResponseBodyAsStream instead is recommended
- Android学习笔记(十六) ContentProvider
- java实现汉诺塔算法
- Hadoop分布式集群安装
- (转)Spring4.2.5+Hibernate4.3.11+Struts1.3.8集成方案一