?"Push yourself, because no one else is going to do it for you." - Unknown

1. 題目描述

2. ?題目分析與解析

2.1 思路一——暴力求解

之所以先暴力求解，是因為我開始也沒什么更好的思路，所以就先寫一種解決方案，沒準寫著寫著就來新的靈感了。暴力求解思路還是很簡單的，就是嘗試遍歷面板的每個格子，判斷其周圍八個位置的狀態(tài)（對于邊角需要特殊處理），根據(jù)邊角種存在的活細胞（也就是1的個數(shù)）判斷該位置應該填什么。

但是需要注意一點，為了避免我們在原矩陣上更改值后導致影響后續(xù)的判斷，所以我們肯定需要先復制一個原始矩陣。

代碼思路：

1. 初始化，復制一個原始矩陣

2. 遍歷復制矩陣的每一個元素，查看其周圍八個位置的狀態(tài)，統(tǒng)計1的個數(shù)

   • 根據(jù)題目提到的判定規(guī)則：少于 2 個或者大于 3 個 1 就判定當前位置為 0

   • 等于 2 個 1 那么當前位置不需要更改

   • 如果等于 3 個 1 那么當前位置如果為 0 需要改為 1

   • 對于邊角位置需要額外處理防止越界

2.2 思路二——進階（原地算法）

根據(jù)題目中的進階提示，要求使用原地算法，也就是不能用一個額外的面板存儲現(xiàn)有的值，并且還提示了所有格子被同時更新。因此我們再想一想怎么解決。

如果使用原地算法，最主要的問題就是對于前面內容的更新會影響后面的結果，因為你不知道原來前面的內容是什么樣子。但是記住，原始狀態(tài)只有兩種，要么是0，要么是1。

而變化也只有四種

1. 要么原來是0，后來變成1

2. 要么原來是0，保持不變?yōu)?

3. 要么原來是1，后來變成0

4. 要么原來是1，后來不變?yōu)?

如下圖：

因為我們擔心原始信息被覆蓋，因此我們是不是可以添加幾個數(shù)字也就相當于幾種狀態(tài)，來存儲這些被覆蓋的信息？這樣我們看見某一個數(shù)字就知道它之前是什么狀態(tài)，就相當于在原始數(shù)據(jù)的基礎上進行操作了！在這里我們假設：

• 用 0 和 1 還是表示原來是什么現(xiàn)在就是什么的情況，也就是對應上圖中兩種不變的情況

• 而用數(shù)字2表示 0 改變?yōu)?1

• 用數(shù)字3表示 1 改變?yōu)?0

作圖表示如下：

對于這種原地算法，如果你需要用到之前的信息，但是可能之前的信息會被修改，就想辦法把原始信息用一種方式存儲起來。

因此我們在遍歷面板的每一個元素時，我們就知道之前的位置原始數(shù)據(jù)是什么，這樣就能正確計算結果，等到最后我們再根據(jù)每一種數(shù)字的情況將它歸為正確的表示，比如最后我們處理完了所有數(shù)據(jù)，然后我們再遍歷每個元素：

• 發(fā)現(xiàn)值為0或者1就不動

• 發(fā)現(xiàn)值為2就變?yōu)?

• 發(fā)現(xiàn)值為3就變?yōu)?

這樣就可以得到最終結果！

代碼思路：

1. 遍歷面板每一個元素，根據(jù)原始狀態(tài)和需要改變?yōu)榈闹荡_定該位置的值

   • 對于面板每一個元素，遇見周圍八個位置中有1和3就把它當作1

   • 對于面板每一個元素，遇見周圍八個位置中有2和0就把它當作0

2. 處理完每個元素后再次遍歷整個面板，將1與3替換回正確的值

2.3 思路三——思路一的優(yōu)化（位運算）

現(xiàn)在我們看看還有沒有什么優(yōu)化空間，有時間提示信息不是白給的哦：

題目提示我們board[i][j] 為 0 或 1，0和1，有沒有想到什么？學計算機的0和1分別表示什么？在java中int是怎么存儲的？

再看看面板的大??？1 <= m, n <= 25，在聯(lián)想一下int的存儲大小：

在不同編程語言中，int 類型的大小可以有所不同。以下是一些常見編程語言中 int 類型的大小：

1. C/C++:

   • 根據(jù)編譯器和操作系統(tǒng)的不同，int 類型通常為 4 字節(jié)，范圍大約是 -2,147,483,648 到 2,147,483,647。

2. Java:

   • Java 中的 int 類型固定為 4 字節(jié)，范圍是 -2,147,483,648 到 2,147,483,647。

3. Python:

   • Python 中的 int 類型大小是動態(tài)的，它可以根據(jù)需要自動調整。在 32 位系統(tǒng)上，通常為 4 字節(jié)，范圍約為 -2,147,483,648 到 2,147,483,647；在 64 位系統(tǒng)上，它可以是 4 字節(jié)或 8 字節(jié)，取決于所使用的 Python 版本。

4. JavaScript:

   • JavaScript 中的 int 類型實際上是一個 64 位浮點數(shù)，范圍大約是 -9,007,199,254,740,992 到 9,007,199,254,740,992。

5. Swift:

   • Swift 中的 Int 類型的大小取決于當前平臺的位數(shù)。在 32 位平臺上，Int 是 32 位，范圍大約是 -2,147,483,648 到 2,147,483,647；在 64 位平臺上，Int 是 64 位，范圍大約是 -9,223,372,036,854,775,808 到 9,223,372,036,854,775,807。

可以看到在大多數(shù)情況下至少是按照4字節(jié)存儲的，也就是32位，而一位可以表示0或者1兩個數(shù)，聯(lián)想到這里是不是又有了一種思路？我們是不是可以按照思路一的解決方案，雖然我們copy了一個原始面板，但是我們面板的每一個值都是一個int，如果我們把面板的一行設置位一個int來存儲，通過位運算來求解，是不是能省好多空間？

所以代碼思路還是思路一的代碼思路，但是我們此時需要使用位運算來解決！

如上圖，紅色部分就相當于我們的面板。

代碼思路：

1. 設置一個和board數(shù)組一樣行數(shù)的int數(shù)組命名位copy，每一個int值表示board的每一行

2. 初始化，采用位運算初始化copy數(shù)組

3. 遍歷復制矩陣的每一個元素，查看其周圍八個位置的狀態(tài)，統(tǒng)計1的個數(shù)

   • 根據(jù)題目提到的判定規(guī)則：少于 2 個或者大于 3 個 1 就判定當前位置為 0

   • 等于 2 個 1 那么當前位置不需要更改

   • 如果等于 3 個 1 那么當前位置如果為 0 需要改為 1

   • 對于邊角位置需要額外處理防止越界

2.4 思路四——壓榨空間到極致

既然我們已經(jīng)完成了思路三的代碼，我想大家應該更清楚位運算的特點。這時我們再看看面板，面板中每一個位置是不是一個int值？那就是32位（假設java在通常情況下），而面板中的值0或者1肯定只用了最后一位，就像下面這樣：

是不是這么多位置都空著想不想做點什么？空著的就是空間啊，由于1 <= m, n <= 25，那么是不是我們就可以用每一行的行首元素來當作我們思路三的copy數(shù)組，還是進行位運算操作，但是就不需要額外的空間了。

思路和思路三相似，但是唯一的改變就是我們將copy數(shù)組放在了board面板的每一行行行首位置而已。

比如對于題目中的示例：

將它放大看就是這樣：

其中藍色部分就是我們充當copy數(shù)組的位置。

比如對于題目中的

它轉化后的結果位：

對應的二進制位為：

1. 1073741824 is represented as 01000000000000000000000000000000

2. 536870912 is represented as 00100000000000000000000000000000

3. -536870911 is represented as 11100000000000000000000000000001

4. 0 is represented as 00000000000000000000000000000000

代碼思路：

1. 初始化，采用位運算初始化copy數(shù)組（實際上就是board的第一個元素的相應位）

2. 遍歷復制矩陣的每一個元素，查看其周圍八個位置的狀態(tài)，統(tǒng)計1的個數(shù)

   • 根據(jù)題目提到的判定規(guī)則：少于 2 個或者大于 3 個 1 就判定當前位置為 0

   • 等于 2 個 1 那么當前位置不需要更改

   • 如果等于 3 個 1 那么當前位置如果為 0 需要改為 1

   • 對于邊角位置需要額外處理防止越界

3. 最后需要更新第一列恢復為原來的值

2.5 思路五——壓榨空間到極致2

改代碼是看了自在飛花的解釋學到的，確實很厲害，因為他寫的c++版本，我在這解釋一下核心思想，并寫一個java版本。

這段代碼的核心思路是兩遍掃描棋盤：

1. 第一遍掃描，計算每個細胞周圍活細胞的數(shù)量，并用第二個比特位來存儲細胞是否應該存活。由于細胞的狀態(tài)是用0（死）和1（活）來表示的，所以作者通過按位與操作&1來獲取當前細胞的狀態(tài)，也就是只取int的最后一位，也就是0或者1，僅累加最低位，來計算周圍的存活細胞個數(shù)。

2. 第二遍掃描，通過右移操作>>= 1來更新細胞的狀態(tài)。這是因為在第一遍掃描中，如果一個細胞在下一代應該是活的，那么它的第二個比特位將被設置為1。通過右移一位，我們可以用這個第二比特位來覆蓋原來的狀態(tài)，從而更新棋盤。

1. 同時在代碼中使用了兩個數(shù)組dx和dy，他們用來表示周圍的八個位置，減少了遍歷周圍八個位置的for循環(huán)造成變量k或者l的重復開辟空間。

這個代碼我就直接附在這里了：

其實效果和思路四差不多，但是思路值得借鑒。

補充

count的優(yōu)化

如果還想繼續(xù)優(yōu)化還是有優(yōu)化空間的，比如我們的count作為一個計數(shù)變量，是可以放在某一個board元素里面的，因為它的最大值不會超過8，因為周圍最多也就八個元素。這樣用一個3個bit就可以存儲起來。

dx和dy優(yōu)化

同時dx和dy也可以優(yōu)化，因為dx和dy的范圍就是在-1到1之間，因此可以用兩個bit來存儲一個值，dx和dy總共有8組，也就是16個元素，那么用32個bit就可以存儲所有的dx和dy。

當然上面的優(yōu)化有點太瘋狂了，但是我們要舉一反三想到這些思路。

3. 代碼實現(xiàn)

3.1 思路一——暴力求解

3.2 思路二——原地算法

3.3 思路三——優(yōu)化（位運算）

在Java中，表達式 (copy[k] & (1 << (31 - l))) 并不直接結果為0或1，而是執(zhí)行了一個按位與（&）操作，這個操作的結果取決于copy[k]在指定位上的值。這里的操作細節(jié)如下：

• 1 << (31 - l)：這部分是位移操作。它將數(shù)字1向左移動(31 - l)位。這意味著，如果l為0，那么1將被移動到最高位（假設是32位整數(shù)），如果l是其他值，1就會被移動到相應的位置上。這樣做的目的是為了生成一個只在特定位置上有一個1的整數(shù)，其他位置都是0。

• copy[k] & (1 << (31 - l))：這部分是按位與操作。它比較copy[k]和上面計算出的數(shù)值，在每個位上進行邏輯與操作。只有當copy[k]在相應的位上也是1時，這個操作的結果在那個位上才是1，否則結果為0。因此，這個表達式的結果是一個整數(shù)，它在大多數(shù)位上都是0，在特定的位上可能是0或者是2的某次冪（取決于l的值）。如果你想判斷這個操作的結果是否為非零（即判斷copy[k]在(31 - l)位上是否為1），你可以將整個表達式與0進行比較：

<span style="background-color:#f8f8f8"><span style="color:#008855">boolean</span> <span style="color:#000000">isBitSet</span> <span style="color:#981a1a">=</span><span style="color:#777777"> (</span><span style="color:#000000">copy</span><span style="color:#777777">[</span><span style="color:#000000">k</span><span style="color:#777777">] </span><span style="color:#981a1a">&</span> <span style="color:#777777">(</span><span style="color:#116644">1 << </span><span style="color:#777777">(</span><span style="color:#116644">31</span> <span style="color:#981a1a">-</span> <span style="color:#000000">l</span><span style="color:#777777">))) </span><span style="color:#981a1a">!=</span> <span style="color:#116644">0</span><span style="color:#777777">;</span></span>

如果你的目的是確保結果嚴格為0或1，你需要進一步處理這個表達式，例如通過判斷表達式是否非零來將結果轉換為0或1：

<span style="color:#777777"><span style="background-color:#f8f8f8"><span style="color:#008855">int</span> <span style="color:#000000">bitValue</span> <span style="color:#981a1a">=</span> (<span style="color:#000000">copy</span>[<span style="color:#000000">k</span>] <span style="color:#981a1a">&</span> (<span style="color:#116644">1</span> << (<span style="color:#116644">31</span> <span style="color:#981a1a">-</span> <span style="color:#000000">l</span>))) <span style="color:#981a1a">!=</span> <span style="color:#116644">0</span> <span style="color:#981a1a">?</span> <span style="color:#116644">1</span> : <span style="color:#116644">0</span>;</span></span>

這樣，bitValue就會根據(jù)copy[k]在(31 - l)位上是否為1來分別存儲1或0。

3.4 思路四——位運算，但是copy存儲在board數(shù)組中

4. 相關復雜度分析

解法一：額外的復制矩陣

時間復雜度：O(MN)，其中M是行數(shù)，N是列數(shù)。因為需要遍歷整個矩陣兩次，一次復制，一次計算。空間復雜度：O(MN)，因為需要一個同樣大小的矩陣來存儲復制。

解法二：原地修改

時間復雜度：O(M*N)，同樣需要遍歷整個矩陣來計算周圍活細胞的數(shù)量?？臻g復雜度：O(1)，除了原數(shù)組外，沒有使用額外的空間，只是利用了額外的狀態(tài)來標記中間狀態(tài)。

解法三：位運算

時間復雜度：O(M*N)，需要遍歷整個矩陣來計算?？臻g復雜度：O(M)，雖然沒有使用額外的矩陣，但是使用了一個數(shù)組來存儲行的狀態(tài)。

解法四：位運算，但是copy存儲在board數(shù)組中

時間復雜度：O(M*N)，遍歷整個矩陣。空間復雜度：O(1)，所有操作都在原地完成，沒有使用額外的存儲空間。

解法五：位運算，將結果存儲在每個元素的左邊一位

時間復雜度：O(M*N)，需要遍歷整個矩陣來計算?？臻g復雜度：O(1)，所有操作都在原地完成，沒有使用額外的存儲空間。

在上述解法中，除了第一種解法需要和原矩陣一樣的額外空間，第三種解法使用了一個數(shù)組來存儲行的狀態(tài)，其他方法都采取了原地算法，即在原數(shù)組上直接修改，大大節(jié)約了空間。文章來源地址http://www.zghlxwxcb.cn/news/detail-833657.html

到了這里，關于面試經(jīng)典150題——生命游戲的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！