🏐 526.优美的排列
假设有从 1 到 n 的 n 个整数。用这些整数构造一个数组 perm（下标从 1 开始），只要满足下述条件 之一 ，该数组就是一个 优美的排列 ：
perm[i] 能够被 i 整除i 能够被 perm[i] 整除
给你一个整数 n ，返回可以构造的 优美排列 的 数量 。
思路
基本思想
看到题目之后，第一想法就是按照回溯法求出所有的全排列，然后再判断每个全排列是否符合要求，也就是对于当前全排列来说，每个位置是否符合（下标从1开始）：
perm[i] 能够被 i 整除i 能够被 perm[i] 整除
按照这种思路编写代码之后，会超时，超时的代码为：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| class Solution {
//使用回溯法找到所有的排列，然后再判断是否合法
//针对一个排列的所有数，依次判断是否符合任意一个条件即可
//解法可行，但是超时
List<Integer> path=new ArrayList<>();
int res=0;
boolean[] visited;
public int countArrangement(int n) {
visited=new boolean[n];
help(n);
return res;
}
//回溯法求排列
private void help(int n){
//形成了一个全排列，并且每个元素都符合条件
if(path.size()==n&&isValid(path)){
++res;
}
//对于当前全排列来说，1-n的所有元素都会尝试一遍，这是超时的主要问题
//对于当前位置来说，只有部分元素符合条件，我们可以在回溯之前进行处理
for(int i=1;i<=n;++i){
//当前元素没访问，加入全排列中
if(!visited[i-1]){
visited[i-1]=true;
path.add(i);
help(n);
//回溯
visited[i-1]=false;
path.remove(path.size()-1);
}
}
}
private boolean isValid(List<Integer> path){
for(int i=0;i<path.size();++i){
//两个条件都不满足，说明当前排列不满足条件
if(!((path.get(i))%(i+1)==0||(i+1)%(path.get(i))==0))
return false;
}
return true;
}
}
|
上述代码超时的主要原因在于构造全排列的过程中，每一个位置都尝试了1-n的所有数，其实大部分数都是无意义的尝试，如果我们提前告知回溯法对于当前位置来说，哪些元素符合上面的两个条件之一，这样就可以减少两个操作：
- 全排列中的每一个位置不再有无意义的尝试
- 构造完全排列之后不用在判断全排列的有效性，因为每个位置的元素都是从合法集中选取的
相当于提前构造一个map,每个位置有哪些元素合法提前构造
执行流程
- 初始化一个二维List，里面存储每个位置合法的元素
- 进行回溯，构造全排列时每个位置的元素选取从合法元素集中选取
- 构造完一个全排列结果数就+1
- 返回需要的结果
代码
根据以上分析，得出以下代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| class Solution {
//使用回溯法找到所有的排列，然后再判断是否合法
//针对一个排列的所有数，依次判断是否符合任意一个条件即可
//解法可行，但是超时
int res=0;
boolean[] visited;
List<List<Integer>> map=new ArrayList<>();
public int countArrangement(int n) {
visited=new boolean[n];
for(int i=0;i<=n;++i){
map.add(new ArrayList<>());
}
//统计每个位置有哪些元素合法
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
if(j%i==0||i%j==0)
//第i个位置上添加元素j
map.get(i).add(j);
}
}
help(n,1);
return res;
}
//回溯法求排列
private void help(int n,int index){
//形成了一个全排列，并且每个元素都符合条件
if(index==n+1){
++res;
return;
}
//对于当前全排列来说，1-n的所有元素都会尝试一遍，这是超时的主要问题
//对于当前位置来说，只有部分元素符合条件，我们可以在回溯之前进行处理
for(int num:map.get(index)){
if(!visited[num-1]){
visited[num-1]=true;
help(n,index+1);
visited[num-1]=false;
}
}
}
}
|
总结
解决问题的核心还是使用回溯法求出所有的排列，只不过第一份代码是求出所有的代码，然后进行筛选，相当于每个位置上填充的元素是从1-n中选取的，而这些无意义的尝试会使得算法超时。第二份代码提前进行构造，每个位置上填充的元素是从一个候选List中选取的，这个候选List中的所有元素都是合法的，这既不会有无意义的尝试，在形成全排列的时候又不用担心当前全排列是否合法，相当于一举两得