Leetcode

Leetcode 957：N日後のセル（非常に詳細なソリューション!!!）



Leetcode 957 Cell After N Days Super Detailed Solution



8つのセルが一列に並んでおり、各セルは空または空のいずれかです。

セルが占有されているか空いているかにかかわらず、毎日、次のルールに従ってセルが変更されます。



  • セルの隣接する2つの部屋が占有されているか空の場合、セルは占有されます。
  • それ以外の場合は空になります。

（刑務所内の独房が並んでいるため、列の最初と最後の部屋に隣接する部屋を2つ持つことはできませんのでご注意ください。）

刑務所の現在の状態を次のように説明します：iセルが占有されている場合、cell[i]==1それ以外の場合cell[i]==0。



刑務所の初期状態によると、Nその日後に刑務所に戻る状況（および上記のNが変化する）。

例1：

Input: cells = [0,1,0,1,1,0,0,1], N = 7 Output: [0,0,1,1,0,0,0,0] Explanation: The table below summarizes the daily conditions of the prison: Day 0: [0, 1, 0, 1, 1, 0, 0, 1] Day 1: [0, 1, 1, 0, 0, 0, 0, 0] Day 2: [0, 0, 0, 0, 1, 1, 1, 0] Day 3: [0, 1, 1, 0, 0, 1, 0, 0] Day 4: [0, 0, 0, 0, 0, 1, 0, 0] Day 5: [0, 1, 1, 1, 0, 1, 0, 0] Day 6: [0, 0, 1, 0, 1, 1, 0, 0] Day 7: [0, 0, 1, 1, 0, 0, 0, 0]

例2：



Input: cells = [1,0,0,1,0,0,1,0], N = 1000000000 Output: [0,0,1,1,1,1,1,0]

促す：

  1. cells.length == 8
  2. cells[i]値0または1
  3. 1 <= N <= 10^9

問題解決

これは、表示できる古典的なセルオートマトンの問題です。 Leetcode 289：ライフゲーム（最も詳細なソリューション!!!） 。考えられる最初の解決策はブルートフォースです（トピックの意味に従ってください）

class Solution: def prisonAfterNDays(self, cells, N): ''' :type cells: List[int] :type N: int :rtype: List[int] ''' tmp = [0]*8 for _ in range(N): for i in range(1, 7): tmp[i] = int(cells[i-1] == cells[i+1]) cells = tmp[::] return cells

上記の記述を簡略化できます

class Solution: def prisonAfterNDays(self, cells, N): ''' :type cells: List[int] :type N: int :rtype: List[int] ''' for _ in range(N): cells = [0] + [cells[i - 1] ^ cells[i + 1] ^ 1 for i in range(1, 7)] + [0] return cells

しかし、与えられた場合Nそれが非常に大きい場合、これは時間の経過とともに明らかになりますN一定の回数の後、この配列の値が繰り返され始めます。したがって、変数を作成できますcycle記録に使用される重複値の数。重複が見つかった場合（最初の日を記録する必要がありますcells）k%=cycle次に、残りの値を実行し続けます。

class Solution: def prisonAfterNDays(self, cells, N): ''' :type cells: List[int] :type N: int :rtype: List[int] ''' source, tmp = None, [0]*8 cycle, k = 0, N while k: for i in range(1, 7): tmp[i] = int(cells[i-1] == cells[i+1]) if cycle == 0: source = tmp[::] elif source == tmp: k %= cycle cells = tmp[::] cycle += 1 k -= 1 return cells

実際、ここですべてのルールを見つけたら14繰り返し、このコードは次のように簡略化できます。

class Solution: def prisonAfterNDays(self, cells, N): ''' :type cells: List[int] :type N: int :rtype: List[int] ''' N = N % 14 if not N: N = 14 for _ in range(N): cells = [0] + [cells[i - 1] ^ cells[i + 1] ^ 1 for i in range(1, 7)] + [0] return cells

前の質問のエンコード方法を使用して、この問題をエンコードします

  • インクルード<- die 00
  • インクルード<- live 01
  • 住む<- die 10
  • 住む<- live 11
class Solution: def prisonAfterNDays(self, cells, N): ''' :type cells: List[int] :type N: int :rtype: List[int] ''' N = N % 14 if not N: N = 14 for _ in range(N): for i in range(1, len(cells) - 1): if cells[i-1] & 1 == cells[i+1] & 1: cells[i] = 2 if not cells[i] & 1 else 3 for i in range(len(cells)): cells[i] >>= 1 return cells

このようにして、私たちのスペースは再び最適化されます。

質問の他の言語バージョンを自分に追加しました GitHub Leetcode

ご不明な点がございましたら、皆様のご指摘をお待ちしております！ ！ ！