LeetCode 题解工作台
优美的排列
假设有从 1 到 n 的 n 个整数。用这些整数构造一个数组 perm （ 下标从 1 开始 ），只要满足下述条件 之一 ，该数组就是一个 优美的排列 ： perm[i] 能够被 i 整除 i 能够被 perm[i] 整除 给你一个整数 n ，返回可以构造的 优美排列 的 数量 。 示例 1： 输入…
5
题型
6
代码语言
3
相关题
当前训练重点
中等 · 状态·转移·动态规划
答案摘要
class Solution: def countArrangement(self, n: int) -> int:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
假设有从 1 到 n 的 n 个整数。用这些整数构造一个数组 perm（下标从 1 开始），只要满足下述条件 之一 ，该数组就是一个 优美的排列 ：
perm[i]能够被i整除i能够被perm[i]整除
给你一个整数 n ，返回可以构造的 优美排列 的 数量 。
示例 1：
输入：n = 2
输出：2
解释：
第 1 个优美的排列是 [1,2]：
- perm[1] = 1 能被 i = 1 整除
- perm[2] = 2 能被 i = 2 整除
第 2 个优美的排列是 [2,1]:
- perm[1] = 2 能被 i = 1 整除
- i = 2 能被 perm[2] = 1 整除
示例 2：
输入：n = 1 输出：1
提示：
1 <= n <= 15
解题思路
方法一
class Solution:
def countArrangement(self, n: int) -> int:
def dfs(i):
nonlocal ans, n
if i == n + 1:
ans += 1
return
for j in match[i]:
if not vis[j]:
vis[j] = True
dfs(i + 1)
vis[j] = False
ans = 0
vis = [False] * (n + 1)
match = defaultdict(list)
for i in range(1, n + 1):
for j in range(1, n + 1):
if j % i == 0 or i % j == 0:
match[i].append(j)
dfs(1)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Understanding of dynamic programming principles and backtracking.
- question_mark
Ability to optimize search space using bitmasking.
- question_mark
Familiarity with state transitions and pruning techniques.
常见陷阱
外企场景- error
Overlooking the need for pruning, leading to excessive recursion.
- error
Failing to properly handle base cases or conditions during recursion.
- error
Mismanaging state transitions when using dynamic programming or bitmasking.
进阶变体
外企场景- arrow_right_alt
Increasing n beyond 15 to test scalability.
- arrow_right_alt
Modifying the divisibility rule for more complex conditions.
- arrow_right_alt
Limiting the problem to only odd or even positions.