# LeetCode: 957. N 天后的牢房¶

## 1、题目描述¶

8 间牢房排成一排，每间牢房不是有人住就是空着。

• 如果一间牢房的两个相邻的房间都被占用或都是空的，那么该牢房就会被占用。
• 否则，它就会被空置。

（请注意，由于监狱中的牢房排成一行，所以行中的第一个和最后一个房间无法有两个相邻的房间。）

输入：cells = [0,1,0,1,1,0,0,1], N = 7

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]


输入：cells = [1,0,0,1,0,0,1,0], N = 1000000000



• $cells.length == 8$
• cells[i] 的值为 0 或 1
• $1 <= N <= 10^9$

## 2、解题思路¶

• 因为只有8位，因此肯定会产生循环，最高也不会超过256
• 只需要找出循环的长度与起始点就能直接推算出来
class Solution:
def prisonAfterNDays(self, cells: List[int], N: int) -> List[int]:
start = "".join([str(i) for i in cells])
index = []
mapping = {}

def get_next_day(days):
current = days

length = len(current)
current_ans = ["0"] * length

for i in range(1, length - 1):
if (current[i - 1] == "1" and current[i + 1] == "1") or (
current[i - 1] == "0" and current[i + 1] == "0"):
current_ans[i] = "1"

return "".join(current_ans)

ans = start
if N <= 256:
for _ in range(N):
ans = get_next_day(ans)
else:
count = 1
cur = start
cycle = 1
cycle_start = 1
for _ in range(256):
cur = get_next_day(cur)
if cur not in mapping:
mapping[cur] = count
index.append(cur)
else:
cycle = count - mapping[cur]
cycle_start = mapping[cur]
break
count += 1

N -= cycle_start
ans = index[N % cycle]

return list(map(int, ans))