Эң узун крек кашектин кийинки натыйжалары боюнча суроолор


Кыйынчылык деңгээли катуу
Көп суралган Amazon CodeNation Гугл PayPal Uber
согуштук тизме чөмөлө

Сизге кээ бир кашаанын артынан кийинки ырааттуулук берилет, башкача айтканда, сизге '(' жана ')' сыяктуу кашаа берилет жана сизге сурам диапазону баштапкы жана аяктоочу чекит катары берилет. "" Эң узун туура кашаанын кийинки натыйжалуулугун сурап билүү "маселеси," () () "," (()) "," (") сыяктуу берилген сурамжылоо чегинде туура кашаа ырааттуулугун же салмактуу кашаа кашаларын максималдуу узундугун табууну сурайт. (()))" жана башкалар.

мисал

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

түшүндүрүү

Бир гана туура кашаа 5 жана 6 индексинде.

Эң узун крек кашектин кийинки натыйжалары боюнча суроолор

 

Algorithm

  1. Декларация a чөмөлө.
  2. Толугу менен өтүү аркан жана бардык ачылуучу кашаа стекке түртүп.
    1. Эгерде ал кашаа ачылбаса, анда стек бош эместигин текшерип, ал индексти 1 деп белгилеңиз.
      1. Стектин көлөмүн алып, ошол индексти 1 деп белгилеңиз жана үстүңкү элементти стектен чыгарыңыз.
    2. Эгерде стек бош болсо, анда ал индексти жабык каша менен 0 деп белгилеңиз.
  3. Жиптин узундугуна чейин басып өтүп, элементтин ар бирин төмөнкүдөй жыйынтыктаңыз.
    1. closedBrackets [i] = жабыкBrackets [i] + жабыкBrackets [i-1]
    2. openBrackets [i] = AçılışBrackets [i] + + OpenBrackets [i-1]
  4. Суроону startPoint жана endingPoint деп алыңыз.
    1. OpenBrackets [startPoint-1] = ochingBrackets [startPoint] экендигин текшериңиз
      1. Кайтып келүү (жабылганBrackets [endingPoint] - AçılışBrackets [startPoint]) * 2.
    2. Башка кайтып келүү (жабылганBrackets [endingPoint] - openBrackets [startPoint] + 1) * 2.

түшүндүрүү

Бизге кашаанын катар тизмеси берилген, анда '(' жана ')' кашаа түрү берилген жана бир катар суроолор берилген. Сурамдар башталгыч жана субарриканын аяктоочу чекити түрүндө берилет. Берилген диапазондо туура же тең салмактуу кашаанын максималдуу узундугун билип алууңузду суранабыз. Туура же тең салмактуу кашаа ачылуучу же жабылуучу кашаанын жоктугу катары каралышы мүмкүн. Бирок бизге диапазон берилген, биз кашаанын туура ырааттуулугу менен мүмкүн болгон максималдуу узундукту табышыбыз керек.

Муну билүү үчүн, Stack сыяктуу маалыматтар түзүмү пайдалуу болот. Баштай турган жерибизден таба алышыбыз үчүн, ачылуучу кашаанын бардыгын стекке түртүп жатабыз. Эгерде учурдагы кашаа ачылуучу кашаа болбосо. Кийинки операцияларды жүргүзүү үчүн стек бош эместигин текшеришибиз керек. Албетте, бул жабык кашаа болот. Эгерде ал ачылуучу кашаа эмес болсо, анда биз ошол жабык кашаанын индексин 1 деп белгилейбиз. Кийинки кадамда биз стектин көлөмүн алабыз жана ал көлөмдү индекс катары карап, ал индексти 1 деп белгилейбиз openBrackets, жана стек элементин поп. Жиптин узундугуна чейин басып өтүңүз жана анын ар бир маанисин жыйынтыктаңыз openBrackets жана closBackets жана сумманы ар бир индексте сактаңыз.

Суроолорду киргизүү катары кабыл алып, closBackets эгер баштапкы чекиттин мааниси мурунку маанисине барабар болсо openBrackets андан кийин санды битүү айырмаларынан эки эсе көп кайтарыңыз [endingPoint] - openBrackets [startPoint]. Башкасы, санды жабуунун айырмачылыгынан эки эсе көп кайтарат [endingPoint] - openBrackets [startPoint] + 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) аткарылган ар бир суроо үчүн. Бирок алдын-ала эсептөө талап кылат O (n + q) убакыт. Ошентип, алгоритмдин жалпы убакыт татаалдыгы сызыктуу.

Космостун татаалдыгы

O (N) кайда "N" жиптин узундугу. Биз ачылуучу кашаа жана жабуу кашаанын санын сактоо үчүн эки массивди жараткандыктан. Космостун татаалдыгы сызыктуу.