英文:
Code challenge: Can the guards of the stadium guard all gates
问题
这是您提供的代码挑战的翻译结果：
> 有26个大写英文字母的门，从A到Z进行编号。每个门的门在第一个人进入之前打开，并在最后一个应该通过该门进入的客人到达后关闭。不能同时进入两名客人。为了正确检查一个门，应该为其分配一名安全员。体育场里有'k'名这样的保安，所以如果打开的门多于'k'个，其中一个将被留下来没有保安。请注意，保安不能离开他的岗位，直到他守卫的门关闭。我们能否检查是否有多于'k'个门同时打开的时刻？从条形码扫描中，我们知道持票人的进场顺序。
>
> 输入：
> * 人数 = 5
> * 保安数 (k) = 1
> * 第i个客人使用的门: AABBB
>
> 输出: NO
>
> 输入：
> * 人数 = 5
> * 保安数 (k) = 1
> * 第i个客人使用的门: ABABB
>
> 输出: YES
我尝试使用双端队列（deque）来存储不同于前一个字母的输入字母，并弹出直到重复相同的字母。但未能获得期望的输出。这是我尝试的代码：
from collections import deque
def solve(people, k, gate):
stack = deque() # 用于跟踪打开的门的堆栈
counter = 0 # 打开的门的计数器
for gate in gate_usage:
if len(stack) == 0 or stack[-1] == gate:
stack.append(gate)
else:
while len(stack) > 0 and stack[-1] != gate:
stack.pop()
counter += 1
if counter > k:
return "NO"
return "YES"
no_of_people = 5
k = 1
gate_usage = "ABABB"
print(solve(no_of_people, k, gate_usage))
英文:
I am looking at this code challenge:
> There are 26 Gates enumerated with the uppercase English alphabet from A to Z. The door of each gate is opened right before the first person enters and closed right after the arrival of the last guest that should enter through this gate. No two guests can enter the stadium simultaneously. For a gate to be properly checked, a security guard should be assigned to it. There are 'k' such guards in the stadium, so if there are more than 'k' gates opened, one of them is going to be left unguarded. Note that a guard can't leave his post until the gate he is guarding is closed. Can we check if there was a moment when more than 'k' doors were opened? From the barcode scanning, we know the order in which the people having tickets entered.
>
> Input:
> * No of people = 5
> * No of guards (k) = 1
> * Gate used by ith guest: AABBB
>
> Output: NO
>
> Input:
> * No of people = 5
> * No of guards (k) = 1
> * Gate used by ith guest: ABABB
>
> Output: YES
I tried using deque to store the incoming alphabet is different from the previous alphabet and pop until the same alphabet is repeated. Not giving desired output. This is the code I tried:
from collections import deque
def solve(people, k, gate):
stack = deque() # Stack to track opened gates
counter = 0 # Counter for opened gates
for gate in gate_usage:
if len(stack) == 0 or stack[-1] == gate:
stack.append(gate)
else:
while len(stack) > 0 and stack[-1] != gate:
stack.pop()
counter += 1
if counter > k:
return "NO"
return "YES"
no_of_people = 5
k = 1
gate_usage = "ABABB"
print(solve(no_of_people, k, gate_usage))
答案1
得分: 1
以下是翻译好的代码部分：
def solve(k, gate_usage):
last = {gate: time
for time, gate in enumerate(gate_usage)
}
first = {gate: time
for time, gate in reversed(list(enumerate(gate_usage)))
}
for time, gate in enumerate(gate_usage):
if time == first[gate]:
k -= 1
if k < 0:
return "YES"
if time == last[gate]:
k += 1
return "NO"
# Example runs
print(solve(2, "EAEBACDBDB")) # NO
print(solve(2, "EAEBADCBDB")) # YES
英文:
A solution is to gather for each gate which is its first use and its last use (the index in the input string is the time dimension). Then iterate the time points in order and when that time has a first use of a gate, decrease 𝑘 (the available guards), and when that time has a last use of a gate, increase 𝑘. If ever 𝑘 becomes negative we have an overrun and should return "YES".
Implementation:
def solve(k, gate_usage):
last = { gate: time
for time, gate in enumerate(gate_usage)
}
first = { gate: time
for time, gate in reversed(list(enumerate(gate_usage)))
}
for time, gate in enumerate(gate_usage):
if time == first[gate]:
k -= 1
if k < 0:
return "YES"
if time == last[gate]:
k += 1
return "NO"
# Example runs
print(solve(2, "EAEBACDBDB")) # NO
print(solve(2, "EAEBADCBDB")) # YES
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论