Open azl397985856 opened 1 year ago
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)
}
}
问题分解为子问题,递归解决,注意需要分为奇数和偶数
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)
复杂度分析
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)
抄作业
# 将问题分解为子问题并进行递归求解。
# 具体来说,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)
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;
}
}
932. 漂亮数组
入选理由
暂无
题目地址
https://leetcode-cn.com/problems/beautiful-array/
前置知识
题目描述
对于每个 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