题解 | 「力扣」第 526 题:优美的排列(回溯、动态规划)

2021-08-16  本文已影响0人  李威威

「力扣」第 526 题:优美的排列

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

现在给定一个整数 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 整除

说明:

  1. N 是一个正整数,并且不会超过 15

关键字:满足如下两个条件中的一个。

方法一:回溯算法

本题用「回溯算法」就太麻烦了。

public class Solution {

    // 其实和第 46 题(全排列)差不多

    public int countArrangement(int n) {
        boolean[] visited = new boolean[n + 1];
        return dfs(n, 1, visited);
    }

    public int dfs(int n, int pos, boolean[] visited) {
        if (pos > n) {
            // 一次加 1 个
            return 1;
        }

        int res = 0;
        for (int i = 1; i <= n; i++) {
            if (!visited[i] && (pos % i == 0 || i % pos == 0)) {
                visited[i] = true;
                res += dfs(n, pos + 1, visited);
                visited[i] = false;
            }
        }
        return res;
    }
}

方法二:动态规划

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

这很可能是一个和位运算相关的问题。

参考资料:https://leetcode-cn.com/problems/beautiful-arrangement/solution/you-mei-de-pai-lie-by-leetcode-solution-vea2/1082657

public class Solution {

    // 用 mask 的二进制表示选取状态,n 个数字用 n 位表示,第 i 位为 1 代表数字 i + 1 已被选取(i 从 0 开始),n 中 1 的个数 m 代表前 m 位已放置
    // 例如:二进制 100110 共三个 1,代表排列的前三位已放置数字,三个 1 分别在二进制第 1、2、5 位置上(从右侧开始,从 0 开始计数)
    // 所以 2、3、6 三个数字被选取,综合起来就是表示:2 3 6 这三个数字被放到了排列的前三位,三个数字完美排列方式未知
    // 通过枚举 mask 进行计算

    public int countArrangement(int n) {
        // 状态定义:dp[6] = dp[000110] = 数字2、3在「前两位时」的完美排列数量
        int size = 1 << n;
        int[] dp = new int[size];
        dp[0] = 1;
        // 通过 mask 进行枚举,最终目的是为了得到二进制 mask = (11..11)n 时,总的完美排列数
        for (int mask = 1; mask < size; mask++) {
            // 目前已经有多少个 1
            int num = Integer.bitCount(mask);
            // 遍历 mask 的每一位,仍以 mask = 100110 为例,此 mask 代表 2 3 6 三个数字在排列的「前三位」
            // 求三个数字 2 3 6 的完美排列方式,则先确定 2 3 6 哪些数字能放到第三位,然后累加另外两个数字的完美排列数量来获得
            
            // liwei 注:下面这两个例子很重要,其实就是「分类计数」的「加法原理」
            // 2 3 6,第三位可以为 6,则 dp[100110] += dp[000110] (2、3在前两位时的完美排列数量)
            // 2 3 6,第三位可以为 3,则 dp[100110] += dp[100010] (2、6在前两位时的完美排列数量)
            for (int i = 0; i < n; i++) {
                // mask & (1<<i) 用来判断 mask 第 i 位是否为 1,如果为 1,说明第 i+1 个数字被选取
                // ((num % (i + 1)) == 0 || (i + 1) % num == 0) 判断被选取的数字 i+1 能否放到位置 num 上,
                // 即:先从被选取的数字中找到能放到最高位 num 的数字,然后将剩余 num-1 个数字的完美排列方式累加到f[mask]中
                if ((mask & (1 << i)) != 0 && ((num % (i + 1)) == 0 || (i + 1) % num == 0)) {
                    // mask ^ (1 << i) 将 mask 第 i 位设置为 0
                    dp[mask] += dp[mask ^ (1 << i)];
                }
            }
        }
        return dp[size - 1];
    }
}

以后「状态压缩」是不是可以出一个专题。

上一篇下一篇

猜你喜欢

热点阅读