Kimi LeetCode 3470. 全排列 IV Rust实现

LeetCode 3470. 全排列 IV — Rust 实现解题思路与之前版本一致采用 组合计数 DP 逐位构造1. DP 状态dp[o][e][p] 表示剩余 o 个奇数、e 个偶数且上一个数字的奇偶性为 p0偶, 1奇时后续能构成的合法交替排列数。2. 防溢出Rust 中 u128 最大约 3.4×10³⁸但 n100 时交替排列数远超此范围。因此将 DP 值上限截断为 k 1使用 u128 存储因为 k ≤ 10¹⁵ 在 u64 范围内。3. 字典序构造从小到大枚举每一位可选数字利用 DP 值判断第 k 个排列所在分支。---完整代码rustimpl Solution {pub fn permute(n: i32, k: i64) - Veci32 {let n n as usize;let k k as u128;let odd_count (n 1) / 2; // 1, 3, 5, ... 的个数let even_count n / 2; // 2, 4, 6, ... 的个数let limit k 1;// dp[o][e][p]// 剩余 o 个奇数、e 个偶数上一个数字奇偶性为 p0偶, 1奇let mut dp vec![vec![vec![0u128; 2]; even_count 1]; odd_count 1];dp[0][0][0] 1;dp[0][0][1] 1;for o in 0..odd_count {for e in 0..even_count {if o 0 e 0 {continue;}// 上一个为偶数下一个需要奇数if o 0 {dp[o][e][0] limit.min((o as u128) * dp[o - 1][e][1]);}// 上一个为奇数下一个需要偶数if e 0 {dp[o][e][1] limit.min((e as u128) * dp[o][e - 1][0]);}}}// 计算总方案数let mut total: u128 0;if odd_count 0 {total (odd_count as u128) * dp[odd_count - 1][even_count][1];}if even_count 0 {total (even_count as u128) * dp[odd_count][even_count - 1][0];}total limit.min(total);// 有效排列不足 k 个if k total {return vec![];}let mut res Vec::with_capacity(n);let mut used vec![false; n 1];let mut remaining_odd odd_count;let mut remaining_even even_count;let mut last_parity: i32 -1; // -1 表示还没有放任何数字let mut k k;for _ in 0..n {let mut found false;for num in 1..n {if used[num] {continue;}let parity (num 1) as i32; // 1奇数, 0偶数// 必须奇偶交替if last_parity ! -1 parity last_parity {continue;}// 计算选择当前数字后剩余位置的方案数let count if parity 1 {dp[remaining_odd - 1][remaining_even][1]} else {dp[remaining_odd][remaining_even - 1][0]};if k count {k - count; // 第 k 个不在当前分支跳过} else {// 第 k 个在当前分支res.push(num as i32);used[num] true;if parity 1 {remaining_odd - 1;last_parity 1;} else {remaining_even - 1;last_parity 0;}found true;break;}}if !found {return vec![];}}res}}---复杂度分析- 时间复杂度O(n²)。DP 填充为 O(n²)构造过程每层最多枚举 n 个数字。- 空间复杂度O(n²)。DP 数组大小约为 (n/2)² × 2。 Rust 的类型系统要求显式处理类型转换。这里使用 u128 存储 DP 值和中间计算结果确保即使 n100 时也不会溢出。k 作为 i64 传入转换为 u128 后参与比较和减法运算。