文章作者：Tyan
博客：noahsnail.com ?|? CSDN ?|? 簡(jiǎn)書

1. Description

Prison Cells After N Days

2. Solution

解析：Version 1，根據(jù)變換規(guī)則可知，第一位和最后一位總是0，因此只有中間6位數(shù)在變，最大可能的變換周期為2^6。因此只要記錄變換周期，因此周期中的所有狀態(tài)就可得出變換結(jié)果，使用字典stat來判斷每次變換是否與之前的重復(fù)，列表state記錄狀態(tài)變化，當(dāng)出現(xiàn)重復(fù)狀態(tài)時(shí)，計(jì)算變換的周期peroid，以及一個(gè)周期的狀態(tài)變化，如果沒出現(xiàn)周期，則直接返回變換后的結(jié)果，如果出現(xiàn)了，則返回計(jì)算后的狀態(tài)。

• Version 1

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

Reference

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