Ստացեք առավելագույնը գեներացված զանգվածի Leetcode լուծման մեջ


Դժվարության մակարդակ Հեշտ
Դասավորություն

Գեներացվող զանգվածում Leetcode Solution- ում Get Maximum- ի խնդիրը մեզ տրամադրեց մեկ ամբողջ թիվ: Տրված սինգլով ամբողջ թիվ, մենք պետք է գտնենք գեներացված զանգվածում առավելագույն ամբողջ թիվը: Rayանգվածի սերունդը որոշ կանոններ ունի: Սահմանված սահմանափակումների ներքո մենք պետք է գտնենք առավելագույն ամբողջ թիվը, որը կարող էր գեներացվել: Կանոններն են.

  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 Solution- ում Get Maximum- ի խնդիրն ունի որոշ սահմանափակումներ, որոնք պետք է բավարարվեն: Տրված սահմանափակումների ներքո մեզանից պահանջվում է գտնել առավելագույն ամբողջ թիվը: Rayանգվածի առաջացման կանոններն արդեն բացատրվել են խնդրի նկարագրության մեջ: Առաջին մեթոդը, որը գալիս է մտքում, զանգվածի առաջացումն է և առավելագույն տարրը գտնելը: Բայց արդյո՞ք դա կլուծի խնդիրը:

Եթե ​​մենք պարզապես առաջ գնանք սերնդի հետ, մենք չենք կարողանա ճիշտ արդյունքներ գտնել: Քանի որ դա կախված է նրանից, թե ինչպես ենք առաջացնում զանգվածը: Եթե ​​մենք ստեղծում ենք տարրեր 2th և (2i + 1) ինդեքսում, երբ գտնվում ենք ith ինդեքսի վրա: Այդ պահին մենք չէինք ունենա (i + 1) ինդեքսի համար գեներացված արժեք: Այդ դեպքում արդյունքը ճշգրիտ չի լինի:

Խնդիրը լուծելու համար մենք շահարկելու ենք տարրերի առաջացման բանաձեւերը: Եթե ​​i- ը փոխարինենք i-1- ով, 3-րդ կանոնում: մենք գտնում ենք, որ arr [2 * i-1] = arr [i] + arr [i-1]: Այսպիսով, այժմ մենք կարող ենք օգտագործել զանգվածների առաջացման կանոնները: Քանի որ այս կանոնն օգտագործում է արդեն գեներացված արժեքի արժեքը: Այսպիսով, այստեղ ապագա ցանկացած անհայտ արժեքներ օգտագործելու փոխարեն մենք օգտագործում ենք նախապես հաշվարկված արժեքները: Այսպիսով, հիմա մենք պարզապես նմանեցնում ենք ամբողջ գործընթացը, օգտագործելով for հանգույց և ստուգում, արդյոք 2 * i և 2 * i-1 զանգվածների սահմաններում են: Երբ դա հաստատվի, մենք օգտագործում ենք բանաձևերը զանգվածը լրացնելու համար:

Կոդ

C ++ կոդ գեներացված զանգվածի Leetcode լուծման մեջ առավելագույնը ստանալու համար

#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

Java- ի կոդը ստացված առավելագույնը գեներացված զանգվածի Leetcode լուծման համար

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

Բարդության վերլուծություն

Timeամանակի բարդություն

ՎՐԱ), քանի որ մենք առաջացնում ենք բոլոր n տարրերը:

Տիեզերական բարդություն

ՎՐԱ), քանի որ մենք ստեղծեցինք ժամանակավոր զանգված զանգվածի արժեքները պահելու համար: