问题：程序必须接受整数N和长度为N和整数X的整数数组，程序应打印由数组的整数形成的最小回文，该回文应大于整数X
边界条件：
1<=N<=10
1<=X<=10^8
Maximum Time Limit : 500 ms
我的代码：
import sys
def Next_smallest_Palindrome(num,Num_List):
numstr = str(num)
for i in range(num+1,sys.maxsize):
if str(i) == str(i)[::-1]:
h=0
for k in str(i):
if int(k) in Num_List :
h+=1
if h == len(str(i)):
return i
a=int(input())
Num_List=sorted(list(map(int,input().split())),reverse = True)
Number=int(input())
print(Next_smallest_Palindrome(Number,Num_List))
我的代码运行良好，它满足所有测试用例。我在代码中使用的逻辑是我正在迭代从N+1到sys.maxsize的数字，检查它们是否是回文的，如果是回文的，那么应该检查整数数组中是否存在数字中的数字如果它是真的，那么它将返回数字。
我的问题是，有没有更好的方法来解决这个问题，而不是像brute force approach那样循环
测试用例：
Input:
3
2 4 0
567
Output:
2002
Input:
4
1 2 3 4
12543
Output:
13131
第二个示例的输出不应该是 12421 吗？
我的代码有点混乱，但这就是我能想到的：
请注意，您还可以修改代码以对列表 L 进行排序，这将产生更快的结果，因为您可以使用二叉搜索来检查数字是否在 L 中，使用 L[0] 而不是 min(L(...它将把复杂度从O(N.len(X((更改为O(len(X(.log(N((。
'''
The output should be greater than X, therefore
number of digits of output >= number of digits of X
if number of digits of output = number of digits of X:
most significant digit of ouput = most significant digit of X (Case 2.a)
most significant digit of ouput > most significant digit of X (Case 2.b)
if this is not possible, then
number of digits of output > number of digits of X:
most significant digit of output = smallest integer in list different than 0
Also note: when we fill the first digit of the output,
we also fill the last digit with the same value
we are therefore guaranteed to obtain a palindrome
After filling out the first and last digits,
we fill the middle part recursively
if the output we already have is guaranteed to be bigger than X
(left side of output bigger than that of X),
we fill the remaining digits in the middle with the minimum of L
When we have one digit remaining to fill,
we can either fill it equal to the digit in X (Case I),
or greater than the digit in X (Case II)
'''
def smallestPalindromeGreaterThanX(L, X):
def recursive(o, L, X, case):
if not X: #X is empty
return o + o[::-1]
if len(X) == 1: #last digit to fill
#Case I: right side of output > right side of X
#digit left to fill of output can be equal to digit of X
if not case:
if int(X) in L:
return o + int(X) + o[::-1]
else:
bigger = min(i for i in L if i > int(X))
return o + str(bigger) + o[::-1]
else:
#Case II: right side of output <= right side of X
minList = [i for i in L if i > int(X)]
if len(minList) > 0:
bigger = min(minList)
return o + str(bigger) + o[::-1]
else:
return -1
if int(X[0]) in L:
return recursive(o + X[0], L, X[1:-1], int(o[::-1]) <= int(X[-len(o):]))
else:
#filled output with digit bigger than that of X
#fill remaining with minimum of L
bigger = min(i for i in L if i > int(X[0]))
return o + str(bigger) + str(minimum)*(len(X)-2-2*len(o)) + str(bigger) + o
minimum, index = min((minimum, index) for (index, minimum) in enumerate(L))
maximum = max(L)
#Case 1: a list only containing zero, therefore no solution
if L[0] == 0 and len(L) == 1: return -1
#Case 2: output will have same length as X
mostSig = int(str(X)[0]) #most significant digit of X
#Case 2.a: most significant digit of output = most significant digit of X
minList = [int(i) for i in str(X)[1:-1]]
if mostSig in L and len(minList) == 0 or (maximum >= min(minList)):
#mostSig exists in L and it can produce an output greater than X
result = -1
result = recursive(str(mostSig), L, str(X)[1:-1], mostSig <= int(str(X)[-1]))
if not result == -1: return int(result)
#Case 2.b: most significant digit of output > most significant digit of X
minList = [i for i in L if i > mostSig]
if not len(minList) == 0: #bigger than mostSig exists in L
biggerThanMostSig = min(minList)
return int(str(biggerThanMostSig)
+ str(minimum) * (len(str(X))-2) #fill with smallest digit, to have same length as X
+ str(biggerThanMostSig))
#Case 3: output will have length greater than that of X
if not minimum == 0:
smallestNonZero = minimum
else:
smallestNonZero = min(L[:index] + L[index+1:])
return int(str(smallestNonZero)
+ str(minimum) * (len(str(X))-1) #length greater than that of X by 1
+ str(smallestNonZero))
print(smallestPalindromeGreaterThanX([2,4,0], 567))
print(smallestPalindromeGreaterThanX([1,2,3,4], 12354))