Опсег на пребарувања за последователна точна заграда


Ниво на тешкотија Тешко
Често прашувано во Амазон CodeNation Google PayPal Uber
Низа Магацинот

Дадена ти е низа од некои последователни загради, со други зборови, ти се дадени загради како „(“ и „)“ и ти е даден опсег на пребарувања како почетна точка и крајна точка. Проблемот „Прашања за опсег за најдолга корекција на заградата“ бара да се открие максималната должина на точната заграда на заградата или балансираните загради на заградата, во дадениот опсег на прашања, како што се „() ()“, „(())“, „( (())) “Итн.

пример

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

Објаснување

Единствените точни загради се на индексот 5 и 6.

Опсег на пребарувања за последователна точна заграда

 

Алгоритам

  1. Прогласи а Магацинот.
  2. Поминете низ целосниот низа и турнете ги сите држачи за отворање во оџакот.
    1. Ако не е држач за отворање, проверете дали оџакот не е празен, тогаш означете го тој индекс како 1.
      1. Добијте ја големината на оџакот и обележете го овој индекс на 1 и пополнете го горниот елемент од оџакот.
    2. Ако оџакот е празен, тогаш обележете го тој индекс како затворен држач како 0.
  3. Поминете ја должината на низата и сумирајте го секој елемент како што следува.
    1. затворени загради [i] = затворени загради [i] + затворени загради [i-1]
    2. отворање на загради [i] = отворање на загради [i] + отворање на загради [i-1]
  4. Земете го барањето како почетна точка и крајна точка.
    1. Проверете дали отворање на загради [почетна точка-1] = отворање на загради [почетна точка]
      1. Враќање (затворени загради [крајна точка] - отворање загради [почетна точка]) * 2.
    2. Друго враќање (затворени загради [крај на точка] - отворање на загради [почетна точка] + 1) * 2.

Објаснување

Дадена низа е низа загради, во кои се присутни типот на заграда '(' и ') и дадени се низа прашања. Пребарувањата се дадени во форма на почетна точка и крајна точка на под-низата. Од нас се бара да ја откриеме максималната должина на правилна или избалансирана заграда, во дадениот опсег. Точните или избалансирани држачи може да се сметаат за еднакви загради за отворање или затворање. Но, ни е даден опсег, мора да ја најдеме максималната должина што е можна со правилна поделба на загради.

Со цел да дознаете, структурата на податоци како Stack ќе биде од корист. Toе ги турнеме сите држачи за отворање во магацинот за да можеме да најдеме од каде треба да започнеме. Ако тековната заграда не е држач за отворање. Мораме да провериме дали оџакот не треба да биде празен за понатамошни операции. Се разбира, тоа ќе биде држач за затворање. Ако не е заграда за отворање, тогаш тој индекс на заградата за затворање го означуваме како 1. И во следниот чекор, ќе ја добиеме големината на оџакот и ќе ја третираме таа големина како индекс и ќе го означиме тој индекс како 1 од отвори загради, и поп елементот на оџакот. Поминувајте по должината на низата и сумирајте ја секоја вредност на отворање загради затворање загради и зачувајте ја збирот на секој индекс.

Земете ги барањата како влез и проверете го затворање загради ако почетната точка е еднаква на претходната вредност на отворање загради потоа вратете го бројот двапати од разликата на затворање на загради [endingPoint] - отворање на загради [почетна точка]. Друго, вратете го бројот како двапати разлика од затворањето на заградите [endingPoint] - openBrackets [почетната точка] + 1. willе го добиеме посакуваниот одговор.

Код

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

Јава код за да одговори на прашањата за опсег за последователна подолга точна заграда

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 (n + q) време Така, вкупната временска сложеност на алгоритмот е линеарна.

Комплексноста на просторот

Тој) каде „Н“ е должината на низата. Бидејќи создадовме две низи за складирање на заградата за отворање и броењето на заградата за затворање. Комплексноста на просторот е линеарна.