[Swift]LeetCode526. 优美的排列 | Beautiful Arrangement

it2022-05-06  2

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★➤微信公众号:山青咏芝(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。
Runtime: 52 ms Memory Usage: 18.5 MB 1 class Solution { 2 func countArrangement(_ N: Int) -> Int { 3 var nums:[Int] = [Int](repeating:0,count:N) 4 for i in 0..<N 5 { 6 nums[i] = i + 1 7 } 8 return helper(N, &nums) 9 } 10 11 func helper(_ n:Int,_ nums:inout [Int]) -> Int 12 { 13 if n <= 0 {return 1} 14 var res:Int = 0 15 for i in 0..<n 16 { 17 if n % nums[i] == 0 || nums[i] % n == 0 18 { 19 (nums[i], nums[n - 1]) = (nums[n - 1], nums[i]) 20 res += helper(n - 1, &nums) 21 (nums[i], nums[n - 1]) = (nums[n - 1], nums[i]) 22 } 23 } 24 return res 25 } 26 }

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


最新回复(0)