Skip to content

Latest commit

 

History

History
141 lines (83 loc) · 3.03 KB

0957._Prison_Cells_After_N_Days.md

File metadata and controls

141 lines (83 loc) · 3.03 KB

957. Prison Cells After N Days

难度: Medium

刷题内容

原题连接

内容描述

There are 8 prison cells in a row, and each cell is either occupied or vacant.

Each day, whether the cell is occupied or vacant changes according to the following rules:

If a cell has two adjacent neighbors that are both occupied or both vacant, then the cell becomes occupied.
Otherwise, it becomes vacant.
(Note that because the prison is a row, the first and the last cells in the row can't have two adjacent neighbors.)

We describe the current state of the prison in the following way: cells[i] == 1 if the i-th cell is occupied, else cells[i] == 0.

Given the initial state of the prison, return the state of the prison after N days (and N such changes described above.)

 

Example 1:

Input: cells = [0,1,0,1,1,0,0,1], N = 7
Output: [0,0,1,1,0,0,0,0]
Explanation: 
The following table summarizes the state of the prison on each day:
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]

Example 2:

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

Note:

cells.length == 8
cells[i] is in {0, 1}
1 <= N <= 10^9

解题方案

思路 1 - 时间复杂度: O(1)- 空间复杂度: O(1)******

一看N这么大的数字就知道会有周期性，直接把每一天的cells存起来，然后通过是否之前出现过，取模算一下应该取的index即可

class Solution:
    def prisonAfterNDays(self, cells, N):
        """
        :type cells: List[int]
        :type N: int
        :rtype: List[int]
        """
        self.cache = {}
        self.states = [cells]
    
        idx = 0
        while str(cells) not in self.cache:
            self.cache[str(cells)] = idx
            idx += 1
            cells = [0] + [int(cells[i - 1] == cells[i + 1]) for i in range(1, 7)] + [0]
            self.states.append(cells)
            N -= 1
            if N == 0:
                return cells
        index = self.cache[str(cells)]
        return self.states[index + N % (idx - index)]

思路 2 - 时间复杂度: O(1)- 空间复杂度: O(1)******

用for loop实现更为方便

class Solution:
    def prisonAfterNDays(self, cells, N):
        """
        :type cells: List[int]
        :type N: int
        :rtype: List[int]
        """
        self.cache = {str(cells): 0}
        self.states = [cells]
        
        for i in range(1, N+1):
            cells = [0] + [int(cells[i - 1] == cells[i + 1]) for i in range(1, 7)] + [0]
            if str(cells) in self.cache:
                idx = self.cache[str(cells)]
                return self.states[idx+(N-idx)%(i-idx)]
            self.cache[str(cells)] = i
            self.states.append(cells)
        return cells