难度：★★★☆☆
类型：数组
方法：穷举法
题目
力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录
8 间牢房排成一排，每间牢房不是有人住就是空着。
每天，无论牢房是被占用或空置，都会根据以下规则进行更改：
如果一间牢房的两个相邻的房间都被占用或都是空的，那么该牢房就会被占用。
否则，它就会被空置。
（请注意，由于监狱中的牢房排成一行，所以行中的第一个和最后一个房间无法有两个相邻的房间。）
我们用以下方式描述监狱的当前状态：如果第 i 间牢房被占用，则 cell[i]==1，否则 cell[i]==0。
根据监狱的初始状态，在 N 天后返回监狱的状况（和上述 N 种变化）。
示例 1：
输入：cells = [0,1,0,1,1,0,0,1], N = 7
输出：[0,0,1,1,0,0,0,0]
解释：
下表概述了监狱每天的状况：
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：
输入：cells = [1,0,0,1,0,0,1,0], N = 1000000000
输出：[0,0,1,1,1,1,1,0]
提示：
cells.length == 8
cells[i] 的值为 0 或 1
1 <= N <= 10^9
解答
很显然我们可以定义一个函数，用于按照规则求取第二天的牢房状态，但是可能出现一种情况，需要求很多天数后的状态，例如示例2的1000000000，不知要计算到猴年马月，这样按部就班的求显然是不可行的。
我们观察到，牢房的总数也就一个字节，而且每个牢房的状态也就0和1，因此，整个牢房的所有状态无非一个字节能表达的整型数字的个数：256。只要一个状态出现过，那么后续状态一定会重复，也就是说：牢房的状态随着时间的变化是有是周期性的。只要找到周期性变化的规律，无论让求多久的状态，都可以立马得到答案。既然只有256个选择，那么当时间足够长时候，周期性的出现是必然的。
周期函数的主要指标：周期和相位，翻译到这道题上，就是以下两个指标：
n：发现某状态第二次出现的时间；
first_occur：那么该状态第一次出现的时间；
那么周期就是：n-first_occur，相位的绝对值就是first_occur。
我们将每一天的状态记录在哈希表seen中（时间与状态的对应对），只要获得了上面所说的两个主要指标，就可以根据这些指标，计算出任何一天N对应的状态，这一天的状态根据周期函数的性质一定与这一天相同：first_occur + (N-first_occur) % (n-first_occur)，而这一天肯定是在哈希表中记录过的，查表就好了。
有两点需要注意：
-
两头的两个房间不论第一天状态如何，根据规则第二天总是会变成0，因此不是周期函数的一部分，在判别时需要区分对待；
-
一旦发现重复，即可跳出循环，此时seen记录中已经包含一个周期的记录了；
-
区分对待N不足一个周期的状况，应该直接返回相应结果，无需根据周期性来计；
-
字典的键值交换可以方便查询。
class Solution(object):
def prisonAfterNDays(self, cells, N):
def next_day(cells):
return [int(0 < i < 7 and cells[i - 1] == cells[i + 1]) for i in range(8)]
seen = dict()
n = 0
first_occur = -1
while n < N:
cells = tuple(cells)
if cells in seen and seen[cells] != 0:
first_occur = seen[cells]
break
seen[cells] = n
n += 1
cells = next_day(cells)
if first_occur == -1:
return cells
return dict(zip(seen.values(), seen.keys()))[first_occur + (N-first_occur) % (n-first_occur)]
如有疑问或建议，欢迎评论区留言~
有关更多力扣中等题的python解决方案，请移步力扣中等题解析
网友评论