محدوده نمایش داده شده برای طولانی ترین دنباله براکت صحیح


سطح دشواری سخت
اغلب در آمازون CodeNation گوگل پی پال حال بارگذاری
صف پشته

دنباله ای از چند دنباله براکت به شما داده می شود ، به عبارت دیگر ، براکت هایی مانند '(' و ')' به شما داده می شود و به شما یک محدوده پرسش به عنوان نقطه شروع و نقطه پایان داده می شود. مسئله "محدوده نمایش داده شده برای طولانی ترین دنباله براکت" از شما می خواهد حداکثر طول دنباله صحیح براکت یا پرانتز متعادل را در یک محدوده پرسش مشخص مانند "() ()" ، "(())" ، "() (()))" و غیره.

مثال

String s = “()())()(())( ”
startingPoint = 4
endingPoint = 8
2

توضیح

تنها براکت های صحیح در شاخص 5 و 6 قرار دارند.

محدوده نمایش داده شده برای طولانی ترین دنباله براکت صحیح

 

الگوریتم

  1. اعلام الف پشته.
  2. عبور از کامل رشته و تمام براکتهای باز را به داخل پشته فشار دهید.
    1. اگر براکت باز نیست ، بررسی کنید که آیا پشته خالی نیست ، سپس این شاخص را 1 نشان دهید.
      1. اندازه پشته را بدست آورید و آن شاخص را به 1 علامت گذاری کنید و عنصر بالایی را از پشته پاپ کنید.
    2. اگر پشته خالی است ، آن شاخص را که دارای براکت بسته است ، به عنوان 0 علامت گذاری کنید.
  3. از طول رشته عبور کنید و هر یک از عناصر را به صورت زیر جمع کنید.
    1. براکت بسته [من] = براکت بسته [من] + براکت بسته [من-1]
    2. opensBrackets [i] = openBrackets [i] + opensBrackets [i-1]
  4. پرس و جو را به عنوان startPoint و endingPoint در نظر بگیرید.
    1. آیا باز کردن Brackets [startPoint-1] = باز کردن Brackets [startPoint] را بررسی کنید
      1. بازگشت (براکت های بسته [endingPoint] - بازکردن براکت ها [شروع نقطه]) * 2.
    2. بازگشت دیگر (براکت های بسته [پایان پوینت] - بازکردن براکت ها [شروع نقطه] + 1) * 2.

توضیح

به ما یک رشته توالی براکت داده می شود که نوع پرانتز '(' و ') در آنها وجود دارد و طیف وسیعی از نمایش داده می شود. نمایش داده شد در قالب یک نقطه شروع و یک نقطه پایان از زیر مجموعه. از ما خواسته می شود حداکثر طول پرانتز صحیح یا متعادل را در محدوده داده شده دریابیم. براکت های صحیح یا متعادل را می توان بدون براکت باز یا بسته در نظر گرفت. اما به ما یک محدوده داده می شود ، ما باید حداکثر طولی را که با دنباله صحیح براکت امکان پذیر است پیدا کنیم.

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

س quالات را به عنوان ورودی در نظر بگیرید و علامت بزنید بستن اگر مقدار نقطه شروع با مقدار قبلی برابر باشد پرانتز سپس عدد را دو برابر تفاوت با بسته شدن Brackets [endingPoint] - باز کردن Brackets [startPoint] برگردانید. در غیر اینصورت عدد را به عنوان دو برابر تفاوت با بسته شدن براکتها [endingPoint] برگردانید - openBrackets [با شروع نقطه] + 1. ما جواب مورد نظر را خواهیم گرفت.

رمز

کد ++ C برای پاسخ به سeriesالات محدوده طولانی ترین پیام صحیح براکت

#include<iostream>
#include<cstring>
#include<stack>

using namespace std;

void correctBracketsLength(int OPENINGBRACKETS[], int CLOSEDBRACKETS[], char* str, int n)
{
    stack<int> STACK;
    int result = 0;
    for (int i = 0; i < n; i++)
    {
        if (str[i] == '(')
            STACK.push(i);
        else
        {
            if (!STACK.empty())
            {
                CLOSEDBRACKETS[i] = 1;
                OPENINGBRACKETS[STACK.top()] = 1;
                STACK.pop();
            }
            else
                CLOSEDBRACKETS[i] = 0;
        }
    }
    for (int i = 1; i < n; i++)
    {
        CLOSEDBRACKETS[i] += CLOSEDBRACKETS[i - 1];
        OPENINGBRACKETS[i] += OPENINGBRACKETS[i - 1];
    }
}
int query(int OPENINGBRACKETS[], int CLOSEDBRACKETS[], int startingPoint, int endingPoint)
{
    if (OPENINGBRACKETS[startingPoint - 1] == OPENINGBRACKETS[startingPoint])
    {
        return (CLOSEDBRACKETS[endingPoint] - OPENINGBRACKETS[startingPoint]) * 2;
    }
    else
    {
        return (CLOSEDBRACKETS[endingPoint] - OPENINGBRACKETS[startingPoint] + 1) * 2;
    }
}
int main()
{
    char str[] = "()())()(())(";
    int n = strlen(str);

    int CLOSEDBRACKETS[n + 1] = { 0 };
    int OPENINGBRACKETS[n + 1] = { 0 };

    correctBracketsLength(OPENINGBRACKETS, CLOSEDBRACKETS, str, n);

    int startingPoint = 4, endingPoint = 8;

    cout << "Maximum Length within "
         << startingPoint << " and " << endingPoint << " = "
         << query(OPENINGBRACKETS, CLOSEDBRACKETS, startingPoint, endingPoint) << endl;

    return 0;
}
Maximum Length within 4 and 8 = 2

کد جاوا برای پاسخ به سeriesالات محدوده طولانی ترین پیام صحیح براکت

import java.util.*;

class LongestCorrectBracket
{
    public static void correctBracketsLength(int OPENINGBRACKETS[], int CLOSEDBRACKETS[], String str, int n)
    {
        Stack<Integer> STACK = new Stack<>();;

        for(int i = 0; i < n; i++)
        {
            if (str.charAt(i) == '(')
                STACK.add(i);
            else
            {
                if (!STACK.isEmpty())
                {
                    CLOSEDBRACKETS[i] = 1;
                    OPENINGBRACKETS[STACK.peek()] = 1;
                    STACK.pop();
                }
                else
                    CLOSEDBRACKETS[i] = 0;
            }
        }
        for(int i = 1; i < n; i++)
        {
            CLOSEDBRACKETS[i] += CLOSEDBRACKETS[i - 1];
            OPENINGBRACKETS[i] += OPENINGBRACKETS[i - 1];
        }
    }
    static int query(int OPENINGBRACKETS[], int CLOSEDBRACKETS[], int startingPoint, int endingPoint)
    {
        if (OPENINGBRACKETS[startingPoint - 1] == OPENINGBRACKETS[startingPoint])
        {
            return (CLOSEDBRACKETS[endingPoint] - OPENINGBRACKETS[startingPoint]) * 2;
        }
        else
        {
            return (CLOSEDBRACKETS[endingPoint] - OPENINGBRACKETS[startingPoint] + 1) * 2;
        }
    }
    public static void main(String[] args)
    {
        String str = "()())()(())(";
        int n = str.length();

        int CLOSEDBRACKETS[] = new int[n + 1];
        int OPENINGBRACKETS[] = new int[n + 1];

        correctBracketsLength(OPENINGBRACKETS, CLOSEDBRACKETS, str, n);

        int startingPoint = 4, endingPoint = 8;
        System.out.print("Maximum Length within " +
                         startingPoint + " and " + endingPoint +
                         " = " + query(OPENINGBRACKETS, CLOSEDBRACKETS, startingPoint,
                                       endingPoint) + "\n");
    }
}
Maximum Length within 4 and 8 = 2

تحلیل پیچیدگی

پیچیدگی زمان

O (1) برای هر پرسش انجام شده اما پیش محاسبات نیاز دارد O (n + q) زمان. بنابراین کل پیچیدگی زمان الگوریتم خطی است.

پیچیدگی فضا

O (N) جایی که "n" طول رشته است. از آنجا که ما دو آرایه برای ذخیره سازی براکت باز و تعداد براکت بسته ایجاد کرده ایم. پیچیدگی فضا خطی است.