მიიღეთ მაქსიმალური მასივის გამომუშავებული Leetcode გამოსავალი


Რთული ტური Easy
Array

პრობლემა მიიღე მაქსიმალური გენერირებული მასივის Leetcode Solution- ში მოგვცა ერთი მთელი რიცხვი. მოცემული სინგლით მთელი რიცხვი, გენერირებულ მასივში უნდა ვიპოვოთ მაქსიმალური მთელი რიცხვი. მასივის თაობას აქვს გარკვეული წესები. დაწესებული შეზღუდვების მიხედვით, ჩვენ უნდა ვიპოვოთ მაქსიმალური მთელი რიცხვი, რომლის გამომუშავებაც შეიძლებოდა. წესები:

  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– ს აქვს გარკვეული შეზღუდვები, რომლებიც უნდა დაკმაყოფილდეს. მოცემული შეზღუდვების მიხედვით, ჩვენ მოვთხოვთ ვიპოვოთ მაქსიმალური მთელი რიცხვი. მასივის წარმოქმნის წესები უკვე განმარტებულია პრობლემის აღწერაში. პირველი მეთოდი, რომელიც მახსენდება, მასივის წარმოქმნა და მაქსიმალური ელემენტის პოვნაა. მოაგვარებს ეს პრობლემას?

თუ ჩვენ უბრალოდ თაობას გავაგრძელებთ, ვერ შევძლებთ სწორი შედეგების პოვნას. რადგან ეს დამოკიდებულია იმაზე, თუ როგორ გამოვიქმნით მასივს. თუ ჩვენ ვაწარმოებთ ელემენტებს 2th და (2i + 1) ინდექსზე, როდესაც ith ინდექსში ვართ. იმ მომენტში, ჩვენ არ გვექნებოდა გენერირებული მნიშვნელობა (i + 1) ინდექსისთვის. ამ შემთხვევაში, შედეგი არ იქნება ზუსტი.

პრობლემის გადასაჭრელად, ჩვენ მანიპულირებთ ელემენტების წარმოქმნის ფორმულებით. თუ მე 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

ჯავის კოდი მაქსიმალური მისაღებად მასივის წარმოქმნილი 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

სირთულის ანალიზი

დროის სირთულე

O (N), რადგან ჩვენ წარმოქმნის ყველა n ელემენტს.

სივრცის სირთულე

O (N), რადგან შევქმენით დროებითი მასივი მასივის მნიშვნელობების შესანახად.