学校网站建设解决方案,网站入口门户,天津百度推广电话号码,产品系统设计案例1. 题目链接#xff1a;526. 优美的排列
2. 题目描述#xff1a; 假设有从 1 到 n 的 n 个整数。用这些整数构造一个数组 perm#xff08;下标从 1 开始#xff09;#xff0c;只要满足下述条件 之一 #xff0c;该数组就是一个 优美的排列 #xff1a; perm[i] 能够被…1. 题目链接526. 优美的排列
2. 题目描述 假设有从 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 3. 解法递归
3.1 算法思路
我们需要在每个位置上考虑所有的可能情况并且不能出现重复。通过深度优先搜索的方式不断地枚举每个数在当前位置的可能性并且回溯到上一个状态直到枚举完所有的可能性得到正确的结果。
我们需要定义一个变量来记录所有可能的排列数量一个一维数组标记元素然后从第一个位置开始进行递归
3.2 递归流程
递归结束条件当pos等于n1时说明已经处理完所有的数字将当前数组存入结果中在每个递归状态中枚举所有下标若这个下标未被标记并且满足题目条件之一 将check[i]标记为true对第pos1个位置进行递归将check[i]重新赋值为false表示回溯 3.3 C算法代码
class Solution {bool check[16]; // 用于记录每个数字是否已经被使用过int ret; // 用于记录满足条件的排列的数量
public:int countArrangement(int n) {dfs(1, n); // 从第一个位置开始搜索return ret; // 返回满足条件的排列的数量}void dfs(int pos, int n) {if (pos n 1) { // 如果已经到达最后一个位置ret; // 找到一个满足条件的排列将计数器加1return; // 返回上一层递归}for (int i 1; i n; i) { // 遍历从1到n的所有数字if (!check[i] (pos % i 0 || i % pos 0)) { // 如果数字i未被使用过且满足排列的条件check[i] true; // 将数字i标记为已使用dfs(pos 1, n); // 继续搜索下一个位置check[i] false; // 将数字i标记为未使用以便在其他路径中使用}}}
};
