如何检查序列是否可以变成回文

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

Answer 2

计算每个值的出现次数.然后检查奇数的数量是零还是一.无需对列表进行排序.这适用于任何值列表.

from collections import Counter

def can_be_palindrome(data):
    odd = (c % 2 for c in Counter(data).values())
    any(odd)  # skip first odd, if present at all
    return not any(odd)  # ensure no more odds

print(can_be_palindrome([0, 99, 97, 97, 99, 100, 100, 0]))  # only even counts, true
print(can_be_palindrome([0, 99, 97, 97, 99, 100, 100, 0, 1]))  # one odd count, true
print(can_be_palindrome([0, 99, 97, 97, 99, 100, 100, 0, 1, 2]))  # two odd counts, false
print(can_be_palindrome('abcabcd'))  # true
print(can_be_palindrome(['a', 'b', 'a', 1, 1])  # true

Answer 3

快速的(或者​​我认为):使用字典来计算odd值.将值存储为字典中的键,True如果键出现奇数次,则值为False偶数.最后返回True,表示.values()只有0或1个True元素(也就是说只有0或1个元素出现奇数次).

迭代器以短路方式工作.第一个any将True在第一个True满足时返回,否则它将扫描整个迭代器.然后我们重新运行any(odd_iter)- True如果迭代器产生另一个 True(也就是奇数值),则返回.如果第一个any用尽了迭代器,那么第二个any将False完全返回.最后,我们否定此返回值并从函数返回它.

def check_palindrome_sequence(sequence):
    odds = {}
    for i in sequence:
        try:
            odds[i] ^= True
        except KeyError:
            odds[i] = True

    odd_iter = iter(odds.values())
    any(odd_iter)
    return not any(odd_iter)

A = [0, 99, 97, 97, 99, 100, 100, 0]
print(check_palindrome_sequence(A))  # True

A = [0, 99, 97, 97, 99, 100, 100, 0, 1]    
print(check_palindrome_sequence(A))  # True

A = [0, 99, 97, 97, 99, 100, 100, 0, 1, 2]
print(check_palindrome_sequence(A))  # False

Python 2.7的时间安排:

In [1]: %timeit antti(ls)
1 loops, best of 3: 128 ms per loop

In [2]: %timeit davidism(ls)
10 loops, best of 3: 103 ms per loop

In [3]: %timeit leek(ls)
10 loops, best of 3: 42.1 ms per loop

所有3的数据都相同:

ls = list(range(100000))
ls *= 2
ls += [ 1, 2 ]
random.shuffle(ls)

在Python 3上的时间,数据相同:

In [1]: %timeit leek(ls)
10 loops, best of 3: 37.4 ms per loop

In [2]: %timeit antti(ls)
10 loops, best of 3: 89.3 ms per loop

In [3]: %timeit davidism(ls)
10 loops, best of 3: 52 ms per loop

韭菜是完全随机的最佳整体.nettux的答案是以二次方式放慢速度,必须花一分钟才能获得100000*2 + 2个元素,而且我没有耐心等待时间.

对于作为回文的小值,韭菜几乎是胜利

In [1]: %timeit leek(ls)                         
100000 loops, best of 3: 2.21 µs per loop

In [2]: %timeit antti(ls)
100000 loops, best of 3: 5.52 µs per loop

In [3]: %timeit davidism(ls)
100000 loops, best of 3: 7.45 µs per loop