Дархостҳои диапазон барои пайдарпаии дарозтарини дуруст


Сатҳи душворӣ мушкил
Аксар вақт пурсида мешавад Amazon CodeNation Google PayPal Uber
тартиботи ҳарбӣ тӯда

Ба шумо пайдарпаии баъзе пайдарпаии қавс дода мешавад, ба ибораи дигар, ба шумо қавсҳо ба монанди '(' ва ')' дода мешаванд ва ба шумо диапазони пурсишҳо ҳамчун нуқтаи оғоз ва нуқтаи хотима дода мешаванд. Масъалаи "Дархостҳои диапазон барои пайдоиши дурусти қавс" дархост мекунанд, ки дарозии максималии пайдоиши дурусти кронштейн ё қавсҳои мутавозин дар доираи саволҳои додашуда ба монанди "() ()", "(())", "( (())) ”Ва ғ.

мисол

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

Шарҳ

Ягона қавсайнҳои дуруст дар индекси 5 ва 6 мебошанд.

Дархостҳои диапазон барои пайдарпаии дарозтарини дуруст

 

Алгоритм

  1. Эълом кунед a тӯда.
  2. Пурра гардиш кунед данд ва ҳамаи қавсҳои кушодаро ба анбор тела диҳед.
    1. Агар он қавс кушода нашавад, пас анбораро холӣ нестед, пас ин нишондиҳандаро ҳамчун 1 қайд кунед.
      1. Андозаи стекро гиред ва ин нишондиҳандаро ба 1 қайд кунед ва унсури болоро аз стек кашед.
    2. Агар стек холӣ бошад, он гоҳ индекси крекетони пӯшида ба 0 гузоред.
  3. То дарозии сатр ҳаракат кунед ва ҳар як элементро тавре ҷамъбаст кунед.
    1. closedBrackets [i] = closedBrackets [i] + closedBrackets [i-1]
    2. openBrackets [i] = кушодани қавс [i] + кушодани қавс [i-1]
  4. Дархостро ҳамчун startPoint ва endingPoint гиред.
    1. Санҷед, ки openBrackets [startPoint-1] = кушоданиBrackets [startPoint]
      1. Бозгашт (пӯшидаBrackets [endingPoint] - кушодани Бракетҳо [startPoint]) * 2.
    2. Бозгашти дигар (closedBrackets [endingPoint] - кушодани Бракетҳо [startPoint] + 1) * 2.

Шарҳ

Ба мо як қатор пайдарпаии қавс дода мешавад, ки дар он навъи '(' ва ')' қавс мавҷуд аст ва як қатор саволҳо дода мешаванд. Дархостҳо дар шакли нуқтаи ибтидоӣ ва нуқтаи хотимаи зергурӯҳ дода мешаванд. Аз мо хоҳиш карда мешавад, ки дарозии максималии қавсҳои дуруст ё мутавозинро дар доираи додашуда фаҳмед. Қавсҳои дуруст ё мутавозин метавонанд баробар набудани қавсҳои кушодан ё пӯшида ҳисоб карда шаванд. Аммо ба мо диапазон дода мешавад, мо бояд дарозии максималиро, ки бо пайдоиши дурусти қавс имконпазир аст, ёбем.

Бо мақсади фаҳмидани он, Stack монанди сохтори додаҳо муфид хоҳад буд. Мо ҳама кронштейнҳои кушодро ба стек тела медиҳем, то мо аз куҷо сар карданро пайдо кунем. Агар қавсайн кунҷетӣ қавсайн кушода нашавад. Мо бояд тафтиш кунем, ки оё анбор барои анҷом додани амалиёти минбаъда холӣ набошад. Албатта, ин як қавсест пӯшида хоҳад буд. Агар он қавсайн кушода нашавад, мо он индекси қавсҳои пӯшидашударо ҳамчун 1 қайд мекунем. Ва дар қадами оянда мо андозаи стакаро мегирем ва ин ҳаҷмро ҳамчун индекс ҳисоб мекунем ва ин нишондиҳандаро ҳамчун 1 кушодани қавс, ва поп унсури анбораро кашед. То дарозии сатр ҳаракат кунед ва ҳар як арзиши кушодани қавс ва бастани кронштейнҳо ва маблағро дар ҳар як нишондиҳанда нигоҳ доред.

Дархостҳоро ҳамчун вуруд қабул кунед ва дар бастани кронштейнҳо агар арзиши нуқтаи ибтидоӣ ба арзиши қаблии баробар бошад кушодани қавс пас рақамро аз фарқи closBrackets [endingPoint] - openBrackets [startPoint] ду маротиба баргардонед. Дигар ин рақамро ду маротиба аз фарқи closBackets [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

Таҳлили мураккабӣ

Мураккабии вақт

О (1) барои ҳар як дархости иҷрошуда. Аммо пешакӣ талаб мекунад O (n + q) вақт. Ҳамин тариқ, мураккабии умумии вақти алгоритм хатӣ аст.

Мураккабии фазо

Эй (н) ки дар "Н" дарозии сатр аст. Азбаски мо ду массивро барои нигоҳ доштани қавсиди кушод ва ҳисобкунии қавс сохтаем. Мураккабии фазо хаттӣ аст.