class Solution {
public:
string largestPalindrome(int n, int k) {
}
};
100409. 找出最大的 N 位 K 回文数
给你两个 正整数 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 <= 1051 <= k <= 9原站题解
golang 解法, 执行用时: 161 ms, 内存消耗: 24.5 MB, 提交时间: 2024-10-20 10:13:28
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)
}
cpp 解法, 执行用时: 412 ms, 内存消耗: 92.6 MB, 提交时间: 2024-10-20 10:13:13
class Solution {
public:
string largestPalindrome(int n, int k) {
vector<int> pow10(n);
pow10[0] = 1;
for (int i = 1; i < n; i++) {
pow10[i] = pow10[i - 1] * 10 % k;
}
string ans(n, 0);
int m = (n + 1) / 2;
vector<vector<int>> vis(m + 1, vector<int>(k));
auto dfs = [&](auto&& dfs, int i, int j) -> bool {
if (i == m) {
return j == 0;
}
vis[i][j] = true;
for (int d = 9; d >= 0; d--) { // 贪心：从大到小枚举
int j2;
if (n % 2 && 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(dfs, i + 1, j2)) {
ans[i] = ans[n - 1 - i] = '0' + d;
return true;
}
}
return false;
};
dfs(dfs, 0, 0);
return ans;
}
};
java 解法, 执行用时: 148 ms, 内存消耗: 52.5 MB, 提交时间: 2024-10-20 10:13:00
class Solution {
public String largestPalindrome(int n, int k) {
int[] pow10 = new int[n];
pow10[0] = 1;
for (int i = 1; i < n; i++) {
pow10[i] = pow10[i - 1] * 10 % k;
}
char[] ans = new char[n];
int m = (n + 1) / 2;
boolean[][] vis = new boolean[m + 1][k];
dfs(0, 0, n, k, m, pow10, ans, vis);
return new String(ans);
}
private boolean dfs(int i, int j, int n, int k, int m, int[] pow10, char[] ans, boolean[][] vis) {
if (i == m) {
return j == 0;
}
vis[i][j] = true;
for (int d = 9; d >= 0; d--) { // 贪心：从大到小枚举
int j2;
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, n, k, m, pow10, ans, vis)) {
ans[i] = ans[n - 1 - i] = (char) ('0' + d);
return true;
}
}
return false;
}
}
python3 解法, 执行用时: 3049 ms, 内存消耗: 51.3 MB, 提交时间: 2024-10-20 10:12:47
class Solution:
def largestPalindrome(self, n: int, k: int) -> str:
pow10 = [1] * n
for i in range(1, n):
pow10[i] = pow10[i - 1] * 10 % k
ans = [''] * n
m = (n + 1) // 2
vis = [[False] * k for _ in range(m + 1)]
def dfs(i: int, j: int) -> bool:
if i == m:
return j == 0
vis[i][j] = True
for d in range(9, -1, -1): # 贪心：从大到小枚举
if n % 2 and i == m - 1: # 正中间
j2 = (j + d * pow10[i]) % k
else:
j2 = (j + d * (pow10[i] + pow10[-1 - i])) % k
if not vis[i + 1][j2] and dfs(i + 1, j2):
ans[i] = ans[-1 - i] = str(d)
return True
return False
dfs(0, 0)
return ''.join(ans)