DeepSeek LeetCode 526. 优美的排列 Java实现

LeetCode 526. 优美的排列（Java）

题目要点

用 1 ~ n 构造排列 perm（下标从 1 开始），要求对每个位置 i：

perm[i] % i == 0 或 i % perm[i] == 0

返回满足条件的排列数量。

方法一：回溯 + 剪枝

从位置 1 到 n 依次填数字，用一个 used 数组标记数字是否已使用。
当前位置 pos 只能放满足整除关系的未使用数字。

classSolution{privateintcount=0;publicintcountArrangement(intn){boolean[]used=newboolean[n+1];backtrack(1,n,used);returncount;}privatevoidbacktrack(intpos,intn,boolean[]used){// 所有位置都填完了，说明找到一个合法排列if(pos>n){count++;return;}for(intnum=1;num<=n;num++){if(used[num])continue;// 满足优美排列条件if(num%pos==0||pos%num==0){used[num]=true;backtrack(pos+1,n,used);used[num]=false;}}}}

复杂度

· 时间复杂度：最坏 O(n!)，但剪枝后远小于全排列。
· 空间复杂度：O(n)，递归栈和 used 数组。

方法二：状态压缩 DP

用二进制 mask 表示哪些数字已经被使用。
dp[mask] 表示使用 mask 中数字填充前 popcount(mask) 个位置的方法数。

当前要填的位置：

pos = Integer.bitCount(mask) + 1

尝试把未使用的数字 num 放到 pos，如果满足整除条件，则转移。

classSolution{publicintcountArrangement(intn){inttotalMask=1<<n;int[]dp=newint[totalMask];dp[0]=1;for(intmask=0;mask<totalMask;mask++){if(dp[mask]==0)continue;intpos=Integer.bitCount(mask)+1;for(intnum=1;num<=n;num++){intbit=1<<(num-1);// 数字 num 还没被使用if((mask&bit)==0){// 满足优美排列条件if(num%pos==0||pos%num==0){dp[mask|bit]+=dp[mask];}}}}returndp[totalMask-1];}}

复杂度

· 时间复杂度：O(n * 2^n)
· 空间复杂度：O(2^n)

示例

输入：n=2输出：2解释： 排列[1,2]：1%1==0，2%2==0，合法 排列[2,1]：2%1==0，1%2!=0但2%1==0，合法

输入：n=3输出：3

推荐

· n ≤ 15 时，回溯法代码简单、实际运行很快，面试中更常写。
· 状态压缩 DP 思路更系统，适合展示动态规划能力。
· 两者都可以通过 LeetCode 526。