Yaratılmış Array Leetcode Solution-da maksimum nəticə əldə edin

Generated Array Leetcode Solution-da Maksimum Al problemi bizə bir tam ədədi təqdim etdi. Verilən tək ilə tam, yaradılan massivdə maksimum tam ədədi tapmaq lazımdır. Dizinin yaranma qaydaları var. Tətbiq olunan məhdudiyyətlər altında, yarana biləcək maksimum tam ədədi tapmaq lazımdır. Qaydalar bunlardır:

arr [0] = 0, arr [1] = 1
arr [2 * i] = arr [i] burada 2 <= 2 * i <= n
və arr [2 * i + 1] = arr [i] + arr [i + 1] burada 2 <= 2 * i + 1 <= n

Ancaq həll yoluna daha da dalmadan əvvəl. Bir neçə nümunəyə nəzər salmalıyıq.

n = 7

İzahat: Verilən qaydalara əsasən:
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

Beləliklə, nums = [0,1,1,2,1,3,2,3] görə bilərik və bunların arasında maksimum 3-dir. Beləliklə cavab 3-dür.

Mündəricat

Yaradılan Array Leetcode həllində maksimum əldə etmə yanaşması

Generated Array Leetcode Solution-da Maksimum Al problemi təmin edilməli olan bəzi məhdudiyyətlərə malikdir. Verilən məhdudiyyətlər altında, maksimum tam ədədi tapmağımız tələb olunur. Dizinin yaranma qaydaları problemin təsvirində artıq izah edilmişdir. Ağla gələn ilk metod, serialın yaradılması və maksimum elementin tapılmasıdır. Bəs bu problemi həll edəcəkmi?

Sadəcə nəsil ilə irəliləsək, düzgün nəticələr tapa bilməyəcəyik. Çünki bu, serialı necə yaratdığımızdan asılıdır. İth indeksində olduğumuz zaman 2ith və (2i + 1) indeksində elementlər yaratsaq. O anda, (i + 1) -ci indeks üçün yaradılan dəyərimiz olmazdı. Bu vəziyyətdə nəticə dəqiq olmayacaq.

Problemi həll etmək üçün element yaratma formullarını idarə edəcəyik. İ-i i-1 ilə əvəz etsək, 3-cü qayda. arr [2 * i-1] = arr [i] + arr [i-1] olduğunu tapırıq. Beləliklə, indi sıra yaratmaq üçün qaydaları istifadə edə bilərik. Çünki bu qayda onsuz da yaradılan dəyərin dəyərindən istifadə edir. Beləliklə, gələcəkdə bilinməyən dəyərləri istifadə etmək əvəzinə əvvəlcədən hesablanmış dəyərlərdən istifadə edirik. Beləliklə, indi for for loop istifadə edərək 2 * i və 2 * i-1 -nin hüdudlarında olub olmadığını yoxlamaqla sadəcə bütün prosesi simulyasiya edirik. Bu təsdiqləndikdən sonra, massivi doldurmaq üçün formullardan istifadə edirik.

Kodu

Generated Array Leetcode Solution-da Maksimum Alın üçün C ++ kodu

#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);
}

Generated Array Leetcode Solution-da Maksimum Alın üçün Java kodu

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));
    }
}

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (N), çünki bütün n elementləri yaradırıq.

Kosmik Mürəkkəblik

O (N), çünki sıra dəyərlərini saxlamaq üçün müvəqqəti bir sıra yaratdıq.

Yaratılmış Array Leetcode həllində maksimum alın