උපසිරැසිය කන්දක ස්වරූපයෙන් තිබේද නැද්ද යන්න සොයා බලන්න


දුෂ්කරතා මට්ටම Hard
නිතර අසනු ලැබේ ඇමේසන් කළු ගල් සිස්කෝ Citrix ෆැක්ට්සෙට් හනිවෙල් ටෙස්ලා Yandex
අරා විමසුම් ගැටළුව

ගැටළු ප්රකාශය

“උපසිරැසිය කන්දක ස්වරූපයෙන් තිබේද නැද්ද යන්න සොයා බලන්න” යන ගැටලුවේ සඳහන් වන්නේ ඔබට ලබා දී ඇති බවයි නිඛිල අරාව සහ පරාසයක්. ලබා දී ඇති පරාසය අතර පිහිටුවා ඇති උප අරාව කඳුකර ස්වරූපයෙන් තිබේද නැද්ද යන්න සොයා බැලීමට ගැටළු ප්‍රකාශය අසයි. සංඛ්‍යා වැඩි වන්නේ අනුපිළිවෙලින් හෝ අඩු වන අනුපිළිවෙලින් නම් හෝ පළමුව වැඩි වන විට අඩු වුවහොත් කඳුකර අරාව සෑදී ඇත.

උදාහරණයක්

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

Left, right = (0, 3)
Mountain Form

පැහැදිලි කිරීම

Ar 3, 4, 5, 6 sub යන උප අරාව වැඩි වන නිසා එය කඳුකරයේ ස්වරූපයෙන් පවතී.

උපසිරැසිය කන්දක ස්වරූපයෙන් තිබේද නැද්ද යන්න සොයා බලන්න

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

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

පැහැදිලි කිරීම

Ar 5, 1, 2 sub යන උප අරාව අඩු වන නිසා වැඩි වේ. එබැවින් එය කඳුකරයේ ස්වරූපයෙන් නොවේ.

ඇල්ගොරිතම

  1. අරා දෙකක් සාදන්න arrayL සහ arrayR මුල් අරාවේ දිගට සමාන ප්‍රමාණයෙන්.
  2. අරාවෙහි පළමු අංගය සහ අරාවර් හි අවසාන අංගය ආරම්භ කරන්න.
  3. වත්මන් අරාව මූලද්‍රව්‍යය පෙර මූලද්‍රව්‍යයට වඩා වැඩි නම්.
    1. යාවත්කාලීන කරන්න වැඩිවන අංකය දර්ශකයට.
    2. අගය වැඩි කිරීමේ අගය අරාව වෙත පවරන්න.
  4. අරාව දකුණේ සිට වමට ගමන් කර පෙර මූලද්‍රව්‍යයට වඩා විශාල සංඛ්‍යාවක් තිබේදැයි පරීක්ෂා කරන්න (වත්මන් මූලද්‍රව්‍යයේ දකුණට ඇති මූලද්‍රව්‍යය).
    1. ඉන්පසු යාවත්කාලීන කරන්න අඩුවීම දර්ශකයට
    2. අඩු වන අංකයට අරාව ලබා දෙන්න.
  5. ලබා දී ඇති සෑම විමසුමකටම, අරාව ආර් [වමේ] අරාව එල් [දකුණට] වඩා සත්‍ය වේ, නැතිනම් අසත්‍යය ආපසු එවන්න.

පැහැදිලි කිරීම

අපි පූර්ණ සංඛ්‍යා අරාවක් සහ පරාසයක් වමට, දකුණට ලබා දී ඇත. ලබා දී ඇති පරාසය සමඟ සාදන ලද උපසිරැසිය කඳුකර පෙළක් විය හැකිද නැද්ද යන්න සොයා බැලීමට අපි ඉල්ලා සිටිමු. එසේ පිහිටුවා ඇති උපසිරැසිය කඳුකර අරාව නම් අපි සත්‍යය වෙත ආපසු යන්නෙමු. අපි අරා දෙකක් ප්‍රකාශ කරන්නෙමු. එකක් අරාවෙහි වම් පැත්තට වන අතර අනෙක අරාවෙහි දකුණු පැත්තට ය. සෑම විමසුමකටම නියත අවකාශයේ විසඳුමක් ලබා දිය හැකි වන පරිදි අපි මෙම අරා සාදන්නෙමු.

අපි පිළිවෙලින් අරේල් සහ අරා ආර් නිර්මාණය කළ අරාවේ පළමු හා අවසාන අංගය ආරම්භ කරමු. එවිට අපි අරාවෙහි වම් පැත්තට අරාව හරහා ගමන් කරමු, නැතහොත් අපට වමේ සිට දකුණට පැවසිය හැකිය. වත්මන් අරාව මූලද්‍රව්‍යය පෙර මූලද්‍රව්‍යයට වඩා අඩු නම් අපි තත්වය පරීක්ෂා කරන්නෙමු. එය සත්‍ය බව සොයාගත හොත්, අපි වැඩිවන සංඛ්‍යාව අංකයේ දර්ශකයට යාවත්කාලීන කරන්නෙමු. තත්වය සත්‍යයක්ද නැද්ද යන්න නොසලකා සෑම විටම අරේල් හි වත්මන් මූලද්‍රව්‍යය වැඩිවන සංඛ්‍යාවට ලබා දෙන්න.

මීලඟ පියවරේදී අපි අරාව දකුණේ සිට වමට, මූලික වශයෙන් දෙවන අන්තිම මූලද්‍රව්‍යයේ සිට අරාවේ පළමු මූලද්‍රව්‍යය දක්වා ගමන් කරන අතර අරාවෙහි වත්මන් මූලද්‍රව්‍යය ඊළඟ මූලද්‍රව්‍යයට වඩා වැඩි දැයි පරීක්ෂා කරමු. අපි දකුණේ සිට වමට ගමන් කරන බැවින්, අපට පෙර අංගය සමඟ පරීක්ෂා කරන්න. තත්වය නිවැරදි හෝ සත්‍ය නම්, අඩු වන සංඛ්‍යා අගය වත්මන් දර්ශකයට වෙනස් වේ. කොන්දේසි නොසලකා අඩු වන අංකයට අරාව යාවත්කාලීන කරන්න. සත්‍යය වෙත ආපසු යන්න, අරාව [වමේ] අරාව [දකුණට] වඩා විශාල හෝ සමාන නම්, එසේ නොමැතිනම් අසත්‍යය ආපසු එවන්න.

කේතය

උප රේඛාවක් කන්දක ස්වරූපයෙන් තිබේද නැද්ද යන්න සොයා ගැනීමට 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

සංකීර්ණ විශ්ලේෂණය

කාල සංකීර්ණත්වය

O (N + Q), අරා දෙකම සෑදීම සඳහා අපට O (N) කාලය අවශ්‍ය වේ. අරා ඉදි කළ පසු. O (1) හි විමසුම් වලට අපට පිළිතුරු දිය හැකිය.

අභ්‍යවකාශ සංකීර්ණතාව

සාමාන්ය (n) එහිදී “N” යනු අරාවෙහි ඇති මූලද්‍රව්‍ය ගණන වේ.