个人主页:元清加油_【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 <= n <= 15
解法
题目解析
题目的意思非常简单
假设有从 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 <= n; i++)
{
if (check[i] == false && (i % pos == 0 || pos % i == 0))
{
if (pos == n)
{
ret++;
return;
}
check[i] = true;
dfs(n, pos + 1);
check[i] = false;
}
}
}
int countArrangement(int n)
{
dfs(n, 1);
return ret;
}
};