Game of Life II

http://segmentfault.com/a/1190000003819277

In Conway's Game of Life, cells in a grid are used to simulate biological cells. Each cell is considered to be either alive or dead. At each step of the simulation each cell's current status and number of living neighbors is used to determine the status of the cell during the following step of the simulation.

In this one-dimensional version, there are N cells numbered 0 through N-1. The number of cells does not change at any point in the simulation. Each cell i is adjacent to cells i-1 and i+1. Here, the indices are taken modulo N meaning cells 0 and N-1 are also adjacent to eachother. At each step of the simulation, cells with exactly one living neighbor change their status (alive cells become dead, dead cells become alive).

For example, if we represent dead cells with a '0' and living cells with a '1', consider the state with 8 cells: 01100101 Cells 0 and 6 have two living neighbors. Cells 1, 2, 3, and 4 have one living neighbor. Cells 5 and 7 have no living neighbors. Thus, at the next step of the simulation, the state would be: 00011101

一维数组需要考虑的情况更少，要注意的是这里头和尾是相连的，所以在判断其左右两边时要取模。

public void solveOneD(int[] board){
    int n = board.length;
    int[] buffer = new int[n];
    // 根据每个点左右邻居更新该节点情况。
    for(int i = 0; i < n; i++){
        int lives = board[(i + n + 1) % n] + board[(i + n - 1) % n];
        if(lives == 1){
            buffer[i] = (board[i] + 1) % 2;
        } else {
            buffer[i] = board[i];
        }
    }
    for(int i = 0; i < n; i++){
        board[i] = buffer[i];
    }
}

In Place 一维解法

public void solveOneD(int rounds, int[] board){
    int n = board.length;
    for(int i = 0; i < n; i++){
        int lives = board[(i + n + 1) % n] % 2 + board[(i + n - 1) % n] % 2;
        if(lives == 1){
            board[i] = board[i] % 2 + 2;
        } else {
            board[i] = board[i];
        }
    }
    for(int i = 0; i < n; i++){
        board[i] = board[i] >= 2 ? (board[i] + 1) % 2 : board[i] % 2;
    }
}

表优化法

public void solveOneDWithTable(int[] board){
    int n = board.length;
    int[] lookupTable = {0, 1, 0, 1, 1, 0, 1, 0};
    int[] buffer = new int[n];
    int env = board[n - 1] * 2 + board[0] * 1;
    for(int i = 0; i < n; i++){
        env = (env % 4) * 2 + board[(i + n + 1) % n] * 1;
        buffer[i] = (lookupTable[env] + board[i]) % 2;
        System.out.println(env);
    }
    for(int i = 0; i < n; i++){
        board[i] = buffer[i];
    }
}

[LeetCode]Game of Life