Leetcode 957. Prison Cells After N Days

文章作者：Tyan
博客：noahsnail.com  |  CSDN  |  简书

1. Description

2. Solution

**解析：**Version 1，根据变换规则可知，第一位和最后一位总是0，因此只有中间6位数在变，最大可能的变换周期为2^6。因此只要记录变换周期，因此周期中的所有状态就可得出变换结果，使用字典stat来判断每次变换是否与之前的重复，列表state记录状态变化，当出现重复状态时，计算变换的周期peroid，以及一个周期的状态变化，如果没出现周期，则直接返回变换后的结果，如果出现了，则返回计算后的状态。

• Version 1

class Solution:def prisonAfterNDays(self, cells: List[int], n: int) -> List[int]:stat = {
    }state = []temp = ''.join(list(map(str, cells)))stat[temp] = 0count = 0pre = cells[:]state.append(pre)for i in range(n):count += 1cells[0] = 0cells[7] = 0for j in range(1, 7):if (pre[j-1] == 1 and pre[j+1] == 1) or (pre[j-1] == 0 and pre[j+1] == 0):cells[j] = 1else:cells[j] = 0temp = ''.join(list(map(str, cells)))if temp not in stat:stat[temp] = countpre = cells[:]state.append(pre)else:peroid = count - stat[temp]state = state[stat[temp]:]breakif count == n:return cellsreturn state[(n - count) % peroid]

Reference

1. https://leetcode.com/problems/prison-cells-after-n-days/