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

代码就非常直接了:

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