leetcodeSolutionInPython/leetcode526 at master · wwx13/leetcodeSolutionInPython · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
假设有从 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


over_occr=[]
res_dic={}
index=1
count=0
def countArrangement(N,over_occr,index,count):
    """
    :type N: int
    :rtype: int
    """
    #存储结果 key:是排列元素索引 value:在该索引的满足优美的元素个数
    # count = -1
    # print(over_occr)
    if len(over_occr)==N:
        count+=1
        return count
    for n in range(1,N+1):
        if n not in over_occr:
            if n%index==0 or index%n==0:
                over_occr.append(n)
                index+=1
                count=countArrangement(N,over_occr,index,count)
                over_occr.pop()
                index=index-1
    return count


print(countArrangement(2,over_occr,index,count))