[LeetCode]Beautiful Arrangement

题目描述:

LeetCode 526. Beautiful Arrangement

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:

  1. The number at the ith position is divisible by i.
  2. 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:

  1. N is a positive integer and will not exceed 15.

题目大意:

如果整数1到N的排列,第i个数满足下列规则之一,则称该排列为“美丽排列”

  1. 第i个位置的数字可以被i整除
  2. i可以被第i个位置的数字整除

给定数字N,求有多少个美丽排列

注意:N是正整数并且不超过15

解题思路:

记忆化搜索(Memoization)

搜索函数定义为:solve(idx, nums)

其中idx为当前数字的下标,nums为剩余待选数字

初始令idx = 1, nums = [1 .. N]

遍历nums,记当前数字为n,除n以外的其余元素为nums'

若n满足题设的整除条件,则将solve(idx + 1, nums')累加至答案

Python代码:

class Solution(object):
    def countArrangement(self, N):
        """
        :type N: int
        :rtype: int
        """
        cache = dict()
        def solve(idx, nums):
            if not nums: return 1
            key = idx, tuple(nums)
            if key in cache: return cache[key]
            ans = 0
            for i, n in enumerate(nums):
                if n % idx == 0 or idx % n == 0:
                    ans += solve(idx + 1, nums[:i] + nums[i+1:])
            cache[key] = ans
            return ans
        return solve(1, range(1, N + 1))

 

本文链接:http://bookshadow.com/weblog/2017/02/19/leetcode-beautiful-arrangement/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。

如果您喜欢这篇博文,欢迎您捐赠书影博客: ,查看支付宝二维码

Pingbacks已关闭。

评论
  1. juzi juzi 发布于 2017年2月25日 01:49 #

    我觉得这里并没有Memoization, 这里的key从1 到N 被依次计算,不会有hit cache提前return的时候,是我哪里理解有错么?

  2. 在线疯狂 在线疯狂 发布于 2017年2月25日 11:39 #

    不妨用一个小型测试用例,输出并观察key和nums,可以帮助理解。

张贴您的评论