★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★➤微信公众号：山青咏芝（shanqingyongzhi）➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）➤GitHub地址：https://github.com/strengthen/LeetCode➤原文地址：https://www.cnblogs.com/strengthen/p/10403153.html ➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★Suppose you have N integers from 1 to N. We define a beautiful arrangement as an array that is constructed by these N numbers successfully if one of the following is true for the ith position (1 <= i <= N) in this array:
The number at the ith position is divisible by i.i is divisible by the number at the ith position.Now given N, how many beautiful arrangements can you construct?
Example 1:
Input: 2 Output: 2 Explanation: The first beautiful arrangement is [1, 2]: Number at the 1st position (i=1) is 1, and 1 is divisible by i (i=1). Number at the 2nd position (i=2) is 2, and 2 is divisible by i (i=2). The second beautiful arrangement is [2, 1]: Number at the 1st position (i=1) is 2, and 2 is divisible by i (i=1). Number at the 2nd position (i=2) is 1, and i (i=2) is divisible by 1.Note:
N is a positive integer and will not exceed 15.假设有从 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。424ms
1 class Solution { 2 func countArrangement(_ N: Int) -> Int { 3 var used = [Bool](repeating: false, count: N + 1) 4 var result = 0 5 backtrack(1, N, &used, &result) 6 return result 7 } 8 9 private func backtrack(_ position: Int, _ n: Int, _ used: inout [Bool], _ result: inout Int) { 10 if position > n { 11 result += 1 12 } else { 13 for i in 1...n where !used[i] && (position % i == 0 || i % position == 0) { 14 used[i] = true 15 backtrack(position + 1, n, &used, &result) 16 used[i] = false 17 } 18 } 19 } 20 }452ms
1 class Solution { 2 var count = 0 3 func countArrangement(_ N: Int) -> Int { 4 var elements: [Bool] = Array(repeating: false, count: N) 5 createNext(elements: &elements, position: 1, n: N) 6 return count; 7 } 8 9 func createNext(elements: inout [Bool], position: Int, n: Int) { 10 if position > n { 11 count += 1 12 return 13 } 14 for i in 0..<elements.count { 15 if !(!elements[i] && ( position % (i+1) == 0 || (i+1) % position == 0)) { continue; } 16 elements[i] = true; 17 createNext(elements: &elements, position: position+1, n: n) 18 elements[i] = false 19 } 20 } 21 }536ms
1 class Solution { 2 func countArrangement(_ N: Int) -> Int { 3 guard N > 0 else { return 0 } 4 5 var visited = Array.init(repeating: 0, count: N + 1) 6 var count = 0 7 func dfs(position: Int) { 8 9 if position > N { 10 count += 1 11 return 12 } 13 14 for i in 1..<(N+1) { 15 if visited[i] == 0 && (i % position == 0 || position % i == 0) { 16 visited[i] = 1 17 dfs(position: position + 1) 18 visited[i] = 0 19 } 20 } 21 22 } 23 24 dfs(position: 1) 25 return count 26 } 27 }820ms
1 class Solution { 2 func countArrangement(_ N: Int) -> Int { 3 var num = 0 4 var mark = Array(repeatElement(0, count: N + 1)) 5 insertNum(N: N, index: 1, mark: &mark, result: &num) 6 return num 7 } 8 9 func insertNum(N: Int, index: Int, mark: inout [Int], result: inout Int) { 10 if N == index - 1 { 11 result += 1 12 return 13 } 14 15 for j in 1...N { 16 if mark[j] == 0 && (j % index == 0 || index % j == 0) { 17 mark[j] = 1 18 insertNum(N: N, index: index + 1, mark: &mark, result: &result) 19 mark[j] = 0 20 } 21 } 22 } 23 }
转载于:https://www.cnblogs.com/strengthen/p/10403153.html
