4654. 消除游戏【Python实现】
Date:4.8
Key:模拟、链表
思路
维护一个双向链表,记录每个位置的前一个位置和后一个位置。
对于每一轮次操作,用一个队列记录本轮次需要删除的位置,对于每个删除的位置,其可能导致新产生边缘字符,只会出现在这个删除位置的前一个位置和后一个位置,用一个队列记录这些位置,每次删除操作结束之后,对于这些位置进行判断是否为边缘字符,再进行下一轮次的操作。
因为每个点最多只会被删除一次,所以整体的时间复杂度是$O(n)$的。
实现上,注意代码细节,在首尾插入一个非小写字母字符可以让代码变简洁。
代码
from collections import deque
s = input().strip()
n = len(s)
s = '!' + s + '!'
nxt= [0] * (n + 10)
pre = [0] * (n + 10)
visited = [0] * (n + 10)
q = deque([])
def check(x):
if s[nxt[x]] == '!' or s[pre[x]] == '!': return
if s[x] == s[pre[x]] and s[x] != s[nxt[x]]:
q.append(x)
q.append(nxt[x])
if s[x] != s[pre[x]] and s[x] == s[nxt[x]]:
q.append(pre[x])
q.append(x)
def rem(x):
nxt[pre[x]] = nxt[x]
pre[nxt[x]] = pre[x]
for i in range(1, n + 1):
pre[i] = i - 1
nxt[i] = i + 1
for i in range(1, n + 1): check(i)
while True:
T = deque([])
while len(q):
x = q.popleft()
if visited[x]: continue
visited[x] = 1
rem(x)
T.append(pre[x])
T.append(nxt[x])
while len(T):
x = T.popleft()
if visited[x]: continue
check(x)
if len(q) == 0: break
ok = 0
for i in range(1, n + 1):
if not visited[i]:
ok = 1
print(s[i], end = '')
if ok == 0: print('EMPTY')
else: print()