需要备用Python列表反向解决方案

Question

我今天有个工作面试。在此期间，我被要求写下一个算法，该算法将反转一个列表。首先，我使用reversed()方法提供了答案：

    x = [1,2,3,4,5]
    y = reversed(x)
    for i in y:
        print i

进行面试的高级开发人员问我是否知道另一种方法，在此基础上，我写下了另一种已知的切片方法：

   x = [1,2,3,4,5]
   y = x[::-1]

不幸的是，他也对这个解决方案不满意，并要求我考虑另一个解决方案。几分钟后，我说我想不出更好的办法了。他说，这对他们的标准来说还不够好。

我完全同意他的观点，在我的代码上进行更多的练习是没有问题的。我的问题是，我不知道的更好的解决方案是什么，如果有的话。还有没有别的“程序员”way...Only我想到的另一件事是递归，不过我是在面试结束后才想到的。谢谢。

Answer 1

你的两个答案在python方面都很好，所以面试官一定是在要求你实现你自己的方法：

使用递归：

def recur_rev(l):
    return recur_rev(l[1:]) + l[:1] if l else l

或从l -1的长度开始并反向进行的列表comp和range：

l = list(range(100))

print([l[ind] for ind in range(len(l)-1,-1,-1)])

使用itertools.count：

from itertools import count
cn = count(len(l) -1, -1)

print([l[next(cn)] for ele in l])

为了提高效率，请使用生成器表达式：

rev  = (l[next(cn)] for ele in l)

for ele in rev:
    print(ele)

或者使用map：

print(list(map(l.__getitem__,range(len(l)-1,-1,-1)))) # list needed for python3

[99, 98, 97, 96, 95, 94, 93, 92, 91, 90, 89, 88, 87, 86, 85, 84, 83, 82, 81, 80, 79, 78, 77, 76, 75, 74, 73, 72, 71, 70, 69, 68, 67, 66, 65, 64, 63, 62, 61, 60, 59, 58, 57, 56, 55, 54, 53, 52, 51, 50, 49, 48, 47, 46, 45, 44, 43, 42, 41, 40, 39, 38, 37, 36, 35, 34, 33, 32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

如果没有对地图的列表调用，我们将获得一个可以在python3中迭代的地图对象，您可以在python2中使用itertools.imap来实现类似的结果

Answer 2

我猜你的面试官想听这样的话：

恢复列表的一种简单方法是找出它的长度，然后从len-1向下迭代到0，并将第i个元素附加到结果中。这种方法可以很好地处理真实列表，但我们如何还原生成器，即长度未知且无法找到的生成器？(优秀的pythonistas使用生成器和收益，而不是列表和返回)。

在这里，我们需要一个称为“栈”的数据结构。堆叠就像，嗯，一堆东西，就像盘子，放在彼此的顶部。

​

​

你放在最后的东西先出来，先放的东西最后出来。所以，我们的策略是这样的：

• 当存在项目时，将每个项目放入堆栈
• 当堆栈不为空时，从堆栈中弹出项目并将其返回

可以使用列表在Python语言中对堆栈进行编程，其中.append将一项放在堆栈的顶部，而.pop删除堆栈中的最后一项：

def reverse(it):
    stack = []
    for item in it:
        stack.append(item)
    while stack:
        yield stack.pop()

当然，Python已经有了一个内置堆栈，它就是调用框架堆栈。我们可以使用它，而不是上面模拟的那个，这将导致我们得到以下递归解决方案：

def reverse(it):
    head = next(it)
    for item in reverse(it):
        yield item
    yield head

在python3中，这甚至更优雅：

def reverse(it):
    head = next(it)
    yield from reverse(it)
    yield head

同样，这适用于任意迭代器，其长度在调用时是未知的。

Answer 3

一个可以很容易移植到其他语言的简单算法是：

x = [1,2,3,4,5]
y = []
for i in len(x):
  y.append(x[len(x) - 1 - i])

或者使用迭代器。这可以很容易地移植到您不知道长度的链表中使用：

x = [1,2,3,4,5]
y = []
x_iterator = iter(x)
try:
  while (1):
    y.insert(0, x_iterator.next())
except:
  print y

或者是一个带有insert的pythonic版本：

x = [1,2,3,4,5]
y = []
for elem in x:
  y.insert(0, elem)