​LeetCode刷题实战526： 优美的排列

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选 ！

今天和大家聊的问题叫做 优美的排列，我们先来看题面：

https://leetcode-cn.com/problems/beautiful-arrangement/

Suppose you have n integers labeled 1 through n. A permutation of those n integers perm (1-indexed) is considered a beautiful arrangement if for every i (1 <= i <= n), either of the following is true: perm[i] is divisible by i. i is divisible by perm[i]. Given an integer n, return the number of the beautiful arrangements that you can construct.

假设有从 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

解题

https://www.cnblogs.com/linrj/p/13972877.html

题目说了N不会超过15，这就是在暗示我们用DFS。

直接DFS出1～N的排列，然后判断一下是否满足条件。

不过这里要剪枝一下，不需要枚举出所有的排列之后逐个判断，对于某个排列的某一位u，如果已经不满足条件了，即不满足u % i == 0 或者 i % u == 0，那么就无需枚举剩下的位。

这题不加这个剪枝貌似会超时。

代码如下：

class Solution {
public:
    int res = 0;
    int n;
    vector<bool> visited; // 判断某个数字是否已经在当前排列出现过

    void dfs(int u, vector<bool>& visited) {
        if(u == n + 1) { // 找到一个满足条件的排列，答案++
            ++res;
            return ;
        }
        for(int i = 1; i <= n; ++i) {
            if(visited[i] == false && ((u % i == 0) || (i % u == 0))) { // 当前数字没有排列中出现过，且满足题目要求的条件，则尝试在当前位置放上数字i，再继续搜索下一个位置
                visited[i] = true;
                dfs(u + 1, visited);
                visited[i] = false;
            }
        }
    }

    int countArrangement(int N) {
        n = N;
        visited = vector<bool>(n + 1, false);
        dfs(1, visited);
        return res;
    }
};

好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力 。

上期推文：

LeetCode1-520题汇总，希望对你有点帮助！

LeetCode刷题实战521：最长特殊序列 I

LeetCode刷题实战522：最长特殊序列 II

LeetCode刷题实战523：连续的子数组和

LeetCode刷题实战524：通过删除字母匹配到字典里最长单词

LeetCode刷题实战525：连续数组