摘要：思路普通解法，遍歷每一個(gè)細(xì)胞求值，用一個(gè)的矩陣存放結(jié)果。求值過程，稍微分析一下可知，其實(shí)就是按照以下的矩陣進(jìn)行結(jié)果是可數(shù)的。

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?

思路1
普通解法，遍歷每一個(gè)細(xì)胞求值，用一個(gè)M*N的矩陣存放結(jié)果。
求值過程，稍微分析一下可知，其實(shí)就是按照以下的矩陣進(jìn)行,結(jié)果是可數(shù)的。

        細(xì)胞狀態(tài)       0    1
        鄰居1個(gè)數(shù)0     0    0
                1     0    0
                2*    0    1
                3*    1    1
                4     0    0
                5     0    0
                6     0    0
                7     0    0
                8     0    0

復(fù)雜度
空間（MN），時(shí)間（MN）

實(shí)現(xiàn)代碼1

public class GameofLife {
    
    /**
     * 直接解法    
     * 空間(n)
     * @param board
     * @return
     */
    public int[][] Solution1(int[][] board){
        int m = board.length;s

        int n = board[0].length;

        int[][] result = new int [m][n];

        for(int i = 0; i= MAXROW || c < 0 || c >= MAXCOL)  
                        continue;  
                    if(r==row && c == col)
                        continue;
                    if(board[r][c] == 1)  
                        count++;  
                }  
         if(count==3)
             result = 1;
         else if(board[row][col] == 1 && count ==2)
             result = 1;
         else 
             result = 0;
        
        return result;
    }
}

思路2
要求inplace解法，即不用額外的空間，那么就要同時(shí)保存細(xì)胞 前后的狀態(tài)
這個(gè)解法用0，1，2，3來表示細(xì)胞下一代的計(jì)算結(jié)果，計(jì)算下一代時(shí)（統(tǒng)計(jì)鄰居和計(jì)算下一個(gè)狀態(tài)），把這四種情況都考慮進(jìn)去，
最后矩陣%2得到最終結(jié)果。
0: 0->0
1: 1->1
2: 1->0
3: 0->1

復(fù)雜度
空間（1），時(shí)間（M*N）

實(shí)現(xiàn)代碼2

public class GameofLife {
    /**
     *     0 : 上一輪是0，這一輪過后還是0
        1 : 上一輪是1，這一輪過后還是1
        2 : 上一輪是1，這一輪過后變?yōu)?
        3 : 上一輪是0，這一輪過后變?yōu)?
     * @param board
     * @return
     */
    public int[][] Solution2(int[][] board){
        int m = board.length;

        int n = board[0].length;

        int[][] result = new int [m][n];

        for(int i = 0; i= MAXROW || c < 0 || c >= MAXCOL)  
                        continue;  
                    if(r==row && c == col)
                        continue;
                    if(board[r][c] == 1 || board[r][c] == 2)  
                        count++;  
                }  
         
         if(board[row][col] == 1 && (count ==2 || count ==3))
             result = 2;
         else if  (board[row][col]==0 && count == 3) 
             result = 3;
         else
             result = board[row][col];
        
        return result;
    }
}

測試代碼

public class GameofLifeTest {

    private GameofLife s;
    
    @Before
        public void setUp() {
         s = new GameofLife();
        }
     
    @Test
    public void testSolution1() {
        
        int[][] nums = {
                {1,0,1},
                {1,0,1},
                {1,0,1}
        };
        int[][] expect = {
                {1,0,1},
                {1,0,1},
                {1,0,1}
        };
        
        int[][] result = s.Solution1(nums);
        for(int i=0;i<3;i++){
            for(int j=0;j<3;j++)
                System.out.print(result[i][j]);
            System.out.println("");
        }        
    }
    
    @Test
    public void testSolution2() {
        
        int[][] nums = {
                {1,0,1},
                {1,0,1},
                {1,0,1}
        };
        int[][] expect = {
                {1,0,1},
                {1,0,1},
                {1,0,1}
        };
        
        int[][] result = s.Solution2(nums);
        for(int i=0;i<3;i++){
            for(int j=0;j<3;j++)
                System.out.print(result[i][j]);
            System.out.println("");
        }        
    }
    
}

測試結(jié)果

000
101
000

101
000
101