Kimi K2.6 思考 LeetCode 3260. 找出最大的 N 位 K 回文数 Java实现

LeetCode 3260 要求找出最大的 n 位 K 回文数（可被 k 整除的回文数）。由于 `k ≤ 9` 而 `n ≤ 10^5`，最优雅的解法是按 k 分类讨论找规律，这样时间复杂度为 O(n)，空间复杂度为 O(1)（除结果字符串外）。

以下是基于题解规律总结的 Java 实现：

```java
class Solution {
public String largestPalindrome(int n, int k) {
// k = 1, 3, 9: 所有位都是9即可被整除
if (k == 1 || k == 3 || k == 9) {
return "9".repeat(n);
}

// k = 2: 末位必须是偶数，首位和末位取最大的偶数8
if (k == 2) {
if (n == 1) return "8";
return "8" + "9".repeat(n - 2) + "8";
}

// k = 4: 末两位需被4整除，88是最大满足条件的末两位
if (k == 4) {
if (n <= 2) return "8".repeat(n);
if (n == 3) return "888";
if (n == 4) return "8888";
// n >= 5: 前两位和末两位都是88，中间全9
return "88" + "9".repeat(n - 4) + "88";
}

// k = 5: 末位必须是5或0，取5（不能前导零），首位末位都是5
if (k == 5) {
if (n == 1) return "5";
return "5" + "9".repeat(n - 2) + "5";
}

// k = 6: 需同时满足被2和被3整除
// 被2整除：末位偶数；被3整除：数字和是3的倍数
if (k == 6) {
if (n == 1) return "6";
if (n == 2) return "66";
// n >= 3: 首尾取8（保证偶数且尽量大）
// 中间需要调整使数字和为3的倍数
if (n % 2 == 1) {
// 奇数位: 8...8...8，中间一位调整
// 8 + 8 + 9*(n-3) = 16 + 9*(n-3), 需中间位使总和%3==0
// 中间位取8: 总和 = 16 + 8 + 9*(n-3) = 24 + 9*(n-3) ≡ 0 (mod 3)
int tmp = (n - 3) / 2;
return "8" + "9".repeat(tmp) + "8" + "9".repeat(tmp) + "8";
} else {
// 偶数位: 中间两位取77
// 8 + 8 + 7 + 7 + 9*(n-4) = 30 + 9*(n-4) ≡ 0 (mod 3)
int tmp = (n - 4) / 2;
return "8" + "9".repeat(tmp) + "77" + "9".repeat(tmp) + "8";
}
}

// k = 7: 规律较复杂，中间部分需要枚举
if (k == 7) {
if (n <= 2) return "7".repeat(n);

// n > 2时，大部分位是9，只需调整中间1位（奇数）或2位（偶数）
if (n % 2 == 1) {
int half = (n - 1) / 2;
for (int m = 9; m >= 0; m--) {
// 构造回文：half个9 + m + half个9
String s = "9".repeat(half) + m + "9".repeat(half);
if (mod(s, 7) == 0) return s;
}
} else {
int half = (n - 2) / 2;
for (int m = 9; m >= 0; m--) {
String s = "9".repeat(half) + m + m + "9".repeat(half);
if (mod(s, 7) == 0) return s;
}
}
}

// k = 8: 末三位需被8整除，888是最大满足条件的三位
if (k == 8) {
if (n <= 6) return "8".repeat(n);
return "888" + "9".repeat(n - 6) + "888";
}

return "";
}

// 辅助方法：计算大数字符串对k取模（避免溢出）
private int mod(String s, int k) {
int res = 0;
for (char c : s.toCharArray()) {
res = (res * 10 + (c - '0')) % k;
}
return res;
}
}
```

核心规律说明

k 规律 示例 (n=5)
1, 3, 9 全9 `99999`
2 首尾8，中间9 `89998`
4 前两位末两位88，中间9 `88988` (n=5)
5 首尾5，中间9 `59995`
6 奇数：首尾8中间8；偶数：首尾8中间77 `89898`
7 大部分9，中间枚举 `99799` (n=5)
8 前三位末三位888，中间9 `88988` (n=5)

复杂度分析

- 时间复杂度: O(n) — 主要是字符串构造，k=7时最多枚举10种中间情况
- 空间复杂度: O(n) — 返回结果字符串的空间

这种方法比通用的 DP 解法（O(nk) 时间）更简洁高效，充分利用了 `k ≤ 9` 的题目约束。