استعلامات النطاق لأطول قوس متتالي صحيح


مستوى الصعوبة الثابت
كثيرا ما يطلب في أمازون CodeNation جوجل Paypal اوبر
مجموعة كومة

يتم إعطاؤك سلسلة من بعض الأقواس اللاحقة ، بمعنى آخر ، يتم إعطاؤك أقواس مثل "(" و ")" ويتم منحك نطاق استعلام كنقطة بداية ونقطة نهاية. تطلب مشكلة "استعلامات النطاق لأطول تتابع قوس صحيح" معرفة الحد الأقصى لطول الأقواس الصحيحة اللاحقة أو الأقواس المتوازنة ، ضمن نطاق استعلام معين ، مثل "() ()" ، "(())" ، "( (()))" إلخ.

مثال

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

تفسير

الأقواس الصحيحة الوحيدة موجودة في الفهرس 5 و 6.

استعلامات النطاق لأطول قوس متتالي صحيح

 

خوارزمية

  1. تعلن أ كومة.
  2. اجتياز كامل سلسلة وادفع جميع أقواس الفتح إلى المكدس.
    1. إذا لم يكن قوس الفتح ، فتحقق مما إذا كانت المكدس ليست فارغة ، ثم حدد هذا الفهرس على أنه 1.
      1. احصل على حجم المكدس وقم بتمييز هذا الفهرس على 1 ، وقم بإخراج العنصر العلوي من المكدس.
    2. إذا كان المكدس فارغًا ، فقم بتمييز هذا الفهرس الذي يحتوي على قوس مغلق على أنه 0.
  3. اجتياز حتى طول السلسلة ولخص كل عنصر على النحو التالي.
    1. أقواس مغلقة [i] = أقواس مغلقة [i] + أقواس مغلقة [i-1]
    2. openBrackets [i] = openBrackets [i] + openBrackets [i-1]
  4. خذ الاستعلام كنقطة بداية ونهاية نقطة.
    1. تحقق مما إذا كان openBrackets [startPoint-1] = openBrackets [نقطة البداية]
      1. العودة (ClosedBrackets [endPoint] - openBrackets [نقطة البداية]) * 2.
    2. عودة أخرى (أقواس مغلقة [نقطة النهاية] - أقواس الفتح [نقطة البداية] + 1) * 2.

تفسير

لدينا سلسلة من تسلسل الأقواس ، حيث يوجد نوع "(" و ")" من الأقواس ، ونطاق من الاستعلامات. يتم تقديم الاستعلامات في شكل نقطة بداية ونقطة نهاية للمصفوفة الفرعية. مطلوب منا معرفة الحد الأقصى لطول الأقواس الصحيحة أو المتوازنة ضمن النطاق المحدد. يمكن اعتبار الأقواس الصحيحة أو المتوازنة على أنها لا تساوي أقواس الفتح أو الإغلاق. لكن لدينا نطاقًا ، وعلينا إيجاد أقصى طول ممكن من خلال التتابع الصحيح للأقواس.

من أجل معرفة ذلك ، ستكون بنية البيانات مثل Stack مفيدة. سنقوم بدفع جميع الأقواس الافتتاحية إلى المكدس حتى نتمكن من إيجاد المكان الذي يجب أن نبدأ منه. إذا كان القوس الحالي ليس قوس فتح. يجب أن نتحقق مما إذا كان يجب ألا يكون المكدس فارغًا لإجراء مزيد من العمليات. بالطبع ، سيكون قوس إغلاق. إذا لم يكن قوس فتح ، فإننا نضع علامة على فهرس قوس الإغلاق على أنه 1. وفي الخطوة التالية ، سنحصل على حجم المكدس ونتعامل مع هذا الحجم كمؤشر ونضع علامة على هذا الفهرس باعتباره 1 من الافتتاح وافرقع عنصر المكدس. اجتياز حتى طول السلسلة ، ولخص كل قيمة من قيم الافتتاح و إغلاق الأقواس وتخزين المجموع في كل مؤشر.

خذ الاستعلامات كمدخلات ، وتحقق في إغلاق الأقواس إذا كانت قيمة نقطة البداية تساوي القيمة السابقة لـ الافتتاح ثم قم بإرجاع الرقم بضعف الفرق بين قوسين الإغلاق [نقطة النهاية] - أقواس الفتح [نقطة البداية]. عدا ذلك ، قم بإرجاع الرقم بضعف الفرق بين قوسين الإغلاق [نقطة النهاية] - أقواس الفتح [نقطة البداية] + 1. سنحصل على الإجابة المطلوبة.

رمز

كود C ++ للإجابة على استعلامات النطاق الخاصة بأطول قوس متتالي صحيح

#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

كود Java للإجابة على استعلامات النطاق لأطول تتابع القوس الصحيح

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

تحليل التعقيد

تعقيد الوقت

يا (1) لكل استعلام تم إجراؤه. لكن يتطلب الأمر يا (ن + ف) زمن. وبالتالي ، فإن التعقيد الزمني الإجمالي للخوارزمية يكون خطيًا.

تعقيد الفضاء

O (ن) أين "ن" هو طول السلسلة. منذ أن أنشأنا مصفوفتين لتخزين قوس الفتح وعدد قوس الإغلاق. تعقيد الفضاء خطي.