কোনও সাবহারি পাহাড়ের আকারে আছে কিনা তা সন্ধান করুন


কাঠিন্য মাত্রা কঠিন
প্রায়শই জিজ্ঞাসা করা হয় মর্দানী স্ত্রীলোক কালো শিলা সিসকো Citrix ফ্যাক্সেট Honeywell টেসলা ইয়ানডেক্স
বিন্যাস প্রশ্ন সমস্যা

সমস্যা বিবৃতি

"একটি সাবহারি পর্বতের আকারে আছে কিনা তা আবিষ্কার করুন" সমস্যাটি আপনাকে জানিয়েছে যে আপনাকে একটি দেওয়া হয়েছে পূর্ণসংখ্যা বিন্যাস এবং একটি পরিসীমা। সমস্যা বিবৃতিটি এটি জানতে জিজ্ঞাসা করে যে প্রদত্ত পরিসরের মধ্যে গঠিত সাব-অ্যারেটি পর্বত রূপের আকারে আছে কিনা? সংখ্যাগুলি ক্রমবর্ধমান ক্রমে বা হ্রাস ক্রমে বা প্রথমে বাড়তে থাকলে কমতে থাকলে মাউন্টেন অ্যারে গঠিত হয়।

উদাহরণ

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. প্রতিটি প্রদত্ত প্রশ্নের জন্য, অ্যারেআর [বামে] অ্যারেএল এর চেয়ে বড় [ডান] সত্য প্রত্যাবর্তন করুন, অন্যথায় মিথ্যা প্রত্যাবর্তন করুন।

ব্যাখ্যা

আমরা একটি পূর্ণসংখ্যা অ্যারে এবং বামে, ডানদিকে একটি পরিসর দিয়েছি। আমরা নির্ধারিত রেঞ্জের সাথে এতটা সুব্রেরি গঠন করা পাহাড়ের অ্যারে হতে পারে কিনা তা জানতে জিজ্ঞাসা করেছি। যদি গঠিত সুব্রেরি যদি পর্বত অ্যারে হয় তবে আমরা সত্যকে ফিরিয়ে দেব, অন্যথায় মিথ্যা ফিরিয়ে দেব। আমরা দুটি অ্যারে ঘোষণা করব। একটি অ্যারের বাম পাশের জন্য এবং অন্যটি অ্যারের ডান পাশের জন্য। তারপরে আমরা এই অ্যারেগুলি তৈরি করব যাতে প্রতিটি ক্যোয়ারী স্থির জায়গায় একটি সমাধান দিতে পারে।

আমরা যথাক্রমে অ্যারেএল এবং অ্যারেআর তৈরি করা অ্যারের প্রথম এবং শেষ উপাদানটি সূচনা করব। তারপরে আমরা অ্যারের বাম পাশের জন্য অ্যারেটি অতিক্রম করি বা আমরা বাম থেকে ডানে বলতে পারি। বর্তমান অ্যারে উপাদানটি আগের উপাদানগুলির চেয়ে কম থাকলে আমরা শর্তটি যাচাই করব। যদি এটি সত্য হিসাবে পাওয়া যায় তবে আমরা ক্রমবর্ধমান সংখ্যাটি সংখ্যার সূচকে আপডেট করব। এবং শর্তটি নির্বিশেষে শর্তটি সত্যই হোক না কেন প্রতিটি সময় বাড়ার সংখ্যাটিতে অ্যারেএল এর বর্তমান উপাদান নির্ধারণ করুন।

পরবর্তী পদক্ষেপে আমরা অ্যারেটি ডান থেকে বামে মূলত দ্বিতীয় শেষ উপাদান থেকে অ্যারের প্রথম উপাদানটিতে নিয়ে যাব এবং অ্যারের বর্তমান উপাদানটি পরবর্তী উপাদানের চেয়ে বড় কিনা তা পরীক্ষা করে দেখব। যেহেতু আমরা ডান থেকে বাম দিকে ঘুরে বেড়াচ্ছি, আমরা আগের উপাদানটির সাথে চেক বলতে পারি। যদি শর্তটি সঠিক বা সত্য হয় তবে হ্রাসের সংখ্যাটি বর্তমান সূচকে পরিবর্তিত হবে। শর্ত নির্বিশেষে হ্রাসকারী সংখ্যাটিতে অ্যারে আপডেট করুন। সত্যটি ফিরে আসুন, যদি অ্যারেআর [বামে] অ্যারেরআল [ডান] এর চেয়ে বড় বা তার সমান হয়, তবে অন্যথায় মিথ্যা ফিরে আসুন।

কোড

সি ++ কোড একটি সাবহারি পর্বতের আকারে আছে কিনা তা সন্ধান করতে

#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

জটিলতা বিশ্লেষণ

সময় জটিলতা

ও (এন + কিউ), উভয় অ্যারে তৈরি করার জন্য আমাদের ও (এন) সময় প্রয়োজন। এবং একবার অ্যারে নির্মিত হয়। আমরা ও (1) এ প্রশ্নের উত্তর দিতে পারি।

স্পেস জটিলতা ity

উপর) কোথায় "এন" অ্যারেতে উপাদানগুলির সংখ্যা।