subarray သည်တောင်ပုံစံတစ်ခုဟုတ်မဟုတ်ရှာဖွေပါ


ခက်ခဲအဆင့် ခိုင်မာသော
မကြာခဏမေးတယ် အမေဇုံ BlackRock Cisco သည် Citrix အချက်အလက် Honeywell တက်စလာ Yandex
အခင်းအကျင်း ပြeryနာပြ.နာ

ပြProbleနာဖော်ပြချက်

“ subarray သည်တောင်ပုံစံတစ်မျိုးလားမရှာသည်” ပြproblemနာကသင့်အားပေးထားသည် ကိန်း အခင်းအကျင်း နှင့်အကွာအဝေး။ ပြstatementနာဖော်ပြချက်သည်ပေးထားသောအကွာအဝေးအကြားဖွဲ့စည်းထားသည့် sub-ခင်းကျင်းသည်တောင်ပုံစံနှင့်မဟုတ်ကိုရှာဖွေရန်တောင်းဆိုသည်။ နံပါတ်များသည်အစဉ်အဆက်တိုးပွားလာခြင်းသို့မဟုတ်အစဉ်လိုက်ကျဆင်းလာခြင်းသို့မဟုတ်ပထမ ဦး ဆုံးတိုးမြှင့်ခြင်းများတိုးပွားလာပါကတောင်တန်းများကိုဖွဲ့စည်းသည်။

နမူနာ

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

Left, right = (0, 3)
Mountain Form

ရှင်းလင်းချက်

အဘယ်ကြောင့်ဆိုသော် sub-array {3, 4, 5, 6} သည်တိုးများလာသဖြင့်၎င်းသည်တောင်တန်း၏ပုံစံဖြစ်သည်။

subarray သည်တောင်ပုံစံတစ်ခုဟုတ်မဟုတ်ရှာဖွေပါ

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

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

ရှင်းလင်းချက်

အဘယ်ကြောင့်ဆိုသော် sub ခင်းကျင်းခြင်း {5, 1, 2} သည်လျော့ကျလာခြင်းနှင့်တိုးပွားလာခြင်းကြောင့်ဖြစ်သည်။ ထို့ကြောင့်၎င်းသည်တောင်တန်းပုံစံမဟုတ်ပါ။

algorithm

  1. Array နှစ်ခုဖန်တီးပါ arrayL နှင့် arrayR မူရင်းခင်းကျင်း၏အရှည်နှင့်အတူတူပင်အရွယ်အစား၏။
  2. arrayL ၏ပထမဆုံး element နှင့် arrayR ၏နောက်ဆုံး element ကိုအစပြုပါ။
  3. လက်ရှိခင်းကျင်း element ကယခင်ဒြပ်စင်ထက်သာ။ ကြီးမြတ်လျှင်။
    1. မွမ်းမံပါ တိုးပွားလာခြင်း အညွှန်းကိန်းရန်။
    2. valuesNumber ကို arrayL သို့သတ်မှတ်ပါ။
  4. Array ကိုညာဘက်ဘယ်ဘက်သို့ဖြတ်ပြီးအရင် element ထက်ပိုကြီးလားဆိုတာစစ်ဆေးပါ (element ကလက်ရှိ element ၏ညာဘက်သို့) ။
    1. ပြီးရင် update လုပ်ပါ decreasingNumber အညွှန်းကိန်းရန်
    2. decreRnumber သို့ arrayR ကိုသတ်မှတ်ပါ။
  5. ပေးထားသောစုံစမ်းမှုတိုင်းအတွက် arrayR [left] သည် arrayL ထက်ပိုကြီးသည် (true) return true, သို့မဟုတ် false သို့ပြန်သွားပါ။

ရှင်းလင်းချက်

ကျွန်တော်တို့က integer array နဲ့ range ကို left, right ပေးထားတယ်။ ပေးထားသောအကွာအဝေးနှင့်အတူဒါဖွဲ့စည်းခဲ့ subarray တောင်ခင်းကျင်းဖြစ်နိုင်ပါတယ်သို့မဟုတ်မရှိမရှိထွက်ရှာရန်ကျနော်တို့မေးတယ်။ ဤကဲ့သို့ဖွဲ့စည်းလိုက်သော subarray သည်တောင်တန်းကြီးဖြစ်ပါကကျွန်ုပ်တို့သည် true သို့ပြန်သွားပါမည်။ ကျနော်တို့ Array ကိုနှစ်ခုကြေညာပါလိမ့်မယ်။ တစ်ခုက array ရဲ့ဘယ်ဘက်ခြမ်းနဲ့နောက်တစ်ခုက array ရဲ့ညာဘက်အခြမ်းအတွက်ပါ။ ထိုအခါကျွန်ုပ်တို့သည်ဤ Array များကိုတည်ဆောက်လိမ့်မည်၊ သို့မှသာ query တစ်ခုချင်းစီသည်အမြဲတမ်းနေရာ၌အဖြေတစ်ခုပေးနိုင်သည်။

ကျွန်ုပ်တို့သည် arrayL နှင့် arrayR ကိုအသီးသီးဖန်တီးခဲ့သောပထမနှင့်နောက်ဆုံး element ကိုစတင်ပါမည်။ ထိုအခါကျွန်ုပ်တို့သည် array ၏ဘယ်ဘက်ခြမ်းအတွက်ခင်းကျင်းဖြတ်သန်းသွားသည်သို့မဟုတ်လက်ဝဲမှညာသို့ပြောနိုင်သည်။ လက်ရှိ array element သည်ယခင်ဒြပ်စင်ထက်နည်းလျှင်ကျွန်ုပ်တို့သည်အခြေအနေကိုစစ်ဆေးပါမည်။ ၎င်းသည်မှန်ကန်ကြောင်းတွေ့ရှိပါကကျွန်ုပ်တို့သည်နံပါတ်၏အညွှန်းကိုတိုးမြှင့်ထားသောNumberကို update လုပ်ပါမည်။ ပြီးတော့ arrayL ရဲ့လက်ရှိ element ကို IncreaseNumber မှာမသက်ဆိုင်ဘဲအခြေအနေမှန်သမျှတိုင်းသတ်မှတ်ပေးပါ။

နောက်တဆင့်တွင်အခြေခံအားဖြင့်ဒုတိယနောက်ဆုံး element မှ array ၏ပထမ element သို့အခြေခံအားဖြင့်လက်ဝဲဘက်သို့ဘယ်ဘက်မှဖြတ်သန်းသွားမည်ဖြစ်ပြီး၊ array ၏လက်ရှိ element သည်လာမည့် element ထက်ပိုမိုကြီးလားဆိုတာကိုစစ်ဆေးလိမ့်မည်။ ကျနော်တို့ညာဘက်မှဘယ်ဘက်ဖြတ်သန်းနေကြသည်ကတည်းကကျနော်တို့ယခင်ဒြပ်စင်နှင့်အတူစစ်ဆေးလို့ရပါတယ်။ အကယ်၍ အခြေအနေမှန်ကန်ပါက၊ true ဖြစ်လျှင်၊ decreasingNumber တန်ဖိုးကိုလက်ရှိအညွှန်းသို့ပြောင်းလိုက်သည်။ အခြေအနေများမည်သို့ပင်ဖြစ်စေ၊ decreasingNumber သို့ array ကို update လုပ်ပါ။ အကယ်၍ arrayR [left] သည် arrayL [ထက်ကြီးသည်] သို့မဟုတ်ညီမျှလျှင်၊ true သို့ပြန်သွားလျှင် false ကိုပြန်သွားပါ။

ကုဒ်

subarray သည်တောင်ပုံစံရှိမရှိရှာရန် 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

subarray သည်တောင်ပုံစံရှိမရှိရှာရန် Java ကုဒ်ဖြစ်သည်

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)၊ Array ကိုတည်ဆောက်ရန် O (N) အချိန်လိုအပ်သည်။ ထိုအခါတစ်ချိန်က Array ကိုတည်ဆောက်နေကြသည်။ O (1) ရှိမေးခွန်းများကိုဖြေဆိုနိုင်ပါသည်။

အာကာသရှုပ်ထွေးမှု

အို (ဎ) ဘယ်မှာ “ n” သည် array အတွင်းရှိ element အရေအတွက်ဖြစ်သည်။