Ən uzun düz bracket sonrakı üçün sıra sorğuları

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

cuqquldamaq Facebook LinkedIn Bufer Reddit Tumblr

Sizə bəzi mötərizələrin ardıcıllığı verilir, başqa sözlə, '(' və ')' kimi mötərizələr verilir və başlanğıc nöqtəsi və bitmə nöqtəsi olaraq sorğu aralığı verilir. “Ən uzun düz bracket sonrası üçün aralıq sorğular” problemi, müəyyən bir sorğu aralığında “() ()”, “(())”, “( (())) ”Və s.

Mündəricat

misal

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

Izahat

Yalnız doğru mötərizə 5 və 6-dır.

Alqoritm

Bəyan edin a Qalaq.
Tam keçin sim və bütün açılış mötərizələrini yığına itələyin.
1. Açılış mötərizəsi deyilsə, yığının boş olmadığını yoxlayın, sonra bu indeksi 1 kimi qeyd edin.
  1. Yığın ölçüsünü alın və bu göstəricini 1 olaraq qeyd edin və üst elementi yığından çıxartın.
2. Yığın boşdursa, o zaman bağlanan mötərizəni 0 olaraq qeyd edin.
Simin uzunluğuna qədər keçin və elementin hər birini aşağıdakı kimi yekunlaşdırın.
1. closedBrackets [i] = kapalıBrackets [i] + closedBrackets [i-1]
2. AçılışBrackets [i] = AçılışBrackets [i] + AçılışBrackets [i-1]
Sorğunu başlanğıc nöqtəsi və son nöqtəsi kimi götürün.
1. AçılışBrackets [startPoint-1] = açılışBrackets [startPoint] olub olmadığını yoxlayın
  1. Qayıdış (qapalıBrackets [endingPoint] - AçılışBrackets [startPoint]) * 2.
2. Başqa qayıdış (qapalıBrackets [endingPoint] - AçılışBrackets [startPoint] + 1) * 2.

Izahat

Bizə '(' və ')' tip mötərizənin mövcud olduğu və bir sıra sorğuların verildiyi mötərizələr ardıcıllığı verilir. Sorğular subarrayın başlanğıc nöqtəsi və bitmə nöqtəsi şəklində verilir. Verilən interval daxilində düzgün və ya balanslı mötərizənin maksimum uzunluğunu öyrənməyimiz istənir. Düz və ya balanslı mötərizələr açılış və bağlanma mötərizələrinin bərabər olmaması kimi qəbul edilə bilər. Ancaq bizə bir sıra verilir, mötərizələrin düzgün ardıcıllığı ilə mümkün olan maksimum uzunluğu tapmalıyıq.

Tapmaq üçün, məlumat quruluşu kimi yığın faydalı olacaq. Başlamalı olduğumuz yerdən tapa bilmək üçün bütün açılış mötərizələrini yığına itələyəcəyik. Mövcud mötərizə açılış mötərizəsi deyilsə. Daha çox əməliyyat aparmaq üçün yığının boş olmamasını yoxlamalıyıq. Əlbətdə ki, bir bağlanma mötərizəsi olacaq. Açılış mötərizəsi deyilsə, o bağlama mötərizəsi indeksini 1 kimi qeyd edirik. Növbəti addımda yığının ölçüsünü alacağıq və bu ölçünü indeks olaraq qəbul edəcəyik və bu indeksi 1 kimi qeyd edəcəyik. açılışBrackets, və yığının elementini açın. Sətrin uzunluğuna qədər keçin və hər dəyərini cəmləyin açılışBrackets və bağlama mötərizələri və cəmi hər indeksdə saxlayın.

Sorğuları giriş olaraq götürün və yoxlayın bağlama mötərizələri başlanğıc nöqtəsi dəyəri əvvəlki dəyərinə bərabərdirsə açılışBrackets sonra bu rəqəmi bağlanmaBrackets [endingPoint] - açılışBrackets [startPoint] fərqinin iki qatından çox qaytarın. Başqa rəqəmi bağlanmaBrackets [endingPoint] - AçılışBrackets [startPoint] + 1. Fərqinin iki qatından geri qaytarın. İstədiyiniz cavabı alacağıq.

Kodu

C ++ kodu ən uzun düz bracket sonrakı ardıcıllığı üçün suallara cavab vermək üçün

#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

Ən uzun düz bracket sonrakı ardıcıllığı üçün sorğuların cavablandırılması üçün Java kodu

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

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (1) hər bir sorğu üçün. Ancaq əvvəlcədən hesablama tələb olunur O (n + q) vaxt. Beləliklə, alqoritmin ümumi zaman mürəkkəbliyi xətti olur.

Kosmik Mürəkkəblik

O (n) hara "N" ipin uzunluğudur. Açılış mötərizəsini və bağlama mötərizəsini saxlamaq üçün iki sıra yaratdığımızdan. Məkan mürəkkəbliyi xətti xarakter daşıyır.

cuqquldamaq Facebook LinkedIn Bufer Reddit Tumblr