python - 如何检查一个序列是否可以变成回文

Question

我必须找出一个列表是否可以是回文。我程序的第一部分对列表进行排序。

A = [0, 99, 97, 97, 99, 100, 100, 0]
# sorted:
B = [0, 0, 97, 97, 99, 99, 100, 100]

这个列表可以是回文，因为它可以重新排序为:

[0, 97, 99, 100, 100, 99, 97, 0]

如果列表可以是回文，我编写了以下代码以返回 True。

i=0
counter = 0

while i<len(B):
    if i+1 < len(B):
        if B[i]==B[i+1]:
            print(B[i],B[i+1])
            i+=2
        else:
            i+=1
            counter += 1
    else:
        i+=1

if counter<2:
    return True
return False

但是，如果我测试列表 [0, 99, 97, 97, 99, 100, 100, 0, 1]，它会进入一个看起来像无限循环的东西。如何正确检查列表是否可能是回文？

Answer 1

当我们遍历 B 时，我们可以使用一个集合来跟踪到目前为止哪些元素具有奇数(在这里使用一个集合比列表快得多):

odds = set()
for i in B:
    if i in odds:
        odds.remove(i)
    else:
        odds.add(i)

然后如果odds的长度是0或1，打印True。否则打印False。

print len(odds) <= 1 # prints the value you're looking for

正如@Antti 所指出的，如果您正在优化性能(大约 20% 的速度提升)，可以通过在循环之外进行属性查找来加快速度:

odds = set()
remove = odds.remove
add = odds.add
for i in B:
    if i in odds:
        remove(i)
    else:
        add(i)
print len(odds) <= 1