leetcode289. Game of Life

jerryloveemily 發(fā)布于2019-08-15 14:30 / 2107人閱讀

摘要：板上的每個(gè)小格子有兩種狀態(tài)，或。而根據(jù)游戲規(guī)則，每一次這個(gè)板上的內(nèi)容將會(huì)隨著前一次板上的內(nèi)容發(fā)生變化。然后再根據(jù)當(dāng)前格子的狀態(tài)計(jì)算當(dāng)前格子的下一個(gè)狀態(tài)。當(dāng)然最后別忘了將原始狀態(tài)傳遞出去。

題目要求

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?

這個(gè)內(nèi)容在維基百科上講述的非常詳細(xì)，有圖文示例。
這個(gè)游戲玩家在游戲開始后是不能操作的，完全是由最初的狀態(tài)來決定最終的結(jié)果。板上的每個(gè)小格子有兩種狀態(tài)，live或dead。
而根據(jù)游戲規(guī)則，每一次這個(gè)板上的內(nèi)容將會(huì)隨著前一次板上的內(nèi)容發(fā)生變化。變化的規(guī)則如下：

如果當(dāng)前格子為live，那么只要它周圍live鄰居的數(shù)量大于3個(gè)或是小于2個(gè)，該格子就會(huì)變成dead狀態(tài)。

如果當(dāng)前個(gè)字為dead，那么只要它周圍live的鄰居數(shù)量正好為3個(gè)，該格子就會(huì)變成live狀態(tài)。否則還是dead狀態(tài)。

現(xiàn)在輸入一個(gè)狀態(tài)，讓我們更新出板子的下一個(gè)狀態(tài)。

思路和代碼

這里其實(shí)用暴力查詢的話也是可以解決的。也就是每遇到一個(gè)格子就將該格子的鄰居統(tǒng)統(tǒng)遍歷一下，計(jì)算一個(gè)鄰居里面live和dead的數(shù)量。然后再根據(jù)當(dāng)前格子的狀態(tài)計(jì)算當(dāng)前格子的下一個(gè)狀態(tài)。但是這里需要一個(gè)新的m*n的數(shù)組來保存新的狀態(tài)，有點(diǎn)浪費(fèi)空間。而且不能很好的利用之前的遍歷結(jié)果。所以我們可以將之前的遍歷結(jié)果用某種方式直接存到當(dāng)前的格子里，減少一些遍歷次數(shù)。

假設(shè)現(xiàn)在有這樣的一個(gè)board：

[
 [1,0,1],
 [0,0,1],
 [1,1,0],
]

我們從左上角開始遍歷，我們發(fā)現(xiàn)它的周圍一個(gè)live的鄰居都沒有，因此它的狀態(tài)將會(huì)變?yōu)?。但是與此同時(shí)，它的上一個(gè)狀態(tài)為1，需要傳遞給周圍的鄰居，因此我們可以采用將周圍鄰居+10的方式傳遞。如下：

[
 [0,10,1],
 [10,10,1],
 [1,1,0],
]

這是我們再看坐標(biāo)為(0,1)的格子。假設(shè)當(dāng)前個(gè)字上的值為cur，那么cur/10則是之前鄰居的數(shù)量，cur%10則代表該格子的初始狀態(tài)。根據(jù)這個(gè)規(guī)律，我們可以知道當(dāng)前格子上的初始狀態(tài)為0即dead，而之前遍歷過的鄰居有1個(gè)。這時(shí)我們就無需遍歷所有的鄰居，只需要繼續(xù)訪問還未訪問的鄰居即可。當(dāng)然最后別忘了將原始狀態(tài)傳遞出去。

代碼如下：

    public void gameOfLife(int[][] board) {
       if(board==null || board.length==0) return;
       int row = board.length;
       int column = board[0].length;
       int multiply = 10;
       for(int i = 0 ; i=0 && isLive(board[i+1][j-1])){liveNeighboars++;}
                   if(j+13){
                       board[i][j] = 0;
                   }else{
                       board[i][j] = 1;
                   }
                   if(j+1=0 && i+1

想要了解更多開發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號！將會(huì)不定期的發(fā)放福利哦~