最長の正しいブラケットサブシーケンスの範囲クエリ


難易度 ハード
よく聞かれる Amazon (アマゾン) コードネーション Google PayPal ユーバー
配列 スタック

いくつかの角かっこサブシーケンスのシーケンスが与えられます。つまり、「(」および「)」のような角かっこが与えられ、開始点および終了点としてクエリ範囲が与えられます。 問題「最長の正しい角かっこサブシーケンスの範囲クエリ」では、「()()」、「(())」、「(( (()))」など。

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. オープニングブラケット[i] =オープニングブラケット[i] +オープニングブラケット[i-1]
  4. クエリをstartingPointおよびendingPointとして取得します。
    1. openBrackets [startingPoint-1] = openBrackets [startingPoint]かどうかを確認します
      1. Return(closedBrackets [endingPoint] –openingBrackets [startingPoint])* 2。
    2. それ以外の場合は、return(closedBrackets [endingPoint] -openingBrackets [startingPoint] + 1)* 2。

説明

'('および ')'タイプの括弧が存在する括弧のシーケンスの文字列が与えられ、クエリの範囲が与えられます。 クエリは、サブアレイの開始点と終了点の形式で提供されます。 与えられた範囲内で、正しい括弧またはバランスの取れた括弧の最大長を見つけるように求められます。 正しいブラケットまたはバランスの取れたブラケットは、開閉ブラケットの数が等しいと見なすことができます。 ただし、範囲が与えられているため、角かっこの正しいサブシーケンスで可能な最大長を見つける必要があります。

見つけるために、データ構造のようなスタックは有益です。 開始する場所を見つけることができるように、すべての開始ブラケットをスタックに押し込みます。 現在のブラケットが開始ブラケットでない場合。 さらに操作を行うために、スタックが空になっていないかどうかを確認する必要があります。 もちろん、それは閉じ括弧になります。 開始ブラケットでない場合は、その終了ブラケットのインデックスを1としてマークします。次のステップでは、スタックのサイズを取得し、そのサイズをインデックスとして扱い、そのインデックスを1としてマークします。 オープニングブラケット、 スタックの要素をポップします。 文字列の長さまでトラバースし、の各値を合計します 開口部ブラケット クロージングブラケット 合計を各インデックスに保存します。

クエリを入力として受け取り、チェックインします クロージングブラケット 開始点の値が前の値と等しい場合 開口部ブラケット 次に、closeingBrackets [endingPoint] –openingBrackets [startingPoint]の差の1倍として数値を返します。 それ以外の場合は、closeingBrackets [endingPoint] – openBrackets [startingPoint] +XNUMXの差のXNUMX倍として数値を返します。目的の答えが得られます。

コード

最長の正しいブラケットサブシーケンスの範囲クエリに応答する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) 実行されたクエリごとに。 しかし、事前計算には O(n + q) 時間。 したがって、アルゴリズムの合計時間計算量は線形です。

スペースの複雑さ

O(N) where 「n」 文字列の長さです。 開始ブラケットと終了ブラケットの数を格納するためにXNUMXつの配列を作成したため。 空間の複雑さは線形です。