Запросы диапазона для самой длинной подпоследовательности правильной скобки


Сложный уровень Жесткий
Часто спрашивают в Амазонка CodeNation Google PayPal Uber
массив Стек

Вам дается последовательность некоторых подпоследовательностей скобок, другими словами, вам даются скобки, такие как '(' и ')', и вам дается диапазон запроса в качестве начальной и конечной точек. Задача «Запросы диапазона для самой длинной подпоследовательности правильных скобок» просит определить максимальную длину правильной подпоследовательности скобок или сбалансированных скобок в пределах заданного диапазона запроса, например «() ()», «(())», «( (()))" так далее.

Пример

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

объяснение

Единственные правильные скобки - это индексы 5 и 6.

Запросы диапазона для самой длинной подпоследовательности правильной скобки

 

Алгоритм

  1. Объявить Стек.
  2. Пройдите полный строка и вставьте все открывающиеся скобки в стопку.
    1. Если это не открывающая скобка, проверьте, не пуст ли стек, а затем отметьте этот индекс как 1.
      1. Получите размер стека, отметьте этот индекс равным 1 и вытолкните верхний элемент из стека.
    2. Если стек пуст, отметьте этот индекс с закрытой скобкой как 0.
  3. Пройдите до длины строки и просуммируйте каждый элемент следующим образом.
    1. closedBrackets [i] = closedBrackets [i] + closedBrackets [i-1]
    2. openBrackets [i] = openBrackets [i] + openBrackets [i-1]
  4. Возьмите запрос как начальную точку и конечную точку.
    1. Проверьте, если openBrackets [startPoint-1] = openBrackets [startPoint]
      1. Возврат (закрытые скобки [конечная точка] - открывающие скобки [начальная точка]) * 2.
    2. Иначе return (closedBrackets [endPoint] - openBrackets [startPoint] + 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

Анализ сложности

Сложность времени

O (1) для каждого выполненного запроса. Но предварительный расчет требует О (п + д) время. Таким образом, общая временная сложность алгоритма линейна.

Космическая сложность

О (п) в котором «Н» - длина строки. Поскольку мы создали два массива для хранения количества открывающих и закрывающих скобок. Сложность пространства линейна.