[数据结构与算法]LeetCode526优美的排列

LeetCode526优美的排列

基于dfs,状态压缩

题目

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

来源：力扣（LeetCode）

方法一：dfs（超时）

1.思想：

这个方法的想法是，先把1~n个数放在数组里，然后通过dfs，从数组的最后两位开始交换位置，得到所有的排列方式，并在每一次得到新的排列方式时判断是否满足条件12。
但是这样写出的代码不仅需要全排列每一种情况，而且在我测试时还发现有大部分时间浪费在无用的循环之中。

2.代码实现

class Solution {
    public int countArrangement(int n) {
        int[]arr=new int[n];
    	
    	for (int i = 0; i <n; i++) {
			arr[i]=i+1;
		}
    	
    	return dfs(arr,0);
    }

   public int dfs(int[]arr,int t) {
    	
    	if (t==arr.length) {
    		//System.out.println("------------");
    		//条件一
    		for (int i = 0; i < arr.length; i++) {
				if (arr[i]%(i+1)!=0&&(i+1)%arr[i]!=0) {
					return 0;
				}
			}
    		//test(arr, num, t);
    		
    		return 1;
		}
    	int num=0;
    	for (int i = t; i < arr.length; i++) {
			jh(i, t, arr);
			num+=dfs(arr,t+1);
			jh(i, t, arr);
		}
    	return num;
	}
    
    public void jh(int i,int t,int[]arr) {
		int temp=arr[i];
		arr[i]=arr[t];
		arr[t]=temp;
	}
 }

超时。

方法二：dfs+爆搜

1.思想：

上一个方法是先组合再判断
这个方法就是先判断再组合了，判断目前没有被用到的数字，如果这个数字在当前位置可以存在，则标记为已用，把这个数放入数组，进行下一位上数字的判断，如果不可以存在，则换一个还未用的数字进行判断。

2.代码实现

class Solution {
    public int countArrangement(int n) {
        //标记数字是否已用过
    	boolean[]isflag=new boolean[n+1];
    	return dfs(n,1,isflag);
    }

    public int dfs(int n,int i,boolean[] isflag) {//总长度，当前所在位置
    	
    	//结束条件
    	if (i>n) {
    		//此时最后一位的数字已经选好，代表得到了一个优美排列
			return 1;
		}
    	
    	//计数
    	int num=0;
    	
    	//j代表可以放入当前数组的数字，具体能不能放入还要在下一步判断
    	for (int j = 1; j <=n ; j++) {
    		//如果满足条件则可以
			if (isflag[j]==false&&(j%i==0||i%j==0)) {
				isflag[j]=true;
				num+=dfs(n, i+1, isflag);//进入下一个位置
				//回溯
				isflag[j]=false;
			}
		}
    	return num;
    	
	}
 }

节省了很多时间

方法三：dfs+状态压缩

1.思想：

首次接触状态压缩。
题目给的限制条件是：n不会超过15，所以，我们可以使用状态压缩，用一个 int 类型的变量代替 isflag数组
先说说什么是状态压缩：
例如(000…0101) 2这个二进制数代表值为 1 和值为 3 的数字已经被使用了，而值为 2 的节点尚未被使用。
然后再来怎么用状态压缩达到判断的要求：
假设int isflag 存放了数字的使用情况，当我们需要检查值为 num 的数是否被使用时，可以使用位运算 a =（1 << (j-1)) & isflag，就是1的二进制数左移j-1位然后和isflag进行与运算，获取 isflag 二进制表示中第 j 位的值，如果 a 为 1 代表值为 j的数字已被使用，如果为 0则未被访问。
本质就是用位运算缩短计算时间。

2.代码实现

class Solution {
    public int countArrangement(int n) {
        return dfs(n,1,0);
    }

    public int dfs(int n,int i,int isflag) {//总长度，当前所在位置
    	//结束条件
    	if (i>n) {
    		//此时最后一位的数字已经选好，代表得到了一个优美排列
			return 1;
		}
    	
    	//计数
    	int num=0;
    	
    	//j代表可以放入当前数组的数字，具体能不能放入还要在下一步判断
    	for (int j = 1; j <=n ; j++) {
    		//如果满足条件则可以
			if (((1<<(j-1))&isflag)==0&&(j%i==0||i%j==0)) {
				num+=dfs(n, i+1,(1<<(j-1))|isflag);//进入下一个位置,并改变isflag
			}
		}
    	
    	return num;
    	
	}
 }