欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

leetcode练习 Beautiful Arrangement

程序员文章站 2022-04-25 10:40:47
...

第一节课没讲什么内容,主要就是斐波那契数列,因此想找一个递归相关的题目,但是递归内容的几道题全部都要氪金…
就找了个回溯的题目。。小试牛刀,选了中等难度的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:

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?

乍一看是个全排列问题,不过可以在排列的过程中提前判断是否符合条件。
代码如下:

class Solution {
public:
    void beautiful(int beg, int end, int &cnt, vector<int> arr) {
    if (beg == end) {
        //judgement
        if ((beg % arr[beg] == 0) || (arr[beg] % beg == 0)) {
            cnt++;
        }
    } else {
        for(int i = beg; i <= end; i++) {
            int temp = arr[beg];
            arr[beg] = arr[i];
            arr[i] = temp;
            if ((beg % arr[beg] == 0) || (arr[beg] % beg == 0)) {
                beautiful(beg+1, end, cnt, arr);
                temp = arr[i];
                arr[i] = arr[beg];
                arr[beg] = temp;
            }
        }
    }
}
    int countArrangement(int N) {
        int cnt = 0;
    int beg = 1;
    vector<int> arr;
    arr.push_back(0);
    for (int i = 1; i <= N; i++) arr.push_back(i);
    beautiful(beg, N, cnt, arr);
    return cnt;
    }
};

我这里取巧把数组第一位默认设为0,这样可以不用考虑+1,-1的问题。
过程没什么好说的,在begin位与i位交换之后,判断begin位是否符合条件,如果符合条件,将begin位固定,后面几位继续递归调用,以此类推,如果所有都符合条件,cnt++。

难度不大,也没遇到什么困难,一次性写完了,不过速度方面并不优秀

leetcode练习 Beautiful Arrangement

可能因为是使用了递归的方式,如果用非递归的方式,可以做到更快。但本身这道题目应该是鼓励使用递归思想实现(N<15),就不再画蛇添足了。

相关标签: leetcode 递归