526. 优美的排列(dfs)

Love The Way You Lie 2022-09-05 01:56 156阅读 0赞

假设有从 1 到 N 的 N 个整数，如果从这 N 个数字中成功构造出一个数组，使得数组的第 i 位 (1 <= i <= N) 满足如下两个条件中的一个，我们就称这个数组为一个优美的排列。条件：

第 i 位的数字能被 i 整除  
i 能被第 i 位上的数字整除  
现在给定一个整数 N，请问可以构造多少个优美的排列？

示例1:

输入: 2  
输出: 2  
解释:

第 1 个优美的排列是 \[1, 2\]:  
  第 1 个位置（i=1）上的数字是1，1能被 i（i=1）整除  
  第 2 个位置（i=2）上的数字是2，2能被 i（i=2）整除

第 2 个优美的排列是 \[2, 1\]:  
  第 1 个位置（i=1）上的数字是2，2能被 i（i=1）整除  
  第 2 个位置（i=2）上的数字是1，i（i=2）能被 1 整除  
说明:

N 是一个正整数，并且不会超过15。

时间复杂度：O(n!)，n的最大值为15，而15！=87178291200，而为啥不会超时？因为剪枝。

class Solution {
    private:
        int vis[16]={0};
        int cnt = 0;
    public:
        void dfs(int pos,int n)
        {
            for(int i = 1;i<=n;i++)
            {
                if(!this->vis[i]&&(i%pos==0||pos%i==0))
                {
                    if(pos == n)
                    {
                        this->cnt++;
                        return;
                    }
                    this->vis[i] = 1;
                    dfs(pos+1,n);
                    this->vis[i] = 0;
                }
            }
        }
        int countArrangement(int n) {
            dfs(1,n);
            return this->cnt;
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，156人围观）

还没有评论，来说两句吧...

相关阅读

相关 Java实现 LeetCode 667 优美的排列 II（暴力）

667. 优美的排列 II 给定两个整数 n 和 k，你需要实现一个数组，这个数组包含从 1 到 n 的 n 个不同整数，同时满足以下条件： ① 如果这个数组是 \[a

清疚/ 2023年07月21日 13:26/ 0 赞/ 4 阅读

相关 AcWing | 【DFS】排列数字

题目内容 > 给定一个整数n，将数字1~n排成一排，将会有很多种排列方法。 > > 现在，请你按照字典序将所有的排列方法输出。输入格式 > 共一行，包含一个整数n。

た入场券/ 2022年12月20日 06:00/ 0 赞/ 136 阅读

相关 Beautiful Arrangement（C++优美的排列）

解题思路：（1）全排列（2）判断每次交换是否满足条件，满足进行下一步的递归 class Solution { public: void

﹏ヽ暗。殇╰゛Y/ 2022年11月14日 13:12/ 0 赞/ 159 阅读

相关 526. 优美的排列

> 假设有从 1 到 N 的 N 个整数，如果从这 N 个数字中成功构造出一个数组，使得数组的第 i 位 (1 <= i <= N) 满足如下两个条件中的一个，我们就称这个数组

我会带着你远行/ 2022年10月08日 05:40/ 0 赞/ 168 阅读

相关 leetcode 526. Beautiful Arrangement | 526. 优美的排列（回溯）

题目 [https://leetcode.com/problems/beautiful-arrangement/][https_leetcode.com_problems

r囧r小猫/ 2022年09月12日 10:50/ 0 赞/ 181 阅读

相关 leetcode526优美的排列

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

蔚落/ 2022年09月05日 11:25/ 0 赞/ 136 阅读

相关 526. 优美的排列(dfs)

假设有从 1 到 N 的 N 个整数，如果从这 N 个数字中成功构造出一个数组，使得数组的第 i 位 (1 <= i <= N) 满足如下两个条件中的一个，我们就称这个数组为一

Love The Way You Lie/ 2022年09月05日 01:56/ 0 赞/ 157 阅读

相关 667 优美的排列 II（构造）

1. 问题描述：给你两个整数 n 和 k ，请你构造一个答案列表 answer ，该列表应当包含从 1 到 n 的 n 个不同正整数，并同时满足下述条件：假设该列表是

柔光的暖阳◎/ 2022年09月02日 08:39/ 0 赞/ 153 阅读

相关 526 优美的排列（状态压缩dp）

1. 问题描述：假设有从 1 到 N 的 N 个整数，如果从这 N 个数字中成功构造出一个数组，使得数组的第 i 位 (1 <= i <= N) 满足如下两个条件中的一个，

淩亂°似流年/ 2022年08月30日 12:54/ 0 赞/ 195 阅读

相关 leetcode 526. Beautiful Arrangement 递归实现全排列 + 经典深度优先遍历DFS做法

Suppose you have N integers from 1 to N. We define a beautiful arrangement as an array t

﹏ヽ暗。殇╰゛Y/ 2022年06月03日 03:21/ 0 赞/ 171 阅读