描述
根据百度百科,生命游戏,简称为生命,是英国数学家约翰·何顿·康威在1970年发明的细胞自动机。
给定一个包含 m × n 个格子的面板,每一个格子都可以看成是一个细胞。每个细胞具有一个初始状态 live(1)即为活细胞, 或 dead(0)即为死细胞。每个细胞与其八个相邻位置(水平,垂直,对角线)的细胞都遵循以下四条生存定律:
根据当前状态,写一个函数来计算面板上细胞的下一个(一次更新后的)状态。下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的,其中细胞的出生和死亡是同时发生的。
在线评测地址:领扣题库官网
样例1 [0,1,0], [0,0,1], [1,1,1], [0,0,0] [0,0,0], [1,0,1], [0,1,1], [0,1,0] ]你可以使用原地算法解决本题吗?请注意,面板上所有格子需要同时被更新:你不能先更新某些格子,然后使用它们的更新后的值再更新其他格子。本题中,我们使用二维数组来表示面板。原则上,面板是无限的,但当活细胞侵占了面板边界时会造成问题。你将如何解决这些问题?
解题思路
原地完成更新的方法:
我们用32位整数的最后两位二进制来表示boardi的当前状态以及下一状态,0 表示死细胞,1 表示活细胞。由于初始时board由 0 和 1 构成,所以我们设定最低位的二进制表示当前细胞的状态,倒数第二位二进制表示下一状态,不同的表示对应的结果如下:
对于前两种情况我们不需要做改动,因为给出的board内所有元素的倒数第二位均为0,所以需要修改的为后两种情况:
当死细胞周围正好有 3 个活细胞时,则满足第三种状态,所以需要重新赋值:boardi = 2
当活细胞周围正好有 2 个或者 3 个活细胞时,则满足第四种状态,所以需要重新赋值:boardi = 3
源代码
class Solution: @param board: the given board @return: nothing def gameOfLife(self, board): # Write your code here m = len(board) n = len(board[0]) for i in range(m): for j in range(n): # 计算与board[i][j]相邻的活细胞数量 lives = self.liveNeighbors(board, m, n, i, j); # 如果当前位置为活细胞,且相邻活细胞数量为2个或者3个,则下一状态仍为活细胞 if board[i][j] == 1 and lives = 2 and lives = 3: board[i][j] = 3 # 如果当前位置为死细胞,且相邻活细胞数量为3个,则下一状态为活细胞 if board[i][j] == 0 and lives == 3: board[i][j] = 2 # 更新细胞状态 for i in range(m): for j in range(n): board[i][j] = 1 def liveNeighbors(self, board, m, n, i, j): lives = 0 for x in range(max(i - 1, 0), min(i + 1, m - 1) + 1): for y in range(max(j - 1, 0), min(j + 1, n - 1) + 1): lives += board[x][y] 1 lives -= board[i][j] 1 return lives
更多题解参考:九章官网solution
云计算服务正在以前所未有的速度在各行各业快速普及,成为IT应用的最主流实现形...
前言 语言的内存管理是语言设计的一个重要方面。它是决定语言性能的重要因素。无...
文本作者:刘晓国,Elastic 公司社区布道师。新加坡国立大学硕士,西北工业大学...
场景描述 最近使用 Redis 遇到了一个类似分布式锁的场景,跟 Redis 实现分布式锁...
近期进展 在 ffmpeg-go init 之后,项目也收到了一些关注,还有几个同学发邮件探...
客户介绍 闲鱼是依托阿里电商体系的前台型业务,有非常独特的业务特点和用户诉求...
日前 阿里云云效联合阿里云大学团队 面向全国高校学子正式启动了83行代码重构大...
AnalyticDB for MySQL是云端托管的PB级高并发低延时数据仓库 通过AnalyticDB for...
本文转载自微信公众号「见贤思编程」,作者泰斗贤若如 。转载本文请联系见贤思编...
鉴于近期加密货币大涨,导致很多小(韭)白(菜)纷纷入场,然后很多人都在问显卡挖...