个人主页：元清加油_【C++】,【C语言】,【数据结构与算法】-CSDN博客元清加油_【C++】,【C语言】,【数据结构与算法】-CSDN博客
个人专栏
力扣递归算法题
http://t.csdnimg.cn/yUl2I
【C++】
http://t.csdnimg.cn/6AbpV
数据结构与算法
http://t.csdnimg.cn/hKh2l
前言：这个专栏主要讲述递归递归、搜索与回溯算法，所以下面题目主要也是这些算法做的
我讲述题目会把讲解部分分为3个部分：
1、题目解析
2、算法原理思路讲解
3、代码实现
优美的排列
题目链接：
题目
假设有从 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
解法
题目解析
题目的意思非常简单
假设有从 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 整除
算法原理思路讲解
- 我们需要在每⼀个位置上考虑所有的可能情况并且不能出现重复。
- 通过深度优先搜索的⽅式，不断地枚举每个数在当前位置的可能性，并回溯到上⼀个状态，直到枚举完所有可能性，得到正确的结果。
- 我们需要定义⼀个变量 ⽤来记录所有可能的排服务器托管网列数量，⼀个⼀维数组 check 标记元素，然后从第⼀个位置开始进⾏递归。
一、画出决策树
决策树就是我们后面设计函数的思路
二、设计代码
（1）全局变量
int ret;
bool check[16] = { false };
- ret（可以构造的优美排列的数量）
- check（用来检测这个数字是否用过）
（2）设计递归函数
void dfs(int n, int pos)- 参数：n（一到n的数字），pos（当前要处理的位置下标）；
- 返回值：无；
- 函数作用：在当前位置填⼊⼀个合理的数字，查找所有满⾜条件的排列。
递归流程如下
- 递归结束条件：当 pos等于 n 时，说明已经处理完了所有数字，将当前数组存⼊结果中；
-
在每个递归状态中，枚举所有下标 i，若这个下标未被标记，并且满⾜题⽬条件之⼀：
- 将 check[i] 标记为 true；
- 对第 pos+1 个位置进⾏递归；
- 将 check[i] 重新赋值为 false，表⽰回溯；
以上思路讲解完毕，大家可以自己做一下了
代码实现
class Solution {
public:
int ret;
bool check[16] = { false };
void dfs(int n, int pos)
{
for (int i = 1; i 服务服务器托管网器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
相关推荐: 【JVM从入门到实战】（六）类加载器的双亲委派机制
一、双亲委派机制 在Java中如何使用代码的方式去主动加载一个类呢？ 方式1：使用Class.forName方法，使用当前类的类加载器去加载指定的类。 方式2：获取到类加载器，通过类加载器的loadClass方法指定某个类加载器加载。 双亲委派机制：自底向上查…
