LeetCode526-优美的排列

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/beautiful-arrangement/

中文链接：https://leetcode-cn.com/problems/beautiful-arrangement/

题目详述

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

  1. 第 i 位的数字能被 i 整除

  2. i 能被第 i 位上的数字整除

现在给定一个整数 N，请问可以构造多少个优美的排列？

示例1:

1
2
3
4
5
6
7
8
9
10
11
输入: 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。

题目详解

  • 创建一个数组 arr 用来表示从 1 到 N 的数。
  • 运用回溯法判断当前排列是否满足要求（实际上回溯的过程就是在生成全排列的过程）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public class LeetCode_00526 {

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

    private int dfs(int[] arr, int s) {
        if (s == 0) {
            return 1;
        }
        int res = 0;
        for (int i = s; i > 0; --i) {
            swap(arr, s, i);
            if (arr[s] % s == 0 || s % arr[s] == 0) {
                res += dfs(arr, s - 1);
            }
            swap(arr, s, i);
        }
        return res;
    }

    private void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}
  • 同样也是回溯，不过是用访问标志来标志 1 到 N 的数是否被用过。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class LeetCode_00526 {
    
    public int countArrangement(int N) {
        boolean[] vis = new boolean[N + 1];
        return dfs(N, 1, vis);
    }

    private int dfs(int N, int s, boolean[] vis) {
        if (s > N) {
            return 1;
        }
        int res = 0;
        for (int i = 1; i <= N; ++i) {
            if (!vis[i] && (s % i == 0 || i % s == 0)) {
                vis[i] = true;
                res += dfs(N, s + 1, vis);
                vis[i] = false;
            }
        }
        return res;
    }
}
  • 动态规划。状态 f[S] 表示用去的数字集合为 S 的方案数，S 的二进制表示中，为 0 的位表示该数字未被使用，为 1 的位表示已经被用过。
  • 枚举所有的状态 i，即 [0, (1 << N) - 1]。统计 i 中 1 的个数得到当前代表的数，然后选择一个没有被使用过的数字 j，判断是否满足题目的条件。若满足则更新。
  • 初试 f[0] = 1，最终结果为 f[(1 << N) - 1]，它对应的数字所有二进制位为 1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class LeetCode_00526 {

    public int countArrangement(int N) {
        int maxn = 1 << N;
        int[] f = new int[maxn];
        f[0] = 1;
        for (int i = 0; i < maxn; ++i) {
            int s = 1;
            for (int j = 0; j < N; ++j) {
                s += (i >> j) & 1;
            }
            for (int j = 1; j <= N; ++j) {
                if (((i >> (j - 1) & 1) == 0) && (s % j == 0 || j % s == 0)) {
                    f[i | (1 << (j - 1))] += f[i];
                }
            }
        }
        return f[maxn - 1];
    }
}