难度: Medium
原题连接
内容描述
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 - 时间复杂度: O(N!)- 空间复杂度: O(N)******
一个一个匹配，只有匹配上了才匹配下一个，因为不是每一个位置上可以整除的数字都很多，并且随着确定的数字越来越多，我们可以选择的数字也越来越少， 算法可以越来越快，我估摸着算是个O(N^2)的算法吧
class Solution(object):
def countArrangement(self, N):
"""
:type N: int
:rtype: int
"""
nums = [i+1 for i in range(N)]
self.res = 0
def permute(nums, cur_idx):
if cur_idx == len(nums):
self.res += 1
for i in range(cur_idx, N):
nums[i], nums[cur_idx] = nums[cur_idx], nums[i]
if nums[cur_idx] % (cur_idx+1) == 0 or (cur_idx+1) % nums[cur_idx] == 0:
permute(nums, cur_idx+1)
nums[cur_idx], nums[i] = nums[i], nums[cur_idx]
permute(nums, 0)
return self.res思路 2 - 时间复杂度: O(N!)- 空间复杂度: O(N)******
如果记录一下已经用过的数字可能会更快一点
beats 43.60%
class Solution(object):
def countArrangement(self, N):
"""
:type N: int
:rtype: int
"""
visited = [False] * (N+1)
self.res = 0
def cal(cur_idx, visited):
if cur_idx > N:
self.res += 1
for i in range(1, N+1):
if not visited[i] and (i % cur_idx == 0 or cur_idx % i == 0):
visited[i] = True
cal(cur_idx+1, visited)
visited[i] = False
cal(1, visited)
return self.res思路 3 - 时间复杂度: O(N!)- 空间复杂度: O(N!)******
用个cache记下来我们已经匹配过的情况
beats 97.60%
class Solution(object):
cache = {}
def countArrangement(self, N):
"""
:type N: int
:rtype: int
"""
def helper(i, nums):
if i == 1:
return 1
key = (i, nums)
if key in self.cache:
return self.cache[key]
total = sum(helper(i-1, nums[:idx] + nums[idx+1:])
for idx, num in enumerate(nums)
if num % i == 0 or i % num == 0)
self.cache[key] = total
return total
return helper(N, tuple(range(1, N + 1)))