LeetCode 634. 寻找数组的错位排列
题目描述
题意分析
将 $1$ 到 $n$ 重新排列，要求数字 $i$ 不能放在位置 $i$，求满足条件的排列数量，并对 $10^9+7$ 取模。只要有一个数字仍在原位置，整个排列就不合法。
解法：动态规划（递推公式）
核心思路
[!blue]
固定数字 1 的去向，再分类处理与它相关的数字。 设 $f(n)$ 为 $n$ 个数字的错排数。数字 1 不能留在位置 1，可以选择其余 $n-1$ 个位置。固定它去了位置 $j$ 后，根据数字 $j$ 是否放在位置 1，分成两类。若数字 $j$ 放在位置 1，两个数字恰好互换，移除它们及各自位置后，剩下 $n-2$ 个数字仍需各自避开原位置，共有 $f(n-2)$ 种。
若数字 $j$ 不放在位置 1，移除数字 1 和已被它占据的位置 $j$。其他数字仍不能回原位，数字 $j$ 则被这一分支禁止放到位置 1。把剩下的位置 1 重新标为位置 $j$，就得到 $n-1$ 个数字各自不能放到同名位置的错排。这个变换可逆：将位置改名回来，再把数字 1 放回位置 $j$ 即可，因此这一类恰好有 $f(n-1)$ 种。
两类互斥且覆盖全部情况，每个 $j$ 的计数又相同，所以 $f(n)=(n-1)(f(n-1)+f(n-2))$。初值为 $f(1)=0$、$f(2)=1$，分别对应无处可放和只能交换。
计算第 $i$ 项时，
d1、d2分别保存前两项 $f(i-2)$、$f(i-1)$ 的余数。先算出cur，再把两项向前推进。递推只含加法和乘法，可以每轮取模而不改变最终余数；乘法必须先使用 Javalong或 Goint64完成，不能等窄整数溢出后再取模。
解题步骤
- 处理已有小规模初值。
- 保存前两项余数。
- 从三开始计算递推，乘法后取模。
- 先保存新值，再移动两项窗口。
代码实现
class Solution {
public int findDerangement(int n) {
long mod = 1_000_000_007L;
if (n == 1) {
return 0;
}
if (n == 2) {
return 1;
}
long d1 = 0;
long d2 = 1;
for (int i = 3; i <= n; i++) {
// 按第一个数的去向分类，交换与不交换两种情况共同乘位置选择数。
long cur = (i - 1L) * ((d2 + d1) % mod) % mod;
// 新值已保存，再整体推进前两项窗口。
d1 = d2;
d2 = cur;
}
return (int) d2;
}
}
func findDerangement(n int) int {
const mod int64 = 1_000_000_007
if n == 1 {
return 0
}
if n == 2 {
return 1
}
d1 := int64(0)
d2 := int64(1)
for i := 3; i <= n; i++ {
// 按第一个数的去向分类，交换与不交换两种情况共同乘位置选择数。
cur := int64(i-1) * ((d2 + d1) % mod) % mod
// 新值已保存，再整体推进前两项窗口。
d1 = d2
d2 = cur
}
return int(d2)
}
复杂度分析
- 时间复杂度：$O(n)$，顺序递推。
- 空间复杂度：$O(1)$，只保存前两项。
关键点总结
[!green]
- 两种去向分类互斥且完整。
- n-1 种位置选择乘上两类子问题之和。
- 滚动变量始终代表相邻的前两项。
易错点总结
[!yellow]
- 括号只乘其中一项：两类情况都应乘 n-1。
- 先覆盖后一项再挪前一项：旧状态丢失。
- 使用窄整数完成大乘积：取模前就可能溢出。
- 缓存起始项与循环起点不配套：整条递推错位。
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！