Leetcode 3260. Find the Largest Palindrome Divisible by K

• Leetcode 3260. Find the Largest Palindrome Divisible by K
  • 1. 解题思路
  • 2. 代码实现

• 题目链接：3260. Find the Largest Palindrome Divisible by K

1. 解题思路

这一题的话首先我们可以快速给出几个简单情况的答案：

1. 如果$k=1$，那么显然返回$n$个$9$即可
2. 如果$k=2$，那么首尾用$8$，其他给出$9$即可；
3. 如果$k=4$，那么头尾的两位均用$88$，其他给出$9$即可；
4. 如果$k=8$，那么头尾的三位均用$888$，其他给出$9$即可；
5. 如果$k=5$，那么首尾用$5$，其他给出$9$即可；

而对于其他的情况，暂时没啥好的思路，因此给出了一个暴力的解法，就是先通过一个迭代由大到小给出所有的回文序列，然后手动写一个除法函数判断一下是否可以整除即可。

2. 代码实现

给出python代码实现如下：

class Solution:def largestPalindrome(self, n: int, k: int) -> str:def dfs(n, start_with_even):if n == 0:yield ""elif n == 1:if start_with_even:for i in range(8, -1, -1):yield str(i)else:for i in range(9, -1, -1):yield str(i)else:m = n // 2for num1 in dfs(m, start_with_even):for num2 in dfs(n-m, False):yield num1 + num2def get_palindromic(n, start_with_even):r = n % 2m = n // 2num_iter = dfs(m, start_with_even)for num in num_iter:if r == 0:yield (num + num[::-1]).strip("0")else:for i in range(9, -1, -1):yield (num + str(i) + num[::-1]).strip("0")return ""def is_divisible(num, k):if k == 1:return Truer = 0for d in num:r = (r*10 + int(d)) % kreturn r == 0if k == 1:return "9" * nelif k == 2:if n <= 2:return "8" * nelse:return "8" + "9" * (n-2) + "8"elif k == 4:if n <= 4:return "8" * nelse:return "88" + "9" * (n-4) + "88"elif k == 8:if n <= 6:return "8" * nelse:return "888" + "9" * (n-6) + "888"elif k == 5:if n <= 2:return "5" * nelse:return "5" + "9" * (n-2) + "5"palindromic_iter = get_palindromic(n, k % 2 == 0)for num in palindromic_iter:if is_divisible(num, k):return numreturn "-1"

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