LeetCode刷题【526】优美的排列

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

1. 第 i 位的数字能被 i 整除
2. 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 整除

说明:

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

题解

8月16日的每日一题，一开始拿到题目有点不理解，反复看了几遍，大意就是，1-15的数字，任意排序，索引0的位置忽略（这样实际需要的是一个长度为16的数组），保证索引i的位置上的数字，要么能整除i，要么能被i整除。

明白了题意就好办了，和之前的拨轮盘一样，用回溯来处理。

import java.util.*;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {

    Map<Integer, List<Integer>> map = new HashMap<>();
    Set<Integer> visited = new HashSet<>();
    int count = 0;
    int length = 0;
    public int countArrangement(int n) {
        length = n;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (!map.containsKey(i)){
                    map.put(i,new ArrayList<>());
                }
                if (i%j==0 || j%i==0){
                    map.get(i).add(j);
                }
            }
        }
        backtrack(1);
        return count;
    }

    void backtrack(int index) {
        if (visited.size() == length){
            count++;
            return;
        }
        for (Integer matchNum : map.get(index)) {
            if (!visited.contains(matchNum)){
                visited.add(matchNum);
                backtrack(index+1);
                visited.remove(matchNum);
            }
        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)