Python

Question

我为任务编写代码，但收到错误：测试系统超出时间限制。我需要获得如何更快更精确地编写此代码的建议

代码：

# input
n = int(input())
seq = input()
pairs = []
seq = list(seq)

# find pairs
counted = []
for i, item in enumerate(seq):
    for j, num in enumerate(seq):
        if (i != j) and (item == num):
            if (i not in counted) and (j not in counted):
                pairs.append((item, num))
                counted.append(i)
                counted.append(j)

# remove pairs from seq
for pair in pairs:
    seq.remove(pair[0])
    seq.remove(pair[1])

# create a palindrome

start = []
end = []

pairs = sorted(pairs)
pairs = list(reversed(pairs))

for item in pairs:
    start.append(item[0])
    end.append(item[1])

end = list(reversed(end))

if len(seq) != 0:
    seq = [int(item) for item in seq]
    max_el = list(sorted(seq))[-1]
    start.append(max_el)

final_s = start + end
# output
output = ''.join([str(item) for item in final_s])
print(output)

Answer 1

这是一个有趣的问题，而且并非完全微不足道。首先，我认为输入只能是单数的奇数，否则不能组成回文。例如，11333 是有效输入，但 113334 不是（3 和 4 都是奇数）。还应该注意的是，我们不能只转储输出中间的 odd-count 数字。例如，我们可能会想做 1335551 -> 3155513，但正确答案（最大回文）是 5315135.

考虑到这些限制，这是我尝试的解决方案。它使用 collections.Counter 来计算数字对，然后按降序排序并镜像以创建输出。可能的 odd-count 数字是通过将其视为单个数字（进入输出的中间）加上一串成对数字来处理的。

我针对 10^5 位数字的输入大小对其进行了测试，它似乎并没有花费太多时间。

from collections import Counter

def biggest_pal(n):
    c = Counter(str(n))
    s = ''
    evens = {k: v for k, v in c.items() if not v % 2}
    odds = {k: v for k, v in c.items() if v % 2}
    vodd = ''
    if len(odds) > 1:
        raise ValueError('Invalid input')
    elif odds:
        vodd, nodd = odds.popitem()
        if nodd > 1:
            evens[vodd] = nodd - 1
    for k, v in sorted(evens.items(), key=lambda p: -int(p[0])):
        s += k * int(v/2)
    return s + vodd + s[::-1]

一些测试输入：

biggest_pal(112)  # 121
biggest_pal(1122)  # 2112
biggest_pal(1234123)  # 3214123
biggest_pal(1331555)  # 5315135
biggest_pal(112212)  # ValueError: invalid input

Python - 优化代码以查找可以由给定数字组成的最大回文数

Python - Optimize code for finding the largest palindrome number that can be formed from the given digits

sorting

algorithm

performance