가장 긴 올바른 대괄호 하위 시퀀스에 대한 범위 쿼리

난이도 하드
자주 묻는 질문 아마존 코드네이션 구글 페이팔 동네 짱
배열 스택조회수 19

일부 대괄호 하위 시퀀스의 시퀀스가 ​​제공됩니다. 즉, '('및 ')'와 같은 대괄호가 제공되고 시작점과 끝점으로 쿼리 범위가 제공됩니다. “가장 긴 올바른 대괄호 하위 시퀀스에 대한 범위 쿼리”문제는“() ()”,“(())”,“(와 같은 주어진 쿼리 범위 내에서 올바른 대괄호 하위 시퀀스 또는 균형 잡힌 괄호 대괄호의 최대 길이를 확인하도록 요청합니다. (())) '등

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. openingBrackets [i] = openingBrackets [i] + openingBrackets [i-1]
  4. 쿼리를 시작점 및 끝점으로 가져옵니다.
    1. openingBrackets [startingPoint-1] = openingBrackets [startingPoint]인지 확인하십시오.
      1. Return (closedBrackets [endingPoint] – openingBrackets [startingPoint]) * 2.
    2. Else return (closedBrackets [endingPoint]-openingBrackets [startingPoint] + 1) * 2.

설명

'('및 ')'유형의 괄호가 있고 다양한 쿼리가 제공되는 일련의 대괄호가 제공됩니다. 쿼리는 하위 배열의 시작점과 끝점의 형태로 제공됩니다. 주어진 범위 내에서 올바른 또는 균형 잡힌 괄호의 최대 길이를 찾아야합니다. 올바르거나 균형 잡힌 대괄호는 여는 대괄호 나 닫는 대괄호가 같지 않은 것으로 간주 할 수 있습니다. 그러나 우리는 범위가 주어졌고 대괄호의 정확한 하위 시퀀스로 가능한 최대 길이를 찾아야합니다.

알아 내기 위해서는 Stack like data structure가 도움이 될 것입니다. 시작해야 할 곳을 찾을 수 있도록 모든 여는 괄호를 스택에 밀어 넣을 것입니다. 현재 대괄호가 여는 대괄호가 아닌 경우. 추가 작업을 수행하기 위해 스택이 비어 있지 않아야하는지 확인해야합니다. 물론 닫는 대괄호가 될 것입니다. 여는 대괄호가 아니면 닫는 대괄호 인덱스를 1로 표시합니다. 다음 단계에서는 스택의 크기를 가져 와서 해당 크기를 인덱스로 처리하고 해당 인덱스를 다음 중 1로 표시합니다. 오프닝 브라켓, 스택의 요소를 팝합니다. 문자열의 길이까지 이동하고 각 값을 합산합니다. 오프닝 브래킷closeBrackets 각 인덱스에 합계를 저장하십시오.

쿼리를 입력으로 취하고 closeBrackets 시작점 값이 이전 값과 같으면 오프닝 브래킷 그런 다음 closedBrackets [endingPoint] – openingBrackets [startingPoint] 차이의 두 배로 숫자를 반환합니다. 그렇지 않으면 closedBrackets [endingPoint] – openingBrackets [startingPoint] + 1의 차이의 두 배로 숫자를 반환합니다. 원하는 답을 얻을 수 있습니다.

암호

Longest Correct Bracket Subsequence에 대한 범위 쿼리에 응답하는 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

Longest Correct Bracket Subsequence에 대한 범위 쿼리에 응답하는 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) 수행 된 각 쿼리에 대해. 그러나 사전 계산에는 O (n + q) 시각. 따라서 알고리즘의 총 시간 복잡도는 선형입니다.

공간 복잡성

O (N) 어디에 "엔" 문자열의 길이입니다. 여는 대괄호와 닫는 대괄호 수를 저장하기 위해 두 개의 배열을 만들었 기 때문입니다. 공간 복잡성은 선형입니다.

Translate »