በተፈጠረው የድርድር 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

ማብራሪያ-በተሰጠው ሕግ መሠረት-
ቁጥሮች [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 ነው ፡፡

በተፈጠረው የድርድር Leetcode መፍትሔ ውስጥ ከፍተኛውን ለማግኘት የሚደረግ አቀራረብ

ችግሩ በተፈጠረው ድርድር ሌቲኮድ መፍትሄ ውስጥ ከፍተኛውን ያግኙ (መሟላት) ያለባቸው አንዳንድ ገደቦች አሉት። በተሰጡት ገደቦች ውስጥ ከፍተኛውን ቁጥር (ኢንቲጀር) መፈለግ ይጠበቅብናል ፡፡ ለድርድር ትውልድ ሕጎች ቀድሞውኑ በችግሩ ገለፃ ላይ ተብራርተዋል ፡፡ ወደ አእምሮ የሚመጣው የመጀመሪያው ዘዴ የድርድር እና ከፍተኛውን ንጥረ ነገር መፈለግ ነው ፡፡ ግን ያ ችግሩን ይፈታልን?

እኛ በቀላሉ ትውልዱን ከቀጠልን ትክክለኛ ውጤቶችን ማግኘት አንችልም ፡፡ ምክንያቱም እሱ ድርድርን በምንፈጥርበት ሁኔታ ላይ የተመሠረተ ነው። ንጥረ ነገሮችን በ 2 ኛ እና (2i + 1) መረጃ ጠቋሚ በምናደርግበት ጊዜ የምንፈጥር ከሆነ ፡፡ በዚያን ጊዜ ለ (i + 1) ኛ መረጃ ጠቋሚ የተፈጠረው እሴት አይኖረንም። ያኔ ውጤቱ ትክክለኛ አይሆንም ፡፡

ችግሩን ለመፍታት ለኤለመንት ትውልድ ቀመሮቹን እንጠቀምባቸዋለን ፡፡ I ን በ i-1 ከቀየርን በ 3 ኛው ደንብ ውስጥ ፡፡ እኛ arr [2 * i-1] = arr [i] + arr [i-1] እናገኛለን። ስለዚህ አሁን ደንቦችን ለድርድር ትውልድ ልንጠቀምባቸው እንችላለን ፡፡ ምክንያቱም ይህ ደንብ ቀድሞውኑ የተፈጠረውን እሴት ዋጋ ይጠቀማል። ስለዚህ እዚህ ማንኛውንም የወደፊት ያልታወቁ እሴቶችን ከመጠቀም ይልቅ ቀድሞ የተሰላውን እሴቶች እንጠቀማለን ፡፡ ስለዚህ አሁን እኛ አጠቃላይ ሂደቱን በቃለ-መጠይቅ በመጠቀም እና 2 * i እና 2 * i-1 በድርድሩ ወሰን ውስጥ መሆናቸውን እናረጋግጣለን ፡፡ ይህ ከተረጋገጠ በኋላ አሰራሩን ለመሙላት ቀመሮቹን እንጠቀማለን ፡፡

ኮድ

በተፈጠረው ድርድር ሌቲኮድ መፍትሄ ውስጥ ከፍተኛውን ለማግኘት የ 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

በተፈጠረው ድርድር ሌቲኮድ መፍትሔ ውስጥ ከፍተኛውን ለማግኘት የጃቫ ኮድ

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

ውስብስብነት ትንተና

የጊዜ ውስብስብነት

ኦ (ኤን) ፣ ምክንያቱም እኛ ሁሉንም ንጥረ ነገሮች እናመነጫለን።

የቦታ ውስብስብነት

ኦ (ኤን) ፣ ምክንያቱም የድርድር እሴቶችን ለማከማቸት ጊዜያዊ ድርድር ፈጥረናል።