我正在尝试解决整数列表对Kattis的挑战。
for _ in range(int(input())):
operation, elements = input(), int(input())
error = False
if elements <= 0:
input()
print('error')
else:
inp_lst = list(map(int, input().strip('[]').split(',')))
for op in operation:
try:
if op == 'R':
inp_lst.reverse()
elif op == 'D':
inp_lst.pop(0)
except IndexError:
print('error')
error = True
break
if not error:
print(inp_lst)
样本输入:
4
RDD
4
[1,2,3,4]
DD
1
[42]
RRD
6
[1,1,2,3,5,8]
D
0
[]
预期输出:
[2,1]
error
[1,2,3,5,8]
error
我的代码确实得到了正确的输出，但它仍然被标记为错误。我不确定我的解决方案有什么问题。如有任何帮助，不胜感激。
你的解决方案太直接了。反转列表并删除第一个元素是一个O(n)操作，您可能会重复O(len(p))次。显然，O(n * len(p))溶液会超时，并且会被标记为错误。
为了改进解决方案，您需要意识到实际上并不需要反转列表。你可以通过跟踪"行为"的结尾来操纵它。如列表头
这是一个不必要的残酷的编码挑战，看起来很简单，但需要大量的微优化才能通过。
正如在这个答案中提到的，对于初学者来说，你不应该使用"drop"。和";reverse"操作。反转一个列表是O(n)，所以在最坏的情况下，你有一个100k元素的列表，R的操作是100k，你做了10个10个步骤，什么也没有实现。
一个更好的方法是使用deque和布尔值。deque的两端都有O(1)的移除，布尔值在前后之间来回翻转，以确定从哪一边删除元素。如果我们以"反向"结尾状态，打印它反转。现在我们谈到了线性时间，但是对于Python来说，简单的线性时间并不一定足够好，所以我们必须攻击常数因子。
我的下一个尝试是避免deque，而是专注于计算我需要在两端删除的元素数量，然后用切片一次性删除它们。将操作的执行和分析分开可以实现更多的优化。每个测试用例的输入顺序是一个很好的提示:我们收集操作，然后是列表大小n，然后是列表内容。每当列表中的drop多于item时，我们可以避免解析列表并打印error。如果列表中有相同数量的掉落作为项，我们可以输出[]，再次避免解析列表。
这些微优化最终让我通过了考试。这是我的解决方案:
from sys import stdin
def main():
for _ in range(int(next(stdin))):
forward = True
trim_from_front = 0
trim_from_rear = 0
for op in next(stdin):
if op == "R":
forward = not forward
elif op == "n":
break
elif forward:
trim_from_front += 1
else:
trim_from_rear += 1
n = int(next(stdin))
if trim_from_front + trim_from_rear > n:
print("error")
next(stdin)
continue
elif trim_from_front + trim_from_rear == n:
print("[]")
next(stdin)
continue
x = next(stdin)[1:-2].split(",", n - trim_from_rear)
if trim_from_rear > 0:
x.pop()
if trim_from_front > 0:
x = x[trim_from_front:]
if not forward:
x = reversed(x)
print("[", ",".join(x), "]", sep="")
if __name__ == "__main__":
main()
参见:
- 快速Python I/O 为什么Python代码在函数中运行得更快?
所以你的程序有一些不同的问题。首先，正如其他人提到的，您的解决方案非常低效。虽然理论上可行，但你处理这个问题的方法完全错了。你还没有找到"正确的想法"。失败的原因是输出格式错误。
这条线
print(inp_lst)
当不应该有空格时，以逗号分隔的形式打印列表。Kattis逐个字节比较输出，所以即使是意外的'n'也会导致失败。
你是否打印"[]"当列表删除所有元素时?虽然这是你失败的原因，但你不会通过你当前的解决方案，因为你会超时相当快。虽然其他人已经发布了正确的想法和代码，但我建议你不要去看他们来提高你解决问题的能力。