力扣932.漂亮数组（构造/思维/递归）

上个月忙完了数电、计网、概率论，三门考试用了我三个十天，也就是一个月，这个月摆了很久，边摆边玩，写科工和算法课作业去了，还挺有意思的，这学期也差不多快结束了，只有数据结构和毛概没有结课了。嗯，毛概考试开卷，20单选20多选10判断二选一简答...嗯，扯远了。

题目描述

题目链接：932. 漂亮数组 - 力扣（LeetCode）
对于某些固定的 N，如果数组 A 是整数 1, 2, ..., N 组成的排列，使得：

对于每个 i < j，都不存在 k 满足 i < k < j 使得 A[k] * 2 = A[i] + A[j]。

那么数组 A 是漂亮数组。

给定 N，返回任意漂亮数组 A（保证存在一个）。

思路

A[k] * 2 = A[i] + A[j]，k在i和j的中间，可以想到让这两个其中一个变为一个奇数一个偶数，比如让A[i]为奇数，让A[j]为偶数。
然后我们将其分成两部分，左半边部分为奇数，右半边部分为偶数，比如{1,3,5,7,2,4,6}，但是这样肯定不行，因为2*3=1+5，所以我们要做一个线性化处理：
我们将所有数$x_i$同时变为$2\times x+1$，这样就全部变为奇数了；
我们将所有数$x_i$同时变为$2\times x$，这样就全部变为偶数了；

比如我们要将{1,2}和{1}合并（此时n=3），那么我们这时候对两个序列都进行线性化处理，这是和{1,2}变为{1,3}，{1}变为{2}，这样再合并则可以变为{1,3,2}，这是一个漂亮数组。

所以我们按照这个思想，一直往下划分，直到1为止，再往上递归回去。

代码

vector<int> dfs(int n)
{
    vector<int> res;
    if (n==1)
    {
        res.push_back(1);
        return res;
    }
    int odd = (n+1)>>1, even = n>>1;
    vector<int> left = dfs(odd);
    vector<int> right = dfs(even);
    for (auto x:left) res.push_back(2*x-1);
    for (auto x:right) res.push_back(2*x);
    return res;
}

结果

随便输出几个来看：

i = 1
{1}
i = 2
{1,2}
i = 3
{1,3,2}
i = 4
{1,3,2,4}
i = 5
{1,5,3,2,4}
i = 6
{1,5,3,2,6,4}
i = 7
{1,5,3,7,2,6,4}
i = 8
{1,5,3,7,2,6,4,8}
i = 9
{1,9,5,3,7,2,6,4,8}
i = 10
{1,9,5,3,7,2,10,6,4,8}
i = 11
{1,9,5,3,11,7,2,10,6,4,8}
i = 12
{1,9,5,3,11,7,2,10,6,4,12,8}
i = 13
{1,9,5,13,3,11,7,2,10,6,4,12,8}
i = 14
{1,9,5,13,3,11,7,2,10,6,14,4,12,8}
i = 15
{1,9,5,13,3,11,7,15,2,10,6,14,4,12,8}
i = 16
{1,9,5,13,3,11,7,15,2,10,6,14,4,12,8,16}