企业官网建设流程全解析

LeetCode 3470. 全排列 IV — Rust 实现

解题思路

与之前版本一致，采用 组合计数 DP + 逐位构造：

1. DP 状态：`dp[o][e][p]` 表示剩余 `o` 个奇数、`e` 个偶数，且上一个数字的奇偶性为 `p`（`0=偶, 1=奇`）时，后续能构成的合法交替排列数。
2. 防溢出：Rust 中 `u128` 最大约 `3.4×10³⁸`，但 `n=100` 时交替排列数远超此范围。因此将 DP 值上限截断为 `k + 1`（使用 `u128` 存储，因为 `k ≤ 10¹⁵` 在 `u64` 范围内）。
3. 字典序构造：从小到大枚举每一位可选数字，利用 DP 值判断第 `k` 个排列所在分支。

---

完整代码

```rust
impl Solution {
pub fn permute(n: i32, k: i64) -> Vec<i32> {
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 个偶数，上一个数字奇偶性为 p（0=偶, 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 值和中间计算结果，确保即使 `n=100` 时也不会溢出。`k` 作为 `i64` 传入，转换为 `u128` 后参与比较和减法运算。