احصل على الحد الأقصى في حل Array Leetcode الذي تم إنشاؤه


مستوى الصعوبة سهل
مجموعة

المشكلة الحصول على الحد الأقصى في Generated 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

ولكن قبل الخوض أكثر في الحل. يجب أن نلقي نظرة على بعض الأمثلة.

احصل على الحد الأقصى في حل Array Leetcode الذي تم إنشاؤه

n = 7
3

شرح: وفقًا للقواعد المحددة:
الأعداد [0] = 0 ، الأعداد [1] = 1
الأعداد [(1 * 2) = 2] = الأعداد [1] = 1
الأعداد [(1 * 2) + 1 = 3] = الأعداد [1] + الأعداد [2] = 1 + 1 = 2
الأعداد [(2 * 2) = 4] = الأعداد [2] = 1
الأعداد [(2 * 2) + 1 = 5] = الأعداد [2] + الأعداد [3] = 1 + 2 = 3
الأعداد [(3 * 2) = 6] = الأعداد [3] = 2
الأعداد [(3 * 2) + 1 = 7] = الأعداد [3] + الأعداد [4] = 2 + 1 = 3

لذلك يمكننا أن نرى الأعداد = [0,1,1,2,1,3,2,3،3،3،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX] ، والحد الأقصى هو XNUMX بينها. إذن الجواب هو XNUMX.

نهج للحصول على الحد الأقصى في حل Leetcode المصفوفة المولدة

مشكلة Get Maximum in Generated Array Leetcode Solution لها بعض القيود التي يجب تلبيتها. في ظل القيود المحددة ، نحن مطالبون بإيجاد الحد الأقصى لعدد صحيح. تم بالفعل شرح قواعد إنشاء المصفوفة في وصف المشكلة. الطريقة الأولى التي تتبادر إلى الذهن هي إنشاء المصفوفة وإيجاد العنصر الأقصى. لكن هل سيحل ذلك المشكلة؟

إذا مضينا قدماً مع الجيل ، فلن نتمكن من العثور على النتائج الصحيحة. لأنه يعتمد على كيفية إنشاء المصفوفة. إذا قمنا بتوليد عناصر عند 2ith و (2i + 1) مؤشر عندما نكون في الفهرس ith. في تلك اللحظة ، لن يكون لدينا القيمة المولدة للفهرس (i + 1). في هذه الحالة ، لن تكون النتيجة دقيقة.

لحل المشكلة ، سوف نتعامل مع الصيغ لتوليد العنصر. إذا استبدلنا i بـ i-1 ، في القاعدة الثالثة. نجد أن arr [3 * i-2] = arr [i] + arr [i-1]. لذا ، يمكننا الآن استخدام قواعد إنشاء المصفوفات. لأن هذه القاعدة تستخدم قيمة القيمة التي تم إنشاؤها بالفعل. لذلك ، بدلاً من استخدام أي قيم مستقبلية غير معروفة ، نستخدم القيم المحسوبة مسبقًا. لذلك نحن الآن ببساطة نحاكي العملية برمتها باستخدام حلقة for ونتحقق مما إذا كان 1 * i و 2 * i-2 في حدود المصفوفة. بمجرد تأكيد ذلك ، نستخدم الصيغ لملء المصفوفة.

رمز

كود C ++ للحصول على أقصى حد في Array Array Leetcode Solution

#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 للحصول على الحد الأقصى في حل Array 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) لأننا أنشأنا مصفوفة مؤقتة لتخزين قيم المصفوفة.