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

LeetCode 3260 要求找出最大的 n 位 K 回文数可被 k 整除的回文数。由于 k ≤ 9 而 n ≤ 10^5最优雅的解法是按 k 分类讨论找规律这样时间复杂度为 O(n)空间复杂度为 O(1)除结果字符串外。以下是基于题解规律总结的 Java 实现javaclass 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: 末位必须是偶数首位和末位取最大的偶数8if (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中间全9return 88 9.repeat(n - 4) 88;}// k 5: 末位必须是5或0取5不能前导零首位末位都是5if (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), 需中间位使总和%30// 中间位取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个9String 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 规律 示例 (n5)1, 3, 9 全9 999992 首尾8中间9 899984 前两位末两位88中间9 88988 (n5)5 首尾5中间9 599956 奇数首尾8中间8偶数首尾8中间77 898987 大部分9中间枚举 99799 (n5)8 前三位末三位888中间9 88988 (n5)复杂度分析- 时间复杂度: O(n) — 主要是字符串构造k7时最多枚举10种中间情况- 空间复杂度: O(n) — 返回结果字符串的空间这种方法比通用的 DP 解法O(nk) 时间更简洁高效充分利用了 k ≤ 9 的题目约束。