Leetcode_526. 优美的排列

题目

526. 优美的排列
难度：中等
假设有从 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）
链接：https://leetcode-cn.com/problems/beautiful-arrangement
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

方法零：流氓方法

因为题目说明了N不会超过15，那就用例测试所有的数得到答案，然后用列表或者一串if语句就可以通过了。

方法一：回溯

思路

本来就隐约觉得会用到回溯算法，但还是想先用排列组合的方法试一下，但太太困难了，最后还是用了回溯算法。
先创建一个字典d，可以理解成键是第几个位置，对应的值是该位置上能放哪些数。
接下来是回溯函数，设置两个参数，第一个是用于记录当前状态的列表，第二个是现在要填的是哪一个位置pos，返回当前状态下的优美排列数c。
c初始设为0，i遍历可以在pos位置上的所有数，即d[pos]，如果i不在列表之内，就将它填到列表的对应位置上，并c += func(s, pos+1)，递归到下一个pos中，直到pos==n时，c += 1。
可能还是直接看代码清楚一些吧。

代码

def countArrangement(n):
    d = defaultdict(list)
    # 第num个位置上可以放哪些数
    for num in range(1, n+1):
        for i in range(1, num+1):
            if num % i == 0:
                d[num].append(i)
                if num != i:
                    d[i].append(num)

    def func(s, pos):
        c = 0
        for i in d[pos]:
            if i not in s:
                s[pos-1] = i
                if pos == n:
                    c += 1
                else:
                    c += func(s, pos+1)
                s[pos-1] = 0
        return c
    return func([0]*n, 1)

官方的回溯算法和我写得几乎一样，只是他用的是集合。我一开始也是想用集合的，但不知道集合的disturb方法，才改成了列表。

class Solution:
    def countArrangement(self, n: int) -> int:
        match = defaultdict(list)
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                if i % j == 0 or j % i == 0:
                    match[i].append(j)
        
        num = 0
        vis = set()

        def backtrack(index: int) -> None:
            if index == n + 1:
                nonlocal num
                num += 1
                return
            
            for x in match[index]:
                if x not in vis:
                    vis.add(x)
                    backtrack(index + 1)
                    vis.discard(x)
                   
        backtrack(1)
        return num

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/beautiful-arrangement/solution/you-mei-de-pai-lie-by-leetcode-solution-vea2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

方法二：状态压缩+动态规划

思路

这个方法实在难理解，借助官方题解下的评论才勉强看懂。也不知道什么叫状态压缩。
首先，是动态规划的状态表示。这里用二进制数表示，从右往左数，第i位上的数字是1，就表示i这个数字被选取了。创建长度为1<<n的数组f，表示某一状态下的优美排列数。
以n=6举例。f[000110]的意思是（这里下标里的数都是二进制数）：数字2和3能够组成的优美排列数。
所以，最后返回的结果就是f[1<<n -1]，即f[111111]。
然后是转移方程。f[111111] = f[011111] + f[101111] + f[110111] + f[111011] + f[111101] + f[111110]，也就是说，要算取了6个数的优美排列，就算上所有任意去掉这已经取了的6个数中的一个的状态的优美排列数。当然，事实上并不是所有的数都要相加，因为还需要判断，去掉的那个数能否放在第6个位置上。比如f[101111]这时数字5还没有取，而5并不能放在第6个位置上。
再举个例子。f[100110]是要算数字2、3和6这3个数的优美排列，那就看哪个数可以放在第3个位置上，这里6和3可以放在第3个位置上，而这时候已经取了的数字分别是2、3和2、6所以f[100110] = f[000110] + f[100010]。
因此，设计双重循环，外层mask循环遍历所有状态，内存i循环做的事情是从0（最右边）开始遍历mask的每一位，如果第i+1位上是1，并且这个1对应的数i+1能放在这个位置上（这句话的意思是：假装还没有取i+1这个数，此时已经取了num - 1个数，那 i+1能否放在num这个位置上，所以，num的意思就是要求的mask当中已经取了的数的数量，所以，num可以通过统计mask中有几个1来获得），那么f[mask]就可以加上这种状态下的优美排列数了。
还是结合代码进行理解吧。

代码

def countArrangement(n):
    # f[X] X是一个二进制数，
    # 例：f[000110]，表示数字2和3被选取后排在前面的优美排列数
    # 从右往左数，1表示被选
    f = [0]*(1 << n)
    f[0] = 1

    # 动态规划，mask 遍历1到 1<<n
    for mask in range(1, 1 << n):
        # 计mask有多少个1
        # 以100110举例例，mum=3
        # 也就是说，2、3、6被选取了，要放在前三个求他们呢的优美排列数
        # 那需要判断第3个位置（也就是第 num个位置）可以放谁，
        # 这里可以放3和6，
        # 前两个位置是2，6，f[100110] += f[100010]
        # 前两个位置是2，3，f[100110] += f[000110]
        num = bin(mask).count("1")
        for i in range(n):
            # mask & (1 << i  mask的第i+1位是不是1
            # 如果是，
            # i+1这个数能不能放在 num 这个位置上
            # 如果可以，
            # mask ^ (1 << i) mask的第i+1位改为0
            # f[mask] += f[mask ^ (1 << i)]
            # 注意i与i+1，i-1的区别含义
            if (mask & (1 << i) and (num % (i+1) == 0 or (i+1) % num == 0)):
                f[mask] += f[mask ^ (1 << i)]
        # for i in range(1,n+1):
        #     if (mask & (1 << (i-1)) and (num % i == 0 or i % num == 0)):
        #         f[mask] += f[mask ^ (1 << (i-1))]
    return f[(1 << n)-1]

盛日辉的博客

Leetcode_526. 优美的排列

题目

方法零：流氓方法

方法一：回溯

思路

代码

方法二：状态压缩+动态规划

思路

代码

提交记录