【Day 70 】2023-08-18 - 932. 漂亮数组

[azl397985856]

932. 漂亮数组

入选理由

暂无

题目地址

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

前置知识

• 分治

题目描述

对于某些固定的 N，如果数组 A 是整数 1, 2, ..., N 组成的排列，使得：

对于每个 i < j，都不存在 k 满足 i < k < j 使得 A[k] * 2 = A[i] + A[j]。

那么数组 A 是漂亮数组。

 

给定 N，返回任意漂亮数组 A（保证存在一个）。

 

示例 1：

输入：4
输出：[2,1,4,3]


示例 2：

输入：5
输出：[3,1,2,5,4]

 

提示：

1 <= N <= 1000

 

[freesan44]

class Solution {
    func beautifulArray(_ N: Int) -> [Int] {
        var cache = [Int: [Int]]()

        func dp(_ n: Int) -> [Int] {
            if n == 1 {
                return [1]
            }

            if let cachedResult = cache[n] {
                return cachedResult
            }

            var ans = [Int]()
            for a in dp(n - n / 2) {
                ans.append(a * 2 - 1)
            }
            for b in dp(n / 2) {
                ans.append(b * 2)
            }

            cache[n] = ans
            return ans
        }

        return dp(N)
    }
}

[Diana21170648]

思路

问题分解为子问题，递归解决，注意需要分为奇数和偶数

代码

class Solution:
    def beautifulArray(self, N: int) -> List[int]:
        @lru_cache(None)
        def dp(n):#递归调用
            if n==1:
                return [1]
            ans=[]
            for i in dp(n-n//2):
                ans+=[i*2-1]
            for j in dp(n//2):
                ans+=[j*2]
            return ans
        return dp(N)

复杂度分析

• 时间复杂度：O(2^N)，其中 N 为数组长度。
• 空间复杂度：O(N)

[GuitarYs]

class Solution:
    def beautifulArray(self, N):
        if N == 1:
            return [1]
        odds = self.beautifulArray((N + 1) // 2)  
        evens = self.beautifulArray(N // 2)  
        return [2*x - 1 for x in odds] + [2*x for x in evens]
solution = Solution()
N = 4
beautiful_array = solution.beautifulArray(N)
print(beautiful_array)

[Alexno1no2]

抄作业
# 将问题分解为子问题并进行递归求解。
# 具体来说，dp(n) 函数返回一个漂亮数组，长度为 n。它首先处理基本情况 n == 1，返回一个只包含元素 1 的数组。然后，通过递归调用 dp(n - n // 2) 和 dp(n // 2)，分别生成奇数部分和偶数部分，并将它们组合起来形成漂亮数组。

# 由于使用了缓存装饰器 @lru_cache(None)，已经计算过的 dp(n) 将会被缓存，避免重复计算，从而提高性能。

# 最终，return dp(N) 返回了长度为 N 的漂亮数组。

class Solution:
    def beautifulArray(self, N: int) -> List[int]:
        @lru_cache(None)  # 使用缓存来加速计算
        def dp(n):
            if n == 1:
                return [1]  # 基本情况，返回单个元素的数组
            ans = []
            # 生成奇数部分
            for a in dp(n - n // 2):
                ans += [a * 2 - 1]
            # 生成偶数部分
            for b in dp(n // 2):
                ans += [b * 2]
            return ans

        return dp(N)

[Fuku-L]

代码

class Solution {
    Map<Integer, int[]> memo;
    public int[] beautifulArray(int n) {
        memo = new HashMap();
        return f(n);
    }
    public int[] f(int n){
        if(memo.containsKey(n)){
            return memo.get(n);
        }

        int[] ans = new int[n];
        if(n == 1){
            ans[0] = 1;
        } else {
            int t = 0;
            for(int x: f((n+1)/2)){
                ans[t++] = 2*x-1;
            } 
            for(int x:f(n/2)){
                ans[t++] = 2*x;
            }
        }
        memo.put(n, ans);
        return ans;
    }
}