主页 / coding / 问题 / 79495292
Accepted
octaviustheking
Asked: 2025-03-09 09:47:49 +0800 CST

有什么方法可以加快这个速度吗？

  • 772

https://open.kattis.com/problems/lyklagangriti?editresubmit=16843522 这个问题基本上就是你输入密码的地方。每次输入中出现 L，光标就会“移动”到左边，右边也是一样，当出现 B 时，你就删除你所在的字符。

text = input()
chars = list(text)
cursor = 0
password = []
for char in chars:
    if char == 'L':
        cursor -= 1
    elif char == 'R':
        cursor += 1
    elif char == 'B':
        password.pop(cursor - 1)
        cursor -= 1
    else:
        password.insert(cursor, char)
        cursor += 1

print(*password, sep='')

我正在 Kattis 上解决这个问题，到目前为止，我已经通过了很多测试用例，但我似乎超出了测试组 4 和 5 的时间限制。有没有什么方法可以加快这个代码的速度？

python

2 个回答

  1. Best Answer

    我正在解决这个问题，我需要用光标移动来处理字符串：

    • 'L'向左移动光标

    • 'R'向右移动

    • 在光标位置插入其他字符

    优化代码：

    from sys import stdin

text = stdin.readline().strip()
left = []
right = []

for char in text:

    if char == 'L':
        if left:
            right.append(left.pop())
    elif char == 'R':
        if right:
            left.append(right.pop())
    elif char == 'B':
        if left:
            left.pop()
    else:
        left.append(char)

print("".join(left + right[::-1]))

    这使用两个堆栈来有效地模拟游标

    • 2

  2. 由于 Kattis 问题陈述，您可以删除健全性检查，因为您知道所做的任何索引都将始终有效。

    因此，您所需要的只是：

    text = input()
left = list(text)
right = list(text)
lp = 0
rp = 0
for c in text:
    match c:
        case 'L':
            lp -= 1
            right[rp] = left[lp]
            rp += 1
        case 'R':
            rp -= 1
            left[lp] = right[rp]
            lp += 1
        case 'B':
            lp -= 1
        case _:
            left[lp] = c
            lp += 1

print("".join(left[:lp] + right[:rp][::-1]))
    • 0

相关问题