Leetcode【526、667、932】

题目描述：【DFS】526. Beautiful Arrangement

解题思路：

这道题是一道构造题，即构造一个长度为 N 的自然序列，满足整除关系： i % nums[i] = 0 或 nums[i] % i = 0（i 为第 i 个位置）。由于看到数据范围 N <= 15，因此很容易想到这道题用深搜（DFS）去做。

刚开始的做法是先通过 DFS 构造出一个个完整的序列，然后再对完整序列判断每个位置是否满足要求，结果 TLE 了。后来又想了一下，其实可以在构造的过程中就判断当前构造的这个序列的每个位置是否满足上述整除关系，如果有一个位置不满足，就不用继续构造下去了（即相当于剪枝操作）。这样省了一大笔时间，题目就 AC 了。

Python3 实现：

class Solution:
    def __init__(self):
        self.b = [False] * 16  # 标记数字 i 是否被使用过
        self.ans = 0  # 结果
    
    def countArrangement(self, N: int) -> int:
        self.search(N, 1)
        return self.ans
        
    def search(self, N, r):
        for i in range(1, N+1):
            if self.b[i] == False and (i % r == 0 or r % i == 0):  # 如果不满足整除关系，就不用继续搜索该组解
                self.b[i] = True
                if N == r:  # 找到一组解
                    self.ans += 1
                else:
                    self.search(N, r+1)
                self.b[i] = False  # 恢复，回溯一步

题目描述：【Math】667. Beautiful Arrangement II

解题思路：

这道题是一道构造题，即构造一个长度为 n 的自然序列，这个序列相邻元素差的绝对值的数量为 k 个。看到数据范围是 10^4，首先排除用 DFS 的方法构造序列，然后判断是否满足题意的这种做法。

但是，乍一看也没有什么思路。因此需要从数学的角度找找规律。首先可以确定一点：对于长度为 n 的序列，元素差最多为 n-1 个，且这 n-1 个差分别为 1~(n-1)。这 n-1 个差的构成也很容易发现，较小的数和较大的数交替形成的序列就满足要求。

举个例子，假设 n = 8，k = 7，那么这个序列就是 1 8 2 7 3 6 4 5，形成的 k 个元素差为：7 6 5 4 3 2 1；若 k 不等于 n-1，假设 k = 4，我们只需要按上述规律形成满足长度为 k+1 的序列，剩余元素按递增顺序安排即可（剩余数的差值都为 1），最终得到的序列是：(1 5 2 4 3) 6 7 8，形成的 k 个元素差为：(4 3 2 1) 3 1 1（后面 3 个数的差值为 1）。

时间复杂度为 O(n)。

Python3 实现：

class Solution:
    def constructArray(self, n: int, k: int) -> List[int]:
        ans = [1]
        cnt = 1
        for i in range(n):
            if k > 0:
                if cnt % 2 == 1:  # 下一个数为较大的数
                    ans.append(ans[-1]+k)
                else:  # 下一个数为较小的数
                    ans.append(ans[-1]-k)
                k -= 1
                cnt += 1
            else:
                break
        for i in range(cnt+1, n+1):  # 如果k<n-1，则安排剩余的数按递增顺序排列
            ans.append(i)
        return ans

题目描述：【Math】932. Beautiful Array

解题思路：

这道题也是一道构造题，即构造一个长度为 N 的自然序列，这个序列满足条件： 对于任意的 i < j < k，有 2 * A[k] != A[i] + A[j]。这个序列叫做美丽数组看到数据范围是 1000，首先也先排除用 DFS 的方法构造序列，然后判断是否满足题意的这种做法。

但是，乍一看也没有什么思路。因此需要从数学的角度找找规律。注意到，美丽数组有如下数学性质： 1、A 是一个漂亮数组，对于 A 中的位置 k，k 左边的都是奇数，k 右边的都是偶数（或者 k 左边的都是偶数，k 右边的都是奇数），因为这样安排就一定能保证 2 * A[k] != A[i] + A[j] （偶数 != 奇数 + 偶数 或 偶数 != 偶数 + 奇数）; 2、A 是一个漂亮数组，如果对 A 中所有元素加（或减）一个常数，那么 Ａ 还是一个漂亮数组； 3、A 是一个漂亮数组，如果对 A 中所有元素乘上一个常数，那么 Ａ 还是一个漂亮数组； 4、A 是一个漂亮数组，如果删除A 中的一些元素，那么 A 还是一个漂亮数组，因为是对于任意的 i < k < j 都有 2 * A[k] != A[i] + A[j]，删除一些元素并不会改变这种顺序； 5、A 是一个由奇数构成的漂亮数组，B 是一个偶数构成的漂亮数组，那么 A + B 也是一个漂亮数组，如: {1,5,3,7} + {2,6,4,8} = {1,5,3,7,2,6,4,8} 也是一个漂亮数组。

有了上述几条性质，我们就可以解决本题的构造问题了。

我们知道一个漂亮数组 A 可以分为奇数部分 A1 和偶数部分 A2（性质 1）。此时如果有一个漂亮数组 B，那么 2*B-1 是一个漂亮数组（性质 2、3）并且是奇数数组，而 2*B 也是一个漂亮数组（性质 2）并且是偶数数组。那么我们通过[2*B-1] + [2*B] 得到的必然也是一个漂亮数组（性质 5）。

所以我们从最简单的 ans = [1] 开始推导，构造奇数 [(2*i-1) for i in ans] + 偶数 [2*i for i in ans]拼接在一起成为新的美丽数组；如果当前构造的美丽数组的长度小于 N，就继续这个操作，就能使得得到的一直是美丽数组。因为每次构造的美丽数组的长度是 2 的整数次方，所以最后要把结果中小于等于 N 的留下来，大于 N 的数字删除即可（性质 4）。

因为构造的美丽数组的长度是随着 2 的整数次方增长的，因此外层循环是 O(logN) 级别，内层循环是 O(N) 级别，总时间复杂度为 O(N*logN)；空间复杂度为 O(N)。

Python3 实现：

class Solution:
    def beautifulArray(self, N: int) -> List[int]:
        ans = [1]  # 从[1]开始构造
        while len(ans) < N:  # 美丽数组长度小于N
            ans = [(2 * i -1) for i in ans] + [(2 * i) for i in ans]  # 性质2、3、5
        return [i for i in ans if i <= N]  # 性质4