289.生命游戏
标签：数组、矩阵、模拟
难度：中等
描述：给定一个 m×n 大小的二维数组 board，每一个格子都可以看做是一个细胞。每个细胞都有一个初始状态：1 代表活细胞，0 代表死细胞。每个细胞与其相邻的八个位置（水平、垂直、对角线）细胞遵循以下生存规律：
如果活细胞周围八个位置的活细胞数少于 2 个，则该位置活细胞死亡；
如果活细胞周围八个位置有 2 个或 3 个活细胞，则该位置活细胞仍然存活；
如果活细胞周围八个位置有超过 3 个活细胞，则该位置活细胞死亡；
如果死细胞周围正好有 3 个活细胞，则该位置死细胞复活。
二维数组代表的下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的的。其中细胞的出生和死亡是同时发生的。
现在给定 m×n 的二维数组 board 的当前状态。
要求：返回下一个状态。
说明：
m==board.length。
n==board[i].length。
1≤m,n≤25。
board[i][j] 为 0 或 1。
进阶：
你可以使用原地算法解决本题吗？请注意，面板上所有格子需要同时被更新：你不能先更新某些格子，然后使用它们的更新后的值再更新其他格子。
本题中，我们使用二维数组来表示面板。原则上，面板是无限的，但当活细胞侵占了面板边界时会造成问题。你将如何解决这些问题？
示例：
示例1
输入：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]]示例2
输入：board = [[1,1],[1,0]]
输出：[[1,1],[1,1]]思路1：使用复制的数组
用copyarray数组复制原始的数组，copyarray数组用于查询周围8个位置活细胞的数量，然后根据活细胞的数量（题目中的规则）修改原始数组board。
public void gameOfLife(int[][] board) {
int m = board.length;
int n = board[0].length;
int[][] copyarray = new int[m][n];
// 用于遍历周围8个位置
int[] direaction = {-1, 0, 1};
// 拷贝board，复制的数组用于查找周围活细胞个数
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
copyarray[i][j] = board[i][j];
}
}
int indexRow = 0, indexCol = 0;
// 统计活细胞个数
int liveCount = 0;
// 遍历复制的数组，查找周围活细胞个数并修改原数组中的细胞状态
for (int row = 0; row < m; row++) {
for (int col = 0; col < n; col++) {
liveCount = 0;
// 统计周围8个位置活细胞的数量
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (!(direaction[i] == 0 && direaction[j] == 0)){
indexRow = row + direaction[i];
indexCol = col + direaction[j];
if ((indexRow >= 0 && indexRow < m) && (indexCol >= 0 &&
indexCol < n) && copyarray[indexRow][indexCol] == 1){
liveCount++;
}
}
}
}
// 规则1、3
if ( copyarray[row][col] == 1 && (liveCount < 2 || liveCount > 3)){
board[row][col] = 0;
}
// 规则4
if ( copyarray[row][col] == 0 && liveCount == 3){
board[row][col] = 1;
}
}
}
}思路2：利用复合状态
如果采用原地修改数组的方法，那么就必须面对一个问题，即更新部分位置的元素会影响到周围还未更新的元素（影响到统计活细胞的个数）。所以这里使用一个技巧，使用复合状态表示元素的过去状态和未来状态。复合状态的作用是：在需要统计周围8个位置活细胞个数的时候，已更新部分不会影响到未更新部分，同时该位置复合状态会标记出未来会变成什么状态。
仔细思考一下，其实细胞只有4个变化状态：
活细胞到死细胞，1->0
活细胞到活细胞，1->1
死细胞到活细胞，0->1
死细胞到死细胞，0->0
只有“活细胞到死细胞”、“死细胞到活细胞”会对细胞的状态造成影响，所以我们主要考虑这2种状态变化。我们定义复合状态：
活细胞到死细胞：赋值为 -1。统计周围8个位置活细胞个数时候，采用Math.abs(元素)的方式，既可以统计现在状态是活细胞（值为1）的个数，也可以统计出过去是活细胞（值为-1）的个数。
死细胞到活细胞：赋值为 2。统计周围8个位置活细胞个数时候，不会统计到值为2的个数。
整个算法的过程：
遍历二维数组的每一个位置。并对该位置遍历周围8个位置，利用绝对值方式计算出8个位置上的活细胞数量。
规则1和3：如果此位置是活细胞，并且周围活细胞少于 2 个或超过 3 个，则将其暂时标记为 −1，意为此细胞死亡。
规则4：如果此位置是死细胞，并且周围有 3 个活细胞，则将暂时标记为 2，意为此细胞复活。
遍历完之后，再次遍历一遍二维数组，修改复合状态的值为未来的状态。如果该位置为 −1，将其赋值为 0，如果该位置为 2，将其赋值为 1。
public void gameOfLife(int[][] board) {
int m = board.length;
int n = board[0].length;
// 用于遍历周围8个位置
int[] direaction = {-1, 0, 1};
// 活细胞的个数
int liveCount = 0;
for (int row = 0; row < m; row++){
for (int col = 0; col < n; col++) {
liveCount = 0;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (!(direaction[i] == 0 && direaction[j] == 0)){
int indexRow = row + direaction[i];
int indexCol = col + direaction[j];
if (indexRow >= 0 && indexRow < m && indexCol >= 0 && indexCol < n
&& Math.abs(board[indexRow][indexCol]) == 1){
liveCount++;
}
}
}
}
// 规则1、3
if (board[row][col] == 1 && (liveCount < 2 || liveCount > 3)){
board[row][col] = -1;
}
// 规则4
if (board[row][col] == 0 && liveCount == 3){
board[row][col] = 2;
}
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == -1){
board[i][j] = 0;
}else if (board[i][j] == 2){
board[i][j] = 1;
}
}
}
}
评论区