0%

LeetCode 526. Beautiful Arrangement

Posted on Edited on In

题目

原题在此
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.
    Given an integer n, return the number of the beautiful arrangements that you can construct.

Example 1:
Input: n = 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.

Example 2:
Input: n = 1
Output: 1

Constraints:

  • 1 <= n <= 15

解析

暴力搜索的情况,需要遍历所有可能的排列(permutation),此时复杂度为$O(N)$.
改进的思路也简单,在全排列的过程中,如果一个分支出现了不满足题意的情况,则该分支下的所有排列都不可能是”Beautiful Arrangement”.
用一个bool数组来记录每个数字的使用情况,然后从位置1开始尝试放入1-N的每个数字,此时:

  • 若该数字还没有被使用且符合题目要求,尝试下一个位置.
  • 若该数字不符合要求,继续看下一个数字是否能放在当前位置.
  • 都放完了的时候即是一个”Beautiful Arrangement”, count 加一.

此时时间复杂度为$O(k)$, k为有效排列的个数.空间复杂度为$O(N)$,使用了一个长度为$n$的数组.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int used[16] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
    int count = 0;
    int countArrangement(int n) {
        dfs(1, n);
        return count;
    }
    
    void dfs(int pos, int n) {
        if(pos > n) {
            count++;
            return;
        }
        for(int i = 1; i <= n; ++i) {
            if(!used[i] && (!(i % pos) || !(pos % i))) {
                used[i] = 1;
                dfs(pos + 1, n);
                used[i] = 0;
            }            
        }
    }
};