生命游戏
根据百度百科，生命游戏，简称为生命，是英国数学家约翰·何顿·康威在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] ]
进阶:
- 你可以使用原地算法解决本题吗？请注意，面板上所有格子需要同时被更新：你不能先更新某些格子，然后使用它们的更新后的值再更新其他格子。
- 本题中，我们使用二维数组来表示面板。原则上，面板是无限的，但当活细胞侵占了面板边界时会造成问题。你将如何解决这些问题？
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=289
解题思路分析：
解法一：（非原地算法， 原地算法请参考解法二）
因为所有个字需要被同时更新，也就是说更新的条件要基于原始数据，这样一来，我么边更新数据，边参照当前数据的话，数据会发生混乱，换句话说我们无法辨别哪些是已更新的，哪些是原始数据。因此我们需要新建一个二维数组，参照原数组计算出新的数据之后，将新数据赋值给新数组即可。最后别忘了将新数组的所有数据再一次性赋值到原始数组。
实现代码：
public void gameOfLife(int[][] board) {
// 新建一个数组
int[][] result = new int[board.length][board[0].length];
// 循环原始数组的每个元素
for(int r=0;r<board.length;r++){
for(int c=0;c<board[0].length;c++){
// 计算出当前元素周围活细胞的数量
int liveCount=0;
if(r-1>=0) liveCount+=board[r-1][c];
if(r+1<board.length) liveCount+=board[r+1][c];
if(c-1>=0) liveCount+=board[r][c-1];
if(c+1<board[0].length) liveCount+=board[r][c+1];
if(r-1>=0 && c-1>=0) liveCount+=board[r-1][c-1];
if(r+1<board.length && c+1<board[0].length) liveCount+=board[r+1][c+1];
if(r-1>=0 && c+1<board[0].length) liveCount+=board[r-1][c+1];
if(r+1<board.length && c-1>=0) liveCount+=board[r+1][c-1];
// 当前细胞为活细胞
if(board[r][c]==1){
// 如果周围活细胞数量小于2或者大于1
if(liveCount<2 || liveCount>3){
// 当前细胞变为死细胞
result[r][c]=0;
}else{
// 反之当前细胞为活细胞
result[r][c]=1;
}
} else{ // 当前细胞为死细胞
// 周围活细胞数量为3
if(liveCount==3){
// 当前细胞为活细胞
result[r][c]=1;
}
}
}
}
// 将新的数组完全赋值到原始数组
System.arraycopy(result, 0, board, 0, board.length);
} 本解法执行时间为0ms。
Runtime: 0 ms, faster than 100.00% of Java online submissions for Game of Life.
Memory Usage: 34.9 MB, less than 100.00% of Java online submissions for Game of Life.
解法二：（原地算法）
在解法一中，我们使用了额外的二维数组来记录更新后的状态。若要使用原地算法来解题，那么就需要考虑如何在现有数组上进行变换。
题目中，不论什么条件，无非是将1变成0，或者0变成1。为了变换后不影响其他元素的变换，我们可以引入另外两个数值，我们使用2代表原数字为0，变更后为1。用3代表原数字是1，变更后为0。这样，查看周围活细胞时，0和2都可暂时看作是0，1和3都可看做是1。赋值时将死细胞赋值为3，活细胞赋值为2。
变换完成之后，我们需要再循环一遍数组，将所有的2变为1，所有的3变为0即可。
实现代码：
public void gameOfLife(int[][] board) {
for(int r=0;r<board.length;r++){
for(int c=0;c<board[0].length;c++){
int liveCount=0;
if(r-1>=0) liveCount+=(board[r-1][c])%2;
if(r+1<board.length) liveCount+=(board[r+1][c])%2;
if(c-1>=0) liveCount+=(board[r][c-1])%2;
if(c+1<board[0].length) liveCount+=(board[r][c+1])%2;
if(r-1>=0&&c-1>=0) liveCount+=(board[r-1][c-1])%2;
if(r+1<board.length&&c+1<board[0].length) liveCount+=(board[r+1][c+1])%2;
if(r-1>=0&&c+1<board[0].length) liveCount+=(board[r-1][c+1])%2;
if(r+1<board.length&&c-1>=0) liveCount+=(board[r+1][c-1])%2;
if(board[r][c]==1){
if(liveCount<2 || liveCount>3){
board[r][c]=3; // 3== 1 -> 0;
}
} else{
if(liveCount==3){
board[r][c]=2; // 2== 0 -> 1
}
}
}
}
for(int r=0;r<board.length;r++){
for(int c=0;c<board[0].length;c++){
if(board[r][c]==3) board[r][c]=0;
if(board[r][c]==2) board[r][c]=1;
}
}
} 本解法执行时间为0ms。
Runtime: 0 ms, faster than 100.00% of Java online submissions for Game of Life.
Memory Usage: 34.9 MB, less than 100.00% of Java online submissions for Game of Life.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-289-game-of-life-解题思路分析/