Appearance
526. 优美的排列
原题链接：LeetCode 526. 优美的排列
题目描述
假设有从 1 到 n 的 n 个整数。用这些整数构造一个数组 perm（下标从 1 开始），只要满足下述条件 之一 ，该数组就是一个 优美的排列 ：
perm[i]能够被i整除i能够被perm[i]整除
给你一个整数 n ，返回可以构造的 **优美排列 **的 数量 。
示例 1：
- 输入： n = 2
- 输出： 2 解释： 第 1 个优美的排列是
[1,2]：- perm[1] = 1 能被 i = 1 整除
- perm[2] = 2 能被 i = 2 整除 第 2 个优美的排列是
[2,1]: - perm[1] = 2 能被 i = 1 整除
- i = 2 能被 perm[2] = 1 整除
示例 2：
- 输入： n = 1
- 输出： 1
提示：
1 <= n <= 15
难度： Medium
题解代码
javascript
/**
* @param {number} n
* @return {number}
*/
let count = 0
var countArrangement = function(n) {
const used = Array(n).fill(false)
count = 0
backTrack(n, [], used)
return count
};
function backTrack (n, path, used) {
if (path.length === n) {
return count++
}
for (let i = 1; i <= n; i++) {
if (!isBeatiful(i, path.length + 1)) continue
if (!used[i - 1]){
path.push(i)
used[i - 1] = true
backTrack(n, path, used)
used[i - 1] = false
path.pop()
}
}
}
function isBeatiful (val, idx) {
return parseInt(val / idx) === parseFloat(val / idx) ||
parseInt(idx / val) === parseFloat(idx / val)
}