526. 优美的排列

leetcode原题： 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。

解答

总体思路就是

1. 先计算出来每个位上满足条件1或者条件2的数字的集合
2. 然后采用排列组合，遍历每个位所有可能性；这个过程中注意要排除掉前面位已经用过的数字；每个位在用一个数字时标志为1，用完之后要记得标志为0，便于后续使用

class Solution {
    //标志一个数字是否已经被使用
    int[] usedMap;
    //每个位满足条件的数字列表
    LinkedList<Integer>[] lists;
    int N;
    //总数目
    int counts = 0;

    public int countArrangement(int n) {
        N = n;
        usedMap = new int[n + 1];
        lists = new LinkedList[n + 1];
        for (int i = 0; i < n + 1; i++) {
            lists[i] = new LinkedList<>();
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (j % i == 0 || i % j == 0) {
                    //满足条件
                    lists[i].add(j);
                }
            }
        }
        for (Integer num : lists[1]) {
            usedMap[num] = 1;
            int okCounts = isOk(2, 1);
            usedMap[num] = 0;
            counts += okCounts;
        }
        return counts;
    }

    public int isOk(int i, int condition) {
        if (i > N) {
            return 1;
        }
        int counts = 0;
        for (Integer num : lists[i]) {
            if (usedMap[num] == 1) {
                continue;
            }
            usedMap[num] = 1;
            int okCounts = isOk(i + 1, condition);
            usedMap[num] = 0;
            counts += okCounts;
        }
        return counts;
    }
}