函数结果因运行而异

Question

我有以下函数通过删除和重新排序字符生成最长的 palindrome 字符串：

from collections import Counter


def find_longest_palindrome(s):
    count = Counter(s)
    chars = list(set(s))
    beg, mid, end = '', '', ''

    for i in range(len(chars)):
        if count[chars[i]] % 2 != 0:
            mid = chars[i]
            count[chars[i - 1]] -= 1
        else:
            for j in range(0, int(count[chars[i]] / 2)):
                beg += chars[i]

    end = beg
    end = ''.join(list(reversed(end)))

    return beg + mid + end


out = find_longest_palindrome('aacggg')
print(out)

我通过 'translating' this example 从 C++

得到了这个函数

每当我运行我的函数时，我似乎随机得到以下输出之一：

a
aca
agcga

本例中正确的是 'agcga'，因为这是输入字符串 'aacggg'.

的最长回文

任何人都可以建议为什么会发生这种情况以及如何使函数可靠地 return 最长回文？

P.S。 C++代码没有这个问题。

Answer 1

您的代码取决于 list(set(s)) 的顺序。

但是集合是无序的。

在 CPython 3.4-3.7 中，字符串集的特定顺序取决于字符串的哈希值，这些值在启动时明确随机化，因此您每个运行.

得到不同的结果

你在 C++ 中看不到这个的原因是 C++ set class 模板不是无序集，而是有序集（基于二叉搜索树，而不是一个散列 table)，所以你总是在每个运行.

中得到相同的顺序

您可以在 Python 中通过在集合上调用 sorted 来获得相同的行为，而不是仅仅按照它的顺序将其复制到列表中。

但是代码还是不对；它恰好适用于某些示例，因为排序顺序恰好为您提供了重复次数最多的字符。但这显然不是一般情况，所以你需要重新考虑你的逻辑。

您的翻译中引入的最明显的区别是：

count[ch--]--;

... 或者，由于您是通过索引而不是直接遍历字符，所以更像是：

count[chars[i--]]--;

无论哪种方式，这都会减少当前字符的计数，然后减少当前字符，以便循环将在下一次通过时重新检查相同的字符。你已经把它变成了完全不同的东西：

count[chars[i - 1]] -= 1

这只是减少前一个字符的计数。

在 for-each 循环中，您不能仅更改循环变量并对循环产生任何影响。要完全复制 C++ 行为，您需要切换到 while 循环，或者在 for 循环内放置一个 while True: 循环以获得相同的 "repeat the same character" 效果.

当然，您必须减少当前字符的计数，而不是减少您永远不会再看到的前一个字符的计数。

for i in range(len(chars)):
    while True:
        if count[chars[i]] % 2 != 0:
            mid = chars[i]
            count[chars[i]] -= 1
        else:
            for j in range(0, int(count[chars[i]] / 2)):
                beg += chars[i]
            break

当然你可以简化这个——从循环 for ch in chars: 开始，但是如果你考虑两个循环如何协同工作的逻辑，你应该能够看到如何删除整个关卡这里的缩进。但这似乎是对您的代码所做的最小更改。

请注意，如果您进行此更改，而没有 sorted 更改，则当正确答案不明确时会随机选择答案——例如，您的示例将给出 agcga 一次，然后 aggga下次

添加 sorted 将使该选择保持一致，但同样具有任意性。

函数结果因运行而异

Function result varies on each run

python

palindrome

函数结果因 运行 而异

Function result varies on each run

python

palindrome

函数结果因运行而异