leetcode 957. N 天后的牢房 Prison Cells After N Days

目录

1. 题解

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/prison-cells-after-n-days
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

把 list 转换为 byte。两次移位然后按位异或后取反。

40 ms 超越 100% python。

class Solution:
    @staticmethod
    def bit2list(x):
        i = 128
        c = []
        while i > 0:
            if x & i > 0:
                c.append(1)
            else:
                c.append(0)
            i >>= 1
        return c

    def prisonAfterNDays(self, cells: [int], N: int) -> [int]:
        x = 0
        idx = 0
        j = 1
        for i in range(8):
            if cells[7-i] == 1:
                x = x | j
            j <<= 1
        mp = {}
        mp[x] = idx
        while idx < N:
            y = x << 1 & 0b011111111
            z = x >> 1
            x = ~(y ^ z) & 0b01111110
            idx += 1
            if x in mp: 
                break
            else: 
                mp[x] = idx
        if idx < N:
            N = (N - mp[x]) % (idx - mp[x])
            idx = 0
            while idx < N:
                y = x << 1 & 0b011111111
                z = x >> 1
                x = ~(y ^ z) & 0b01111110
                idx += 1
        return self.bit2list(x)