以下是 LeetCode 3260 **找出最大的 N 位 K 回文数** 的 **Rust 实现**基于 k 的分类讨论规律解法时间复杂度 O(n)空间复杂度 O(n)。rustimpl 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: 末位需为偶数取最大偶数82 {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取55 {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 {// 偶数位: 中间两位取77let 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的倍数 全 92 末位偶数 首尾 8中间全 94 末两位被4整除 前两位和末两位 88中间全 95 末位0或5 首尾 5中间全 96 被2且被3整除 奇数8...8...8偶数中间 777 无简单规则 按 n % 12 查中间表两侧填充 9999998 末三位被8整除 前三位和末三位 888中间全 9k 7 的特殊处理k7 的规律最为复杂通过数学推导发现结果以 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 的题目约束。