0526. Beautiful Arrangement =========================== 题目信息 -------- :题号: 0526 :难度: Medium :主题: 排列、一基位置、整除条件、方案计数 :原题: `LeetCode 0526 `_ :重点: 使用 1..n 的每个整数恰好一次、位置从 1 开始、每个位置满足双向整除条件、返回排列数量 题目重述 -------- 给定正整数 ``n``,考虑由整数 ``1`` 到 ``n`` 组成的所有排列。若对排列中的每个一基位置 ``i``,都有 ``perm[i]`` 能被 ``i`` 整除,或者 ``i`` 能被 ``perm[i]`` 整除,则该排列称为美丽排列。 返回美丽排列的总数量。每个整数必须恰好使用一次,位置编号从 ``1`` 而不是 ``0`` 开始;同一组数字的不同排列按不同方案计数。 自建示例 -------- 三个数字的排列: .. code-block:: text 输入:n = 3 输出:3 解释:合法排列为 [1,2,3]、[2,1,3] 和 [3,2,1];其他排列至少有一个位置不满足整除条件。 只有一个数字: .. code-block:: text 输入:n = 1 输出:1 解释:唯一排列 [1] 在位置 1 满足整除条件。 按位置回溯并用位掩码去重 ------------------------ 从位置 1 开始逐位放置未使用数字。数字 ``value`` 能放在当前位置 ``position`` 的条件是二者至少一个能整除另一个;掩码的第 ``value-1`` 位记录它是否已被使用。由于后续结果只取决于已用集合,当前位置可以由集合中位数推出,适合记忆化。 C++ 实现 -------- .. code-block:: cpp class Solution { int n; std::vector memo; int count(int used) { int& cached = memo[used]; if (cached != -1) return cached; int position = __builtin_popcount(static_cast(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)``。