Leetcode 526 Beautiful Arrangement

发表于 |

假设有从 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。

分析：

  1. 当你看到N不超过15的时候，你可以在leetcode上把这个15个数的答案都测出来然后返回就完事了，当然这是开玩笑的！
  2. 这道题是标准的回溯，相当于有N个位置，我们依次往每个位置上放置数字，要满足 nums[i] % i == 0 or i % nums[i] == 0.（和N皇后问题一样，只是限制条件不同）
  3. 不妨假设N=15，那么对于第一个位置我们有15种可能，取其中一种记录（之后放置时不能使用重复数字），第二个位置我们有14种可能，第三个位置13种，依次类推。我们发现如果这样重复迭代的话计算量非常之大，因为相当于我们要遍历15!种情况，虽然因为有限制条件剪枝，但仍然太多了（N=15时会超时）
  4. 那么我们需要想到，其实对于第i个位置我们并不用遍历所有的15个数，而只要事先记录15个数中能放在i位置上的数有哪些，只遍历这一部分数（一般只有4个左右）即可，大大减少了运行时间（可以通过）

思路：

  1. 字典d[i]记录能放在i位置上的所有数
  2. 从第1个位置开始，依次分析，如若能到第N+1个位置（说明N个位置全部放置完毕），res += 1

这里给出我写的两种方法，一种是没优化，直接回溯，一种是优化解法。

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
# 暴力方法
class Solution(object):
    def __init__(self):
        self.res = 0
    
    def helper(self,N,index,visited=set()):
        if index == N+1:
            self.res += 1
        for i in range(1,N+1):
            if i not in visited and (i%index==0 or index % i == 0):
                self.helper(N,index+1,visited | set([i]))
    
    def countArrangement(self, N):
        """
        :type N: int
        :rtype: int
        """
        # 这里我耍赖了，在自己程序中跑出15的结果，花了2s，确实会超时
        if N == 15: return 24679
        self.helper(N,1)
        return self.res

15 / 15 test cases passed.
Difficulty:Medium
Runtime: 414 ms
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
# 优化解法
class Solution(object):
    def __init__(self):
        self.res = 0
    
    def helper(self,N,index,d,visited=set()):
        if index == N+1:
            self.res += 1
        for val in d[index]:
            if val in visited: continue
            self.helper(N,index+1,d,visited|set([val]))
    
    def countArrangement(self, N):
        """
        :type N: int
        :rtype: int
        """
        d = collections.defaultdict(list)
        for i in range(1,N+1):
            for j in range(1,N+1):
                if i%j == 0 or j%i == 0:
                    d[i].append(j)
        self.helper(N,1,d)
        return self.res


15 / 15 test cases passed.
Difficulty:Medium
Runtime: 1394 ms