LC 932. Beautiful Array

https://leetcode.com/problems/beautiful-array/

在做这道题之前，我已经看到了它"divide and conquer"的标签，所以思路尽量上面靠。在我的印象中，DnC的方法应该是自顶向下的，以归并排序为例： a) 先找到pivot点，按照pivot点分为左右两部分 b) 然后分别处理这两部分。但是自顶向下的方法往这题上面套就非常别扭，假设我找到了A,B两个序列各自满足条件，那么如何将A,B混合起来呢？好像没有显然的办法。

我觉得lee同学的 解法非常巧妙。他的解法是从奇偶性出发的，如果A,B两个部分各自满足条件，而A是奇数序列，B是偶数序列的话，那么A+B肯定也是满足条件的。 但是如何考虑到奇偶性这个事情？使用自顶向下的方法是很难的，本质上这个方法更强调如何合并两个序列。但是使用bottom-up的方法可能就会容易并且自然一些， 在我看来bottom-up更强调如何构造出这个序列，如何从一个单元出发不断地扩展成为合乎要求的序列，这也就是构造的过程。

我毫不脸红地将答案“剽窃”过来了，这证明过程真是清晰流畅。

Beautiful Array Properties:

Saying that an array is beautiful, there is no i < k < j, such that A[k] * 2 = A[i] + A[j]

Apply these 3 following changes a beautiful array, we can get a new beautiful array.

A. Deletion: Easy to prove.

B. Addition:

If we have A[k] * 2 != A[i] + A[j],

(A[k] + x) * 2 = A[k] * 2 + 2x != A[i] + A[j] + 2x = (A[i] + x) + (A[j] + x)

E.g: [1,3,2] + 1 = [2,4,3].

C. Multiplication:

If we have A[k] * 2 != A[i] + A[j],

for any x != 0, (A[k] * x) * 2 = A[k] * 2 * x != (A[i] + A[j]) * x = (A[i] * x) + (A[j] * x)

E.g: [1,3,2] * 2 = [2,6,4]

---

With the observations above, we can easily construct any beautiful array. Assume we have a beautiful array A with length N

• A1 = A * 2 - 1 is beautiful with only odds from 1 to N * 2 -1
• A2 = A * 2 is beautiful with only even from 2 to N * 2
• B = A1 + A2 beautiful array with length N * 2

代码就非常直接了：

class Solution:
    def beautifulArray(self, N: int) -> List[int]:
        res = [1]
        while len(res) < N:
            a = [2 * x - 1 for x in res if (2 * x - 1) <= N]
            b = [2 * x for x in res if (2 * x) <= N]
            res = a + b
        return res