ببینید آیا یک زیر مجموعه به شکل کوه است یا نه


سطح دشواری سخت
اغلب در آمازون بلک راک سیسکو خودتان هستید؟ واقعیت شرکت Honeywell تسلا 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. دو آرایه ایجاد کنید آرایه و آرایه R به همان اندازه طول آرایه اصلی.
  2. اولین عنصر arrayL و آخرین عنصر arrayR را مقداردهی اولیه کنید.
  3. اگر عنصر آرایه فعلی بیشتر از عنصر قبلی باشد.
    1. به روز رسانی افزایش تعداد به فهرست.
    2. مقدار افزایش تعداد را به آرایه اختصاص دهید.
  4. آرایه را از راست به چپ عبور داده و بررسی کنید که آیا عدد بیشتر از عنصر قبلی است (عنصر سمت راست عنصر فعلی).
    1. سپس به روز رسانی کاهش تعداد به فهرست
    2. آرایه را به عدد در حال کاهش اختصاص دهید.
  5. برای هر درخواست داده شده ، arrayR [چپ] بزرگتر از بازگشت arrayL [راست] است ، در غیر این صورت false است.

توضیح

ما یک آرایه صحیح و یک محدوده سمت چپ ، راست داده ایم. ما خواسته ایم دریابیم که زیر مجموعه ای که با دامنه داده شده تشکیل شده است ، می تواند یک آرایه کوهستانی باشد یا خیر. اگر زیر مجموعه ای که به صورت آرایه ای شکل گرفته است ، آرایه کوهستانی باشد ، ما به true برمی گردیم ، وگرنه false برگردیم. ما دو آرایه را اعلام خواهیم کرد. یکی مربوط به سمت چپ آرایه و دیگری مربوط به سمت راست آرایه است. سپس ما این آرایه ها را خواهیم ساخت تا هر پرس و جو بتواند در فضای ثابت یک راه حل ارائه دهد.

اولین و آخرین عنصر آرایه ای را که به ترتیب arrayL و arrayR ایجاد کردیم ، مقداردهی اولیه خواهیم کرد. سپس آرایه را برای سمت چپ آرایه رد می کنیم یا می توانیم از چپ به راست بگوییم. اگر عنصر آرایه فعلی کمتر از عنصر قبلی باشد ، شرایط را بررسی خواهیم کرد. اگر درست تشخیص داده شود ، پس ما عدد در حال افزایش را به شاخص عدد به روز می کنیم. و عنصر فعلی arrayL را به هر تعداد و بدون در نظر گرفتن شرایط صحیح یا صحیح ، به عدد در حال افزایش اختصاص دهید.

در مرحله بعدی ما آرایه را از راست به چپ و اساساً از آخرین عنصر دوم به اولین عنصر آرایه رد می کنیم و بررسی می کنیم که آیا عنصر فعلی آرایه از عنصر بعدی بیشتر است یا خیر. از آنجا که ما از راست به چپ در حال پیمایش هستیم ، می توانیم بگوییم با عنصر قبلی بررسی کنید. اگر شرط درست یا درست باشد ، مقدار عددی در حال کاهش به شاخص فعلی تغییر می کند. بدون در نظر گرفتن شرایط ، آرایه را با کاهش تعداد به روز کنید. true برگردانید ، اگر آرایه R [سمت چپ] بزرگتر یا برابر آرایه L باشد [سمت راست] ، دیگر نادرست برگردید.

رمز

کد ++ 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) پاسخ دهیم.

پیچیدگی فضا

O (N) جایی که "n" تعداد عناصر آرایه است.