[leetcode] 957. Prison Cells After N Days

[leetcode] 957. Prison Cells After N Days

Description

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 = 7Output: [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 = 1000000000Output: [0,0,1,1,1,1,1,0]

Note:

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

分析

题目的意思是：根据上面的规则，求出第N天牢房的状态。这道题需要找规律，因为N很大的时候肯定会超时，牢房有8个状态，其中第1个和最后一个肯定是0，我们只需要找中间6个状态的规律就行了。

prison用来存储已经得到的状态，防止进入死循环，利用prison可以找到循环周期，然后更新N，再递归调用一遍就可以得到最终的cells的状态了主意一下mod的计算方式和递归的时候N的更新方式，我尝试把它换成N%(mod+1)结果ac不了，这个以后可以研究一下啦每一次确定下一天状态的时候，只需要确定中间的6个状态就行了

如果知道上面这些要点，就容易写出来了

代码

class Solution: def prisonAfterNDays(self, cells: List[int], N: int) -> List[int]: prison = {} for i in range(N): str1=str(cells) if(str1 in prison): mod=i-prison[str1] return self.prisonAfterNDays(cells,(N-i)%mod) prison[str1]=i t=[0] for i in range(1,7): if(cells[i-1]==cells[i+1]): t.append(1) else: t.append(0) t.append(0) cells=t return cells

参考文献

​​Python Solution​​​​[LeetCode]957.Prison Cells After N Days 中文​​​​957. Prison Cells After N Days​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。