LeetCode 526. Beautiful Arrangement

版权声明:本文为博主原创文章,转载请注明出处,谢谢!

版权声明:本文为博主原创文章,转载请注明出处:http://blog.jerkybible.com/2017/02/28/LeetCode-526-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.

题意解析

所谓美丽的排布是指,在i位置上的数字能够整除i或者被i整除,i从1开始。给定一个数字N,计算有多少个这样的排布。

解法分析

这道题的主要解法就是回溯,回溯的核心是使用一个数组(假设叫used),这个数组表示这个排布中的某一个数字(用数组下标表示)是否被使用,因为从1开始,所以数组的长度为N+1

先从第1个位置找合适的数字,如果数字合适然后这个数字没有被使用则将used数组对应下标设为已使用,以此类推。回溯的时候只需要将前面使用的标记为未使用就可以了。

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public int countArrangement(int N) {
if (N == 0) {
return 0;
}
int[] used = new int[N + 1];
return findRight(N, 1, used);
}
private int findRight(int maxNumber, int position, int[] used) {
if (position > maxNumber) {
return 1;
}
int rightNumber = 0;
for (int i = 1; i <= maxNumber; i++) {
if (used[i] == 0 && (position % i == 0 || i % position == 0)) {
used[i] = 1;
rightNumber += findRight(maxNumber, position + 1, used);
used[i] = 0;
}
}
return rightNumber;
}