LeetCode932 漂亮数组

发表于 | 分类于 |
字数统计: 506 | 阅读时长 ≈ 2

链接： https://leetcode-cn.com/problems/beautiful-array/description/

题面

对于某些固定的N，如果数组A是整数1, 2, ..., N组成的排列，使得：对于每个i < j，都不存在k满足i < k < j使得A[k] * 2 = A[i] + A[j]。

解法

这道题还是有点难做的，主要用到的是分治的思想
但是如何进行分治求解需要用到一些trick以及奇偶数的一些性质
重点：
如果·{ X, Y, Z }是一个漂亮数组，则{ k * X + b, k * Y + b, k * Z + b }也一定是漂亮数组
奇数 + 偶数 = 奇数 一定成立

所以可以将数组分为left和right两部分进行处理
如果left部分为漂亮数组且都为奇数，right部分为漂亮数组且都为偶数，则合并后也一定是漂亮数组
因为奇数+偶数一定等于奇数

所以初试所有数组均为1，然后分治处理左半边和右半边的数组
处理完后将left数组所有数*2-1，right数组所有数乘以2，就得到了一个扩充后的漂亮数组
还是挺巧妙的
有两种写法，差异不大，个人更喜欢直接分治的做法，当然也可以加记忆化处理

代码

纯粹分治

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<int> beautifulArray(int n) {
        vector<int> ans(n, 1);
        part(0, n - 1, ans);
        return ans;
    }
    void part(int l, int r, vector<int>& ans) {
        if (r <= l) return;
        int mid = l + (r - l) / 2;
        part(l, mid, ans);
        part(mid + 1, r, ans);
        for (int i = l ; i <= mid; i++) {
            ans[i] = ans[i] * 2 - 1;
        }
        for (int i = mid + 1; i <= r; i++) {
            ans[i] = ans[i] * 2;
        }
    }
};

记忆化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    unordered_map<int, vector<int> > mp;
    vector<int> beautifulArray(int n) {
        if (n == 1) {
            return {1};
        }
        if (mp.find(n) != mp.end()) {
            return mp[n];
        }
        vector<int> ret;
        for (int i: beautifulArray((n + 1) / 2)) {
            ret.push_back(i * 2 - 1);
        }
        for (int i: beautifulArray(n / 2)) {
            ret.push_back(i * 2);
        }
        mp[n] = ret;
        return ret;
    }
};