Problem
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:
The number at the ith position is divisible by i.
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:
N is a positive integer and will not exceed 15.
題意
輸入整數(shù)N料饥，表示有N個數(shù)需要放置在N個位置上（數(shù)字和位置的下標(biāo)都是從1到N），如果能夠找出一個序列中任意一個數(shù)都滿足以下兩個條件中的一個哎甲，則將這個序列稱為一個Beautiful Arrangement：
- arr[i]能夠被i整除芽隆，i = 1, 2, ..., N
- i能夠被arr[i]整除僵闯，i = 1, 2, ..., N
對于給出的N奉呛，要求計算出共有多少種Beautiful Arrangement.
分析
簡單分析該題可以發(fā)現(xiàn)藏杖，將N個數(shù)字放置在N個位置上懂盐，這樣的問題是較為典型的回溯問題：假設(shè)前i個數(shù)字已經(jīng)放置好（滿足條件1或條件2）竭恬，則對于第i+1個位置跛蛋，如果能從還未被放置的數(shù)字集合unused（或visited）中找到一個滿足條件的數(shù)字k，則將其放在第i+1個位置痊硕，同時將k從unused中去掉（或者將visited[k - 1]標(biāo)記為true）问芬，繼續(xù)對第i+2執(zhí)行相同的操作（通過遞歸調(diào)用）；如果找不到滿足條件的數(shù)字寿桨，則回溯到上一層此衅，修改第'i'個位置的數(shù)字，再嘗試第'i+1'個位置···依此類推亭螟。
遞歸的base case應(yīng)當(dāng)是遞歸樹的高度達(dá)到了N挡鞍，如果當(dāng)前層次為第N層，則表示從0到N-1層得到的這條路徑是一個Beautiful Arrangement预烙，count++墨微。
Code
對于回溯同樣也有不同的實現(xiàn)，下面貼出兩段代碼扁掸，都用到了回溯的思想翘县，但在具體的實現(xiàn)上有所不同最域。
使用visited
//主要的思想是從后向前開始遞歸，即遞歸樹的根節(jié)點是最后一個元素
//使用visited數(shù)組標(biāo)識數(shù)字i是否已經(jīng)被使用過
//Runtime: 19ms
class Solution {
private:
vector<bool> visited;
int count;
void _dfs(int N, int nextPos){
if (nextPos == 0){
count++;
return;
}
for (int i = 1; i <= N; i++){
//該數(shù)字已經(jīng)被使用 || 兩個條件都不滿足
if (visited[i - 1] || nextPos % i != 0 && i % nextPos != 0)
continue;
visited[i - 1] = true;
//深入
_dfs(N, nextPos - 1);
//回溯
visited[i - 1] = false;
}
}
public:
int countArrangement(int N){
count = 0;
visited.resize(N);
for (int i = 0; i < N; i++) visited[i] = false;
_dfs(N, N);
return count;
}
};
使用swap
//這是Solution中效率很高的一份代碼锈麸，貼在這里以供學(xué)習(xí)
//同樣是從后向前镀脂，這個解法的作者使用swap函數(shù)代替了visited數(shù)組，主要思路如下：
//1. 初始化一個數(shù)組容器v忘伞，存放的元素為[1...N]（不包括0）
//1. 假設(shè)后面的下標(biāo)從p+1到N-1的位置都已經(jīng)放置好薄翅，考慮下標(biāo)為p的位置
//2. for(int i = 0; i < p; i++) 遍歷從v[0]到v[p-1]的數(shù)，如果v[i]滿足條件氓奈，則將v[i]與v[p-1]交換
//3. 再次遞歸時翘魄，需要考慮的就只是下標(biāo)從0到p-1的位置該如何放置了
//4. 返回結(jié)果時，再將v[i]與v[p-1]交換回來
//Runtime: 6ms
class Solution {
private:
int _count(int n, vector<int>& v){
if (n <= 1) return 1;
int result = 0;
for (int i = 0; i < n; i++){
if (v[i] % n == 0 || n % v[i] == 0){
swap(v[i], v[n - 1]);
result += _count(n - 1, v);
swap(v[i], v[n - 1]);
}
}
return result;
}
public:
int countArrangement(int N) {
vector<int> v;
v.resize(N);
for (int i = 0; i < N; i++) v[i] = i + 1;
return _count(N, v);
}
};
