0526. Beautiful Arrangement¶
题目信息¶
- 题号:
0526
- 难度:
Medium
- 主题:
排列、一基位置、整除条件、方案计数
- 原题:
- 重点:
使用 1..n 的每个整数恰好一次、位置从 1 开始、每个位置满足双向整除条件、返回排列数量
题目重述¶
给定正整数 n,考虑由整数 1 到 n 组成的所有排列。若对排列中的每个一基位置 i,都有 perm[i] 能被 i 整除,或者 i 能被 perm[i] 整除,则该排列称为美丽排列。
返回美丽排列的总数量。每个整数必须恰好使用一次,位置编号从 1 而不是 0 开始;同一组数字的不同排列按不同方案计数。
自建示例¶
三个数字的排列:
输入:n = 3
输出:3
解释:合法排列为 [1,2,3]、[2,1,3] 和 [3,2,1];其他排列至少有一个位置不满足整除条件。
只有一个数字:
输入:n = 1
输出:1
解释:唯一排列 [1] 在位置 1 满足整除条件。
按位置回溯并用位掩码去重¶
从位置 1 开始逐位放置未使用数字。数字 value 能放在当前位置 position 的条件是二者至少一个能整除另一个;掩码的第 value-1 位记录它是否已被使用。由于后续结果只取决于已用集合,当前位置可以由集合中位数推出,适合记忆化。
C++ 实现¶
class Solution {
int n;
std::vector<int> memo;
int count(int used) {
int& cached = memo[used];
if (cached != -1) return cached;
int position = __builtin_popcount(static_cast<unsigned>(used)) + 1;
if (position > n) return cached = 1;
cached = 0;
for (int value = 1; value <= n; ++value) {
int bit = 1 << (value - 1);
if ((used & bit) != 0) continue;
if (value % position != 0 && position % value != 0) continue;
cached += count(used | bit);
}
return cached;
}
public:
int countArrangement(int nValue) {
n = nValue;
memo.assign(1 << n, -1);
return count(0);
}
};
代码分析¶
每条递归路径恰好使用一个新数字,位置由已用数字数量决定;整除判断保留且只保留合法排列。相同已用集合的后续选择完全相同,记忆化避免重复计算。状态数为 2^n,每个状态尝试 n 个值,时间复杂度为 O(n2^n),空间复杂度为 O(2^n)。