አንድ ንዑስ ቡድን በተራራ መልክ ይሁን አይሁን ይፈልጉ  


የችግር ደረጃ ጠንካራ
ውስጥ በተደጋጋሚ ተጠየቀ አማዞን ብላክ ሮክ Cisco Citrix ፋርስት Honeywell tesla Yandex
ሰልፍ የጥያቄ ችግር

የችግሩ መግለጫ  

ችግሩ “አንድ ንዑስ ቡድን በተራራ መልክ ይሁን አይሁን ፈልግ” የሚለው እንደተሰጠ ነው ኢንቲጀር ደርድር እና አንድ ክልል. በተሰጠው ክልል መካከል የተገነባው ንዑስ ድርድር በተራራ መልክ መሆኑን ወይም አለመሆኑን ለማወቅ የችግሩ መግለጫ ይጠይቃል? ቁጥሩ በቅደም ተከተል ወይም በቅደም ተከተል እየቀነሰ ወይም መጀመሪያ እየጨመረ ከዚያ እየቀነሰ ከሆነ የተራራ ድርድር ይፈጠራል።

ለምሳሌ  

arr[]={3,4,5,6,1,5,1,2,1}

Left, right = (0, 3)
Mountain Form

ማስረጃ

ምክንያቱም ንዑስ ድርድሩ {3, 4, 5, 6} እየጨመረ ስለሆነ በተራራማው ድርድር መልክ ነው።

አንድ ንዑስ ቡድን በተራራ መልክ ይሁን አይሁን ይፈልጉጭንቅላታም መያያዣ መርፌ

arr[]={3,4,5,6,1,5,1,2,1}

Left, right = (5, 7)
Not a Mountain form

ማስረጃ

ምክንያቱም ንዑስ ድርድር {5, 1, 2} እየቀነሰ ከዚያ እየጨመረ ነው። ስለዚህ በተራራ ድርድር መልክ አይደለም።

አልጎሪዝም  

  1. ሁለት ድርድሮችን ይፍጠሩ ድርድር ኤልድርድር አር ከመጀመሪያው ድርድር ርዝመት ጋር ተመሳሳይ መጠን ያለው።
  2. የድርድር ኤል የመጀመሪያ አካል እና የድርድር አር የመጨረሻ አካል።
  3. የአሁኑ የድርድር አካል ከቀዳሚው ንጥረ ነገር የበለጠ ከሆነ።
    1. አዘምን ቁጥር መጨመር ወደ ማውጫ.
    2. የቁጥር መጨመር ቁጥርን ለድርድሩ ኤል ይመድቡ።
  4. ድርደራውን ከቀኝ ወደ ግራ በማለፍ ከቀዳሚው ንጥረ ነገር የሚበልጥ ቁጥር (ከአሁኑ ንጥረ ነገር በስተቀኝ ያለው ኤለመንት) ያረጋግጡ።
    1. ከዚያ, አዘምን ቁጥር መቀነስ ወደ ማውጫ
    2. የድርጅቱን አር ቁጥር እየቀነሰ ይመድቡ።
  5. ለእያንዳንዱ ጥያቄ ፣ ድርድር አር [ግራ] ከድርድር ይበልጣል [ከቀኝ] እውነት ይመለሳል ፣ ካልሆነም ሐሰት ይመለስ።
ተመልከት
ከ M ክልል መቀያየር ክወናዎች በኋላ የሁለትዮሽ ድርድር

ማስረጃ  

የኢቲጀር ድርድር እና ግራ ፣ ቀኝ ክልል ሰጥተናል ፡፡ ከተጠቀሰው ክልል ጋር የተገነባው ይህ ንዑስ ቡድን የተራራ ድርድር ሊሆን ይችላል ወይም አለመሆኑን ለማወቅ ጠይቀናል ፡፡ እንዲህ የተደረገው ንዑስ ቡድን የተራራ ድርድር ከሆነ እኛ ወደ እውነት እንመለሳለን ፣ አለበለዚያ ወደ ሐሰት እንመለሳለን። ሁለት ድርድሮችን እናውጃለን ፡፡ አንደኛው ለድርድሩ የግራ ጎን ሌላኛው ደግሞ ለድርድሩ የቀኝ ጎን ነው ፡፡ ከዚያ እያንዳንዱ ጥያቄ በቋሚ ቦታ ላይ መፍትሄ እንዲሰጥ እነዚህን ዝግጅቶች እንገነባለን ፡፡

ድርድር ኤል እና ድርድር አር እኛ የፈጠርነው የድርድር የመጀመሪያ እና የመጨረሻ አካል በቅደም ተከተል እንጀምራለን። ከዚያ ድርድሩን ለድርድሩ ግራ በኩል እናልፋለን ወይም ከግራ ወደ ቀኝ ማለት እንችላለን ፡፡ የአሁኑ የድርድር አካል ከቀዳሚው ንጥረ ነገር ያነሰ ከሆነ ሁኔታውን እንፈትሻለን። እውነት ሆኖ ከተገኘ ከዚያ እየጨመረ ያለውን ቁጥር ወደ ቁጥሩ መረጃ ጠቋሚ እናሳድሰዋለን ፡፡ እና ሁኔታውን በግዴለሽነት በሚመለከት ቁጥር እውነት ወይም ያልሆነ በሚሆንበት ጊዜ ሁሉ የድርጅት ኤል የአሁኑን ንጥረ ነገር ቁጥር እንዲጨምር ይመድቡ።

በሚቀጥለው ደረጃ ድርደራውን ከቀኝ ወደ ግራ በማለፍ በመሠረቱ ከሁለተኛው የመጨረሻ አካል እስከ መጀመሪያው ንጥረ-ነገር ድረስ እናልፋለን ፣ እና አሁን ያለው የድርጅት አካል ከቀጣዩ ንጥረ ነገር ይበልጣል የሚለውን እንፈትሻለን። ከቀኝ ወደ ግራ እየተጓዝን ስለሆንን ከቀደመው አካል ጋር ቼክ ማለት እንችላለን ፡፡ ሁኔታው ትክክል ወይም እውነት ከሆነ በመቀነስ የቁጥር እሴት ወደ የአሁኑ መረጃ ጠቋሚ ይቀየራል። ሁኔታዎቹ ምንም ቢሆኑም ቁጥሩ እየቀነሰ ለሚሄድ ድርድር ያዘምኑ ፡፡ ወደ እውነተኛው ይመለሱ ፣ ድርድሩ አር (ግራ) ከድርድሩ ኤል [ከቀኝ] የበለጠ ወይም እኩል ከሆነ ፣ ከዚያ ሐሰት ይመለስ።

ተመልከት
Palindrome የተገናኘ ዝርዝር Leetcode መፍትሔ

ኮድ  

አንድ ንዑስ ቡድን በተራራ መልክ ይሁን አይሁን ለማወቅ የ C ++ ኮድ

#include<iostream>

using namespace std;

void buildArrays(int arr[], int N, int arrayL[], int arrayR[])
{
    arrayL[0] = 0;
    int increasingNumber = 0;

    for (int i = 1; i < N; i++)
    {
        if (arr[i] > arr[i - 1])
            increasingNumber = i;
        arrayL[i] = increasingNumber;
    }
    arrayR[N - 1] = N - 1;
    int decreasingNumber = N - 1;

    for (int i = N - 2; i >= 0; i--)
    {
        if (arr[i] > arr[i + 1])
            decreasingNumber = i;
        arrayR[i] = decreasingNumber;
    }
}

bool solveQuery(int arr[], int arrayL[], int arrayR[], int Left, int Right)
{
    return (arrayR[Left] >= arrayL[Right]);
}

int main()
{
    int arr[] = {3,4,5,6,1,5,1,2,1};
    int N = sizeof(arr) / sizeof(int);

    int arrayL[N], arrayR[N];
    buildArrays(arr, N, arrayL, arrayR);

    int L = 0;
    int R = 3;
    if (solveQuery(arr, arrayL, arrayR, L, R))
        cout << "Mountain form\n";
    else
        cout << "Not a mountain form\n";

    L = 5;
    R = 7;
    if (solveQuery(arr, arrayL, arrayR, L, R))
        cout << "Mountain form\n";
    else
        cout << "Not a mountain form\n";

    return 0;
}
Mountain form
Not a mountain form

የጃቫ ኮድ አንድ ንዑስ ክፍል በተራራ መልክ ይሁን አይሁን ለማወቅ

class MountainArray
{
    static void buildArrays(int arr[], int N, int arrayL[], int arrayR[])
    {
        arrayL[0] = 0;
        int increasingNumber = 0;

        for (int i = 1; i < N; i++)
        {
            if (arr[i] > arr[i - 1])
                increasingNumber = i;
            arrayL[i] = increasingNumber;
        }
        arrayR[N - 1] = N - 1;
        int decreasingNumber = N - 1;

        for (int i = N - 2; i >= 0; i--)
        {
            if (arr[i] > arr[i + 1])
                decreasingNumber = i;
            arrayR[i] = decreasingNumber;
        }
    }
    
    static boolean solveQuery(int arr[], int arrayL[], int arrayR[], int Left, int Right)
    {
        return (arrayR[Left] >= arrayL[Right]);
    }

    public static void main(String[] args)
    {
        int arr[] = {3,4,5,6,1,5,1,2,1};
        int N = arr.length;
        int arrayL[] = new int[N];
        int arrayR[] = new int[N];
        buildArrays(arr, N, arrayL, arrayR);
        int L = 0;
        int R = 3;

        if (solveQuery(arr, arrayL, arrayR, L, R))
            System.out.println("Mountain form");
        else
            System.out.println("Not a mountain form");

        L = 5;
        R = 7;

        if (solveQuery(arr, arrayL, arrayR, L, R))
            System.out.println("Mountain form");
        else
            System.out.println("Not a mountain form");
    }
}
Mountain form
Not a mountain form

ውስብስብነት ትንተና  

የጊዜ ውስብስብነት

ኦ (N + Q) ፣ ሁለቱንም ድርድር ለመገንባት O (N) ጊዜ እንፈልጋለን ፡፡ እና አንዴ ድርድሮች ከተገነቡ ፡፡ ጥያቄዎቹን በ O (1) ውስጥ መመለስ እንችላለን ፡፡

ተመልከት
ሚን ቁልል Leetcode መፍትሄ

የቦታ ውስብስብነት

ሆይ (n) የት “N” በድርድሩ ውስጥ ያሉት ንጥረ ነገሮች ብዛት ነው።