Kimi K2.6快速 LeetCode 3260. 找出最大的 N 位 K 回文数 Rust实现

2026/6/16 0:39:27

以下是 LeetCode 3260 **找出最大的 N 位 K 回文数** 的 **Rust 实现**，基于 k 的分类讨论规律解法，时间复杂度 O(n)，空间复杂度 O(n)。

```rust
impl Solution {
pub fn largest_palindrome(n: i32, k: i32) -> String {
let n = n as usize;
match k {
// k = 1, 3, 9: 全9即可被整除
1 | 3 | 9 => "9".repeat(n),

// k = 2: 末位需为偶数，取最大偶数8
2 => {
if n <= 2 {
"8".repeat(n)
} else {
format!("8{}8", "9".repeat(n - 2))
}
}

// k = 4: 末两位需被4整除，88是最大满足条件的两位
4 => {
if n <= 4 {
"8".repeat(n)
} else {
format!("88{}88", "9".repeat(n - 4))
}
}

// k = 5: 末位需为0或5，取5
5 => {
if n <= 2 {
"5".repeat(n)
} else {
format!("5{}5", "9".repeat(n - 2))
}
}

// k = 6: 需同时满足被2和被3整除
6 => {
if n <= 2 {
"6".repeat(n)
} else if n % 2 == 1 {
// 奇数位: 8...8...8，中间8保证数字和为3的倍数
let l = n / 2 - 1;
format!("8{}8{}8", "9".repeat(l), "9".repeat(l))
} else {
// 偶数位: 中间两位取77
let l = n / 2 - 2;
format!("8{}77{}8", "9".repeat(l), "9".repeat(l))
}
}

// k = 7: 规律最复杂，按 n % 12 查表
7 => {
if n <= 2 {
"7".repeat(n)
} else {
let middle = vec![
"", "7", "77", "959", "9779", "99799",
"999999", "9994999", "99944999", "999969999",
"9999449999", "99999499999",
];
let q = n / 12;
let r = n % 12;
format!(
"{}{}{}",
"999999".repeat(q),
middle[r],
"999999".repeat(q)
)
}
}

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

_ => String::new(),
}
}
}
```

核心思路说明

由于 `k ≤ 9`，可以对每个 k 值利用整除规则和回文约束分别找规律：

k 关键规则构造方式
1, 3, 9 数字和是3/9的倍数全 `9`
2 末位偶数首尾 `8`，中间全 `9`
4 末两位被4整除前两位和末两位 `88`，中间全 `9`
5 末位0或5 首尾 `5`，中间全 `9`
6 被2且被3整除奇数：`8...8...8`；偶数：中间 `77`
7 无简单规则按 `n % 12` 查中间表，两侧填充 `999999`
8 末三位被8整除前三位和末三位 `888`，中间全 `9`

k = 7 的特殊处理

k=7 的规律最为复杂，通过数学推导发现结果以 12 为周期循环。因此预存了 12 种中间模式（`middle` 数组），两侧用 `999999` 填充：

- `n = 3` → `959`（中间模式索引 3）
- `n = 5` → `99799`（中间模式索引 5）
- `n = 6` → `999999`（中间模式索引 6）
- `n = 12` → `999999999999`（两侧各一个 `999999`，中间为空）
- `n = 15` → `999999959999999`（两侧各一个 `999999`，中间 `959`）

复杂度分析

- 时间复杂度: O(n) — `String::repeat` 和 `format!` 的字符串构造
- 空间复杂度: O(n) — 返回结果字符串所需空间

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