python-3.x - 缩短Python3中Stack的使用时间

Question

我正在处理一个编码问题。

https://www.acmicpc.net/problem/1406

我已经为此写了一个解决方案，

front = []
back = []

word = input()
count = int(input())

for a in word:
    front.append(a)

for i in range(count):
    command = input().split()
    if command[0] == "P":
        front.append(command[1])
    elif command[0] == "L":
        if front:
            back.append(front.pop())
    elif command[0] == "D":
        if back:
            front.append(back.pop())
    else:
        if front:
            front.pop()

while (back):
    front.append(back.pop())

print(''.join(map(str, front)))

但是，我在提交时总是收到超时错误。我如何更改某些内容以在 Python 中更快地运行此代码？或者这是语言的固有问题？

Answer 1

假设您有一百万个字符和两百万个命令。

1. 您需要先迭代一百万个字符并创建一个非常大的数组。
2. 对于每个 L 和 D 操作，您都需要弹出和推送。在此示例中，您执行了将近 200 万次。
3. 在边缘情况下，当我们只进行 L 操作时，您将不得不迭代整个 back 并将其附加到 front

我敢打赌所有 3 个案例都经过了测试。

您可能总是尝试使用双端队列来提高性能 https://docs.python.org/2/library/collections.html#collections.deque

但我建议根本不要使用列表。您只需对 word 进行操作并记住当前光标所在的索引即可。