我的博客

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。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
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)

评论无需登录,可以匿名,欢迎评论!