LeetCode 289. Game of Life (生命游戏)
According to the Wikipedia's article: "The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970."
Given a board with m by n cells, each cell has an initial state live (1) or dead (0). Each cell interacts with its eight neighbors (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article):
- Any live cell with fewer than two live neighbors dies, as if caused by under-population.
- Any live cell with two or three live neighbors lives on to the next generation.
- Any live cell with more than three live neighbors dies, as if by over-population..
- Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.
Write a function to compute the next state (after one update) of the board given its current state.
Follow up:
- Could you solve it in-place? Remember that the board needs to be updated at the same time: You cannot update some cells first and then use their updated values to update other cells.
- In this question, we represent the board using a 2D array. In principle, the board is infinite, which would cause problems when the active area encroaches the border of the array. How would you address these problems?
题目标签:Array
题目给了我们一个2d array,让我们根据game of life 的规则,改变cells,进行到下一个 状态。
规定了我们要in-place改动,但是问题在于,每一个cell 的改动都依赖于它周围8个的cell的情况,所以有先后顺序的改动,肯定会造成错误。
所以我们要想出一种方法,就是,改动完了的cell,我们查看它的情况,依然能够知道那个cell 之前的state。
对于每一个cell, 可以建立 4种情况:
0 dead -> dead 没有变化
1 live -> live 没有变化
2 live -> dead 从live 变为 dead
3 dead -> live 从dead 变为live
对于情况0 和1, 因为没有变化,所以每个cell 的值 还是 0 和 1;
增加2种情况:如果是从 live 变为 dead, 就把值改成2; 如果是从 dead 变为 live, 就把值改成3。
那么对于每一个cell, 我们要查看的是它周围有几个live cell 来做判断,如果周围的cell 已经被改动过了,我们需要看的是它之前的状态。
那么我们看,红色的是初始的状态,蓝色的是改动过的状态,因为我们只需要查看live, 不管它有没有被改动过,我们只看红色部分就对了,因为我们要的是它初始的状态,那么只可能是1 和 2。所以我们只需要查看所有cell 是1 或者是 2的,来count 一共有几个live neighbors。
Java Solution:
Runtime beats 10.94%
完成日期:09/15/2017
关键词:Array,
关键点:对于每一个cell,有4个值,每一个值对应一种变化关系
class Solution
{
public void gameOfLife(int[][] board)
{
if(board == null || board.length == 0)
return; int m = board.length; // rows
int n = board[0].length; // columns // first iteration: mark states for each cell
for(int i=0; i<m; i++) // rows
{
for(int j=0; j<n; j++) // columns
{
int cnt = 0;
// count cell's live neighbors 3x3 matrix and set boundary
for(int x= Math.max(0, i-1); x<= Math.min(m-1, i+1); x++)
{
for(int y= Math.max(0, j-1); y<= Math.min(n-1, j+1); y++)
{
if(x == i && y == j) // skip itself
continue;
// only state 1 and 2: cell are live for previous state
if(board[x][y] == 1 || board[x][y] == 2)
cnt++;
}
} if(board[i][j] == 0 && cnt == 3) // current is dead cell
board[i][j] = 3; // dead -> live
else if(board[i][j] == 1 && (cnt < 2 || cnt > 3)) // current live cell
board[i][j] = 2; // live -> dead
}
} // second iteration: convert state back to dead or live
for(int i=0; i<m; i++)
for(int j=0; j<n; j++)
board[i][j] %= 2;
}
}
参考资料:
http://www.cnblogs.com/grandyang/p/4854466.html
LeetCode 题目列表 - LeetCode Questions List
最新文章
- 微信将推指纹支付 ";指付通";会与Touch ID整合吗
- iOS archive(归档)的总结 (序列化和反序列化,持久化到文件)
- gridview--基本的gridview
- Wap站总结一
- iphone开发之适配iphone5
- JAVA GUI学习 - JTable表格组件学习_C ***
- VMware Workstation 12 Pro 之安装林耐斯Ubuntu X64系统
- 《大型网站系统与JAVA中间件实践》【PDF】下载
- Java Web前端到后台常用框架介绍
- 五一出门必备的手机APP神器 让你瞬间大开眼界
- Devexpress中文语言包汉化
- 工欲善其事,必先利其器-ecplise配置和优化
- MySQL开启远程连接的方法
- Java中的Html解析:使用jsoup
- JQuery判断数组中是否包含某个字符串
- 【洛谷】【单调栈】P4333 [COI2007] Patrik
- 在没有创建Provision Profile权限的情况下 发布Enterprise inhouse app 的方法
- linux平台下防火墙iptables原理
- C盘下出现msdia80.dll文件
- Python 列表 sort() 方法