力扣932.漂亮数组(构造/思维/递归)

2022年6月17日 下午4:57 杂项 , ,

上个月忙完了数电、计网、概率论,三门考试用了我三个十天,也就是一个月,这个月摆了很久,边摆边玩,写科工和算法课作业去了,还挺有意思的,这学期也差不多快结束了,只有数据结构和毛概没有结课了。嗯,毛概考试开卷,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}

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注