【LeetCode】526. Beautiful Arrangement【M】【35】【回溯】

本文主要是介绍【LeetCode】526. Beautiful Arrangement【M】【35】【回溯】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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.

class Solution(object):def countArrangement(self, N):'''        def check(num):#print 'check',numfor i in range(len(num)):if num[i] % (i+1) != 0 and (i+1) % num[i] != 0:return 0return 1def bt(pos,res,n,num):if pos == n:res += check(num)return resfor i in xrange(0,pos+1):temp = num[:i]+[pos+1]+num[i:]res = bt(pos+1,res,n,temp)return resreturn bt(1,0,N,[1])'''self.res = 0def bt(N,pos,visited):if pos > N:self.res += 1#print self.resreturn for i in xrange(1,N+1):#print i,N+1if visited[i] == 0 and (i % pos == 0 or pos % i == 0):#print i,N,pos,visited,self.resvisited[i] = 1bt(N,pos+1,visited)visited[i] = 0bt(N,1,[0]*(N+1))return self.res""":type N: int:rtype: int"""

这篇关于【LeetCode】526. Beautiful Arrangement【M】【35】【回溯】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---