在生成的阵列Leetcode解决方案中获得最大收益


难度级别 易得奖学金
排列

问题“在生成的阵列Leetcode解决方案中获取最大”为我们提供了一个整数。 与给定的单 整数,我们需要在生成的数组中找到最大整数。 数组生成有一些规则。 在强加的约束下,我们需要找到可能已生成的最大整数。 规则是:

  1. arr [0] = 0,arr [1] = 1
  2. arr [2 * i] = arr [i]其中2 <= 2 * i <= n
  3. 和arr [2 * i + 1] = arr [i] + arr [i + 1]其中2 <= 2 * i + 1 <= n

但是在深入探讨解决方案之前。 我们应该看几个例子。

在生成的阵列Leetcode解决方案中获得最大收益

n = 7
3

说明:根据给定的规则:
nums [0] = 0,nums [1] = 1
nums [(1 * 2)= 2] = nums [1] = 1
nums [(1 * 2)+1 = 3] = nums [1] + nums [2] = 1 +1 = 2
nums [(2 * 2)= 4] = nums [2] = 1
nums [(2 * 2)+1 = 5] = nums [2] + nums [3] = 1 +2 = 3
nums [(3 * 2)= 6] = nums [3] = 2
nums [(3 * 2)+1 = 7] = nums [3] + nums [4] = 2 +1 = 3

因此,我们可以看到nums = [0,1,1,2,1,3,2,3],其中最大为3。 因此答案是3。

在生成的阵列Leetcode解决方案中获取最大值的方法

问题“在生成的阵列Leetcode解决方案中获取最大”有一些必须满足的约束。 在给定的约束下,我们需要找到最大整数。 问题的描述中已经解释了数组生成的规则。 我想到的第一个方法是生成数组并找到最大元素。 但这能解决问题吗?

如果我们只是继续前进,我们将无法找到正确的结果。 因为这取决于我们如何生成数组。 如果我们在第ith个索引处生成元素在2th和(2i + 1)索引处。 那时候,我们将没有第(i + 1)个索引的生成值。 在这种情况下,结果将不准确。

为了解决该问题,我们将操纵用于生成元素的公式。 如果我们将i替换为i-1,则在第三条规则中。 我们发现arr [3 * i-2] = arr [i] + arr [i-1]。 因此,现在我们可以使用规则生成数组了。 因为此规则使用已经生成的值的值。 因此,此处使用的是预先计算的值,而不是使用任何将来的未知值。 因此,现在我们简单地使用for循环模拟整个过程,并检查1 * i和2 * i-2是否在数组的边界内。 确认后,我们将使用公式来填充数组。

代码

用于在生成的阵列Leetcode解决方案中获取最大值的C ++代码

#include <bits/stdc++.h>
using namespace std;

int getMaximumGenerated(int n) {
    if(n == 0)return 0;
    if(n == 1)return 1;
    vector<int> tmp(n+1);
    tmp[0] = 0;
    tmp[1] = 1;
    for(int i=1;i<=n;i++){
        if(2*i<=n)
            tmp[2*i] = tmp[i];
        if(2*i-1<=n)
            tmp[2*i-1] = tmp[i] + tmp[i-1];
    }
    int ans = 0;
    for(int i=0;i<=n;i++)
        ans = max(tmp[i], ans);
    return ans;
}

int main(){
    cout<<getMaximumGenerated(7);
}
3

在生成的阵列Leetcode解决方案中获取最大数量的Java代码

import java.util.*;
import java.io.*;

class Main {

    public static int getMaximumGenerated(int n) {
        if(n == 0)return 0;
        if(n == 1)return 1;
        int[] tmp = new int[n+1];
        tmp[0] = 0;
        tmp[1] = 1;
        for(int i=1;i<=n;i++){
            if(2*i<=n)
                tmp[2*i] = tmp[i];
            if(2*i-1<=n)
                tmp[2*i-1] = tmp[i] + tmp[i-1];
        }
        int ans = 0;
        for(int i=0;i<=n;i++)
            ans = Math.max(tmp[i], ans);
        return ans;
    }

    public static void main(String[] args){
        System.out.println(getMaximumGenerated(7));
    }
}
3

复杂度分析

时间复杂度

上), 因为我们生成了所有n个元素。

空间复杂度

上), 因为我们创建了一个临时数组来存储数组值。