3260. 找出最大的 N 位 K 回文数(2370)

给你两个 正整数 n 和 k。

如果整数 x 满足以下全部条件，则该整数是一个 k 回文数：

  • x 是一个

    回文数

    。

  • x 可以被 k 整除。

以字符串形式返回 最大的 n 位 k 回文数。

注意，该整数 不 含前导零。

示例 1：

输入： n = 3, k = 5

输出： “595”

解释：

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

示例 2：

输入： n = 1, k = 4

输出： “8”

解释：

1 位 k 回文数只有 4 和 8。

示例 3：

输入： n = 5, k = 6

输出： “89898”

提示：

  • 1 <= n <= 10^5
  • 1 <= k <= 9

数位dp，记忆化搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    char res[];
    public String largestPalindrome(int n, int k) {
        res = new char[n];
        // MOD[i]: 10^i % k
        int MOD[] = new int[n+1];
        MOD[0] = 1 % k;
        for (int i = 0; i < n; i++) {
            MOD[i+1] = (MOD[i] * 10) % k;
        }
        int vis[][] = new int[(n+1)/2][10];
        dfs(0, 0, n, k, MOD, vis);
        return new String(res);
    }
    // i：当前数位，mod：当前数字mod k的余数
    public boolean dfs(int i, int mod, int n, int k, int MOD[], int vis[][]) {
        if (i >= (n+1)/2) return mod == 0;
        if (vis[i][mod] == 1) return false;
        for (int j = 9; j >= 0; j--) {
            boolean mid = n % 2 == 1 && i == n/2;
            int next = 0;
            if (mid) next = (mod + MOD[i]*j) % k;
            else next = (mod + (MOD[i]+MOD[n-1-i])*j) % k;
            if (dfs(i+1, next, n, k, MOD, vis)) {
                res[i] = (char)(j+48);
                res[n-1-i] = (char)(j+48);
                return true;
            }
        }
        vis[i][mod] = 1;
        return false;
    }
}

这题也可以递推dp，从中间到起始位置，计算结束后，进行dp回溯，找到最大方案