[LeetCode] 289 Game of Life

Description

According to 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."
The board is made up of an m x n grid of cells, where each cell has an initial state: live (represented by a 1) or dead (represented by a 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.

The next state is created by applying the above rules simultaneously to every cell in the current state, where births and deaths occur simultaneously. Given the current state of the m x n grid board , return the next state.

Example 1:

Input: board = [[0,1,0],[0,0,1],[1,1,1],[0,0,0]]
Output: [[0,0,0],[1,0,1],[0,1,1],[0,1,0]]

Example 2:

Input: board = [[1,1],[1,0]]
Output: [[1,1],[1,1]]

Constraints:

m == board.length

n == board[i].length

1 <= m, n <= 25

board[i][j] is 0 or 1 .

に答える

2 D配列は、0または1のみから構成される.

生と死が伴う.

私をめぐる8명の隣人の中で、生きている隣人の数によって、私は死ぬか生きることができます.

<ルール>
[原句]私が生きている間に、二人も住んでいない隣の人が死んでしまった.
[原句]私が生きている間に二、三人の隣人がいた->そのまま生きていた.
[原句]私が生きている間に、三人以上の隣人が生きていた.
[原句]私が死んだとき、隣の三人が生きていた.

まず、生と死は一緒に発生するので、既存の記憶値を見て条件を適用します.したがって、既存の値を新しい2 D配列にコピーします.

私の周りの8つの隣接座標を容易にするために、xy 2次元配列には、移動する各좌표의 차이が格納されています.

コピーした配列マトリクスをすべて回転させます.

xy配列に格納された座標を1つずつ適用し,隣接する座標を求める.

隣の座標は범위 안에 있고값이 1일 때、つまり生きている間に数を数えます.

その後、以上の4つのルールが適用されます.
<コード順>
1番ルール->既存の配列の弦座標値を0に変更します.(死亡)
2番ルール->既存のアレイの座標値を保持します.
4番ルール->既存の配列の弦座標値を1に変更します.(生活)
3番ルール->既存の配列の弦座標値を0に変更します.(死亡)

これにより、既存の配列が新しい値に変更されます.

各マトリクスは1回のみ回転し,2つの記憶値の2次元配列のみで,時間的および空間的複雑さはO(N)であった.

コード#コード#

class Solution {
    public void gameOfLife(int[][] board) {
        int[][] copyBoard = new int[board.length][board[0].length];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                copyBoard[i][j] = board[i][j];
            }
        }
        int[][] xy = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
        int count, neighborX, neighborY;
        for (int i = 0; i < copyBoard.length; i++) {
            for (int j = 0; j < copyBoard[0].length; j++) {
                count = 0;
                for (int k = 0; k < xy.length; k++) {
                    neighborX = i + xy[k][0];
                    neighborY = j + xy[k][1];
                    if (neighborX >= 0 && neighborX < copyBoard.length && neighborY >= 0 && neighborY < copyBoard[0].length && copyBoard[neighborX][neighborY] == 1) {
                        count++;
                    }
                }
                if (copyBoard[i][j] == 1 && count < 2) board[i][j] = 0;
                else if (copyBoard[i][j] == 1 && count <= 3) board[i][j] = copyBoard[i][j];
                else if (copyBoard[i][j] == 0 && count == 3) board[i][j] = 1;
                else if (copyBoard[i][j] == 1 && count > 3) board[i][j] = 0;
            }
        }
    }
}