LeetCode刷题--- 优美的排列

个人主页：元清加油_【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 整除

---

算法原理思路讲解?

1. 我们需要在每?个位置上考虑所有的可能情况并且不能出现重复。
2. 通过深度优先搜索的?式，不断地枚举每个数在当前位置的可能性，并回溯到上?个状态，直到枚举完所有可能性，得到正确的结果。
3. 我们需要定义?个变量 ?来记录所有可能的排列数量，?个?维数组 check 标记元素，然后从第?个位置开始进?递归。

一、画出决策树

决策树就是我们后面设计函数的思路

---

二、设计代码

（1）全局变量

    int ret;
    bool check[16] = { false };

• ret（可以构造的?优美排列?的?数量?）
• check（用来检测这个数字是否用过）

（2）设计递归函数

    void dfs(int n, int pos)

• 参数：n（一到n的数字），pos（当前要处理的位置下标）；
• 返回值：无；
• 函数作用：在当前位置填??个合理的数字，查找所有满?条件的排列。

递归流程如下

1. 递归结束条件：当 pos?等于 n 时，说明已经处理完了所有数字，将当前数组存?结果中；
2. 在每个递归状态中，枚举所有下标 i，若这个下标未被标记，并且满?题?条件之?：
   1. ?将 check[i] 标记为 true；
   2. ?对第 pos+1 个位置进?递归；
   3. ?将 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;
    }
};