2025-03-29：找出最大的 N 位 K 回文数。用go语言，给定两个正整数 n 和 k。

一个正整数 x 被称为 k 回文数，当且仅当它满足以下所有条件：

1.x 是一个回文数。

2.x 可以被 k 整除。

请以字符串的形式返回最大的 n 位 k 回文数。需要注意的是，该数不能有前导零。

1 <= n <= 100000。

1 <= k <= 9。

输入： n = 3, k = 5。

输出： “595”。

解释：

595 是最大的 3 位 k 回文数。

题目来自leetcode3260。

大体步骤如下：

1.首先定义一个长度为 N 的数组 pow10，用于存储 10 的幂，以便后续计算。

2.接着创建一个长度为 N 的答案数组 ans，初始化为 0。

3.计算回文数的中间位置，定义一个二维数组 vis 用于记录访问状态。

4.定义深度优先搜索函数 dfs，依次尝试填充回文数的各位数字。

5.在 dfs 函数中，采用贪心算法，从大到小枚举可填充的数字。

6.递归地尝试填充各位数字，直到得到最大的回文数。

7.执行 main 函数，给定输入参数 n=3 和 k=5，调用largestPalindrome(n, k)得到结果并打印输出。

总的时间复杂度为 O(N * 10)，其中 N 为数字长度，10 为数字排列的可能性。

总的额外空间复杂度为 O(N * K)，其中 N 为数字长度，K 为除数范围。

Go完整代码如下：

package main

import (
	"fmt"
)

func largestPalindrome(n, k int) string {
	pow10 := make([]int, n)
	pow10[0] = 1
	for i := 1; i < n; i++ {
		pow10[i] = pow10[i-1] * 10 % k
	}

	ans := make([]byte, n)
	m := (n + 1) / 2
	vis := make([][]bool, m+1)
	for i := range vis {
		vis[i] = make([]bool, k)
	}
	var dfs func(int, int) bool
	dfs = func(i, j int) bool {
		if i == m {
			return j == 0
		}
		vis[i][j] = true
		for d := 9; d >= 0; d-- { // 贪心：从大到小枚举
			var j2 int
			if n%2 > 0 && i == m-1 { // 正中间
				j2 = (j + d*pow10[i]) % k
			} else {
				j2 = (j + d*(pow10[i]+pow10[n-1-i])) % k
			}
			if !vis[i+1][j2] && dfs(i+1, j2) {
				ans[i] = '0' + byte(d)
				ans[n-1-i] = ans[i]
				return true
			}
		}
		return false
	}
	dfs(0, 0)
	return string(ans)
}

func main() {
	n := 3
	k := 5
	result := largestPalindrome(n, k)
	fmt.Println(result)
}

Python3完整代码如下：

# -*-coding:utf-8-*-

def largest_palindrome(n, k):
    pow10 = [1] * n
    for i in range(1, n):
        pow10[i] = (pow10[i - 1] * 10) % k

    ans = ['0'] * n
    m = (n + 1) // 2
    vis = [[False] * k for _ in range(m + 1)]

    def dfs(i, j):
        if i == m:
            return j == 0
        if vis[i][j]:
            return False
        vis[i][j] = True
        for d in range(9, -1, -1):  # 贪心：从大到小枚举
            if i == m - 1 and n % 2 > 0:  # 正中间
                j2 = (j + d * pow10[i]) % k
            else:
                j2 = (j + d * (pow10[i] + pow10[n - 1 - i])) % k
            if not vis[i + 1][j2] and dfs(i + 1, j2):
                ans[i] = str(d)
                ans[n - 1 - i] = ans[i]
                return True
        return False

    dfs(0, 0)
    return ''.join(ans)

# 示例用法
n = 3
k = 5
result = largest_palindrome(n, k)
print(result)