Leetcode 3646. Next Special Palindrome Number

• Leetcode 3646. Next Special Palindrome Number
  • 1. 解题思路
  • 2. 代码实现

• 题目链接：3646. Next Special Palindrome Number

1. 解题思路

这一题我的思路的话就是首先计算出所有$10^{17}$以下的所有满足条件的特殊回文数字，然后根据具体的$n$进行查找即可。

而要涉及如何获取所有$10^{17}$以下的特殊回文数字，我们就是使用一个迭代的算法即可，我们只要考察每一个数字的使用情况，然后考察单侧的可能排序方法，然后将其返回即可。

2. 代码实现

给出python代码实现如下：

def get_special_palindrome():even = [2, 4, 6, 8]odd = [1, 3, 5, 7, 9]ans = set()def get_candidates(idx, candidates):nonlocal ansif len(candidates) > 8:returnif idx < 4:get_candidates(idx+1, candidates)get_candidates(idx+1, candidates + [even[idx]] * (even[idx]//2))else:if len(candidates) > 0:for purb in permutations(candidates):sub = "".join([str(x) for x in purb])ans.add(int(sub + sub[::-1]))for num in odd:dup = [str(num)] * (num//2)candi = candidates + dupif len(candi) > 8:breakfor purb in permutations(candi):sub = "".join([str(x) for x in purb])ans.add(int(sub + str(num) + sub[::-1]))returnget_candidates(0, [])return sorted(ans)SPECIAL_PALINDROME = get_special_palindrome()class Solution:def specialPalindrome(self, n: int) -> int:idx = bisect.bisect_right(SPECIAL_PALINDROME, n)return SPECIAL_PALINDROME[idx]

提交代码评测得到：耗时0ms，占用内存18.36MB。