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

﹏ヽ暗。殇╰゛Y 2022-11-14 13:12 170阅读 0赞

解题思路：

（1）全排列

（2）判断每次交换是否满足条件，满足进行下一步的递归

class Solution {
    public:
        void permute(vector<vector<int>> &v,vector<int> a, int l, int r) {  
            if (l == r)  v.push_back(a);  
            else {  
                for (int i = l; i <= r; i++) { 
                    if(a[l]!=a[i]||i==l) {
                        swap(a[l], a[i]); 
                        if(a[l]%(l+1)==0 || (l+1)%a[l]==0)
                            permute(v,a, l+1, r);
                        else continue;
                        swap(a[l], a[i]); 
                    }
                }  
            }
            return;
        }
        
        int countArrangement(int n) {
            vector<vector<int>> v;
            vector<int> a;
            for(int i=1;i<=n;i++) {
                a.push_back(i);
            }
            permute(v,a,0,n-1);
            int sum=0;
            for(int i=0;i<v.size();i++) {
                int count=0;
                for(int j=1;j<=v[i].size();j++) {
                    if(v[i][j-1]%j==0 || j%v[i][j-1]==0) count++;  
                }
                if(count==v[i].size()) sum++;
            }
            return sum;
        }
    };

发表评论取消回复

表情：

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

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

相关阅读

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

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

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

相关 Java实现 LeetCode 526 优美的排列（DFS）

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

分手后的思念是犯贱/ 2023年07月18日 04:47/ 0 赞/ 18 阅读

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

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

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

相关 526. 优美的排列

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

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

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

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

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

相关 leetcode526优美的排列

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

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

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

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

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

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

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

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

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

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

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

相关 Beautiful Soup

1. Beautiful Soup的简介 Beautiful Soup 是用Python写的一个HTML/XML的解析器，它可以很好的处理不规范标记并生成剖析树(pars...

亦凉/ 2021年05月03日 16:23/ 0 赞/ 382 阅读