Leetcode 932 Beautiful Array

发表于 |

对于一个确定的N，一个数组A是漂亮的，当前仅当满足以下条件：

  1. 数组是1,2,…,N的一个迭代
  2. 对于任意的i,k,j(i < k < j)，不存在A[k] * 2 = A[i] + A[j].

现在给定一个N，请你找出一个漂亮的数组A。

Example 1:
Input: 4
Output: [2,1,4,3]
Example 2:
Input: 5
Output: [3,1,2,5,4]

Note:

  1. 1 <= N <= 1000

题意分析：
这道题有点东西奥，找到一个1,2,…,N的某种排列，使得对于任意的A[i],A[k],Aj，都满足A[k] * 2 != A[i] + A[j].

着重写一下我思考这道题时候的思维过程

思路分析：
前半部分是我自己的思维过程，虽然是错误的过程，但我想将这整个想法写下来，想直接看正确答案的可以跳到下面标记处

刚看到这道题的时候说实话没什么思路，就在暴力法自己一个一个写，看能不能找到什么规律出来

对于N=5，有A = [3,1,2,5,4]，那么我就在想，现在加一个6，能加在哪呢？
我首先想的是往两边的某个地方加，因为如果可行的话就可以直接dp了

加在最左边行吗？不行，因为有6,5,4（第一种情况）
加在最右边行吗？不行，因为有2,4,6（第二种情况）
那加在哪能行呢？要避开刚才的两种情况，只能是在5和4的中间加，[3,1,2,5,6,4]
但是这样就没规律了啊，因为有第二种情况的存在，所以6是不能加在4的右边的，又因为第一种情况的存在，6也不能在5的左边。那我手动把5移动一下呢，因为5和左边的数组都不冲突

我就把数组变成了[3,1,5,2,4],现在6就可以有两种方式往里放：
[3,1,5,6,2,4], [3,1,5,2,6,4]

但这样好像还是很蠢，只是把6能加的位置增多了而已，还是没有什么规律，我在这里为了强行找到某种规律（就是想把6加到边界的地方），我手动把2,4换了一下位置
那么有： A = [3,1,5,4,2,6]，诶这样就舒服了！

那么7能不能加到边界的地方呢，如果又能加在最左边感觉规律就有了啊！
发现好像还真可以诶，此时 A = [7,3,1,5,4,2,6]

要是现在8又能加到最右边就可以证明我想的这个规律是正确的了。
但是很可惜并不能，因为[4,6,8]不符合题意，但这时候我发现了另一个规律
如果我把8加到4左边，A = [7,3,1,5,8,4,2,6]

正确答案直接从这里看：
那么此时奇数部分和偶数部分大小顺序的排列是一致的，并且只要其中一个符合题目规律另一个也一定符合。

我觉得我自己想明白了，就先找偶数部分的排列，然后把奇数的排列按照偶数的顺序加上去就好了
此时我分析[8,4,2,6]，想分析10能放在哪，突然发现此时是可以先约分的，反正题目规定的是求和不等嘛，等式两边除2不影响结果。
一除之后规律就出来了：
奇数部分 odd = [7,3,1,5]`
偶数部分(约分) even = [4,2,1,3]
发现有 odd = even*2 - 1，而even又恰好是n//2的一个排列情况，递归方程式豁然开朗！

f(n) = f(n//2) * 2 + f(n-n//2) * 2 - 1
因为涉及到重复计算，所以用到了记忆化的思想。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 28ms
class Solution(object):
    def beautifulArray(self, N):
        cache = {}
        def solve(N):
            if N == 1: return [1]
            if N in cache: return cache[N]
            
            even_index = N // 2
            odd_index = N - even_index
            even = solve(even_index)
            odd = solve(odd_index)
            even = [2*val for val in even]
            odd = [2*val-1 for val in odd]
            cache[N] = even + odd
            return cache[N]
        return solve(N)