Ερωτήματα εύρους για τη μεγαλύτερη ακολουθία σωστών αγκυλών  


Επίπεδο δυσκολίας Σκληρά
Συχνές ερωτήσεις αμαζόνα CodeNation Google PayPal Uber
Παράταξη Στοίβα

Σας δίνεται μια σειρά ακολουθίας ορισμένων αγκυλών, με άλλα λόγια, σας παρέχονται αγκύλες όπως '(' και ')' και σας δίνεται ένα εύρος ερωτημάτων ως σημείο εκκίνησης και λήξης. Το πρόβλημα "Ερωτήματα εύρους για τη μεγαλύτερη ακολουθία σωστών αγκυλών" ζητά να μάθετε το μέγιστο μήκος της σωστής ακολουθίας αγκύλης ή αγκύλες ισορροπημένης παρένθεσης, εντός ενός δεδομένου εύρους ερωτημάτων, όπως "() ()", "(())", "( (()))" και τα λοιπά.

Παράδειγμα  

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

εξήγηση

Οι μόνες σωστές αγκύλες βρίσκονται στο ευρετήριο 5 και 6.

Ερωτήματα εύρους για τη μεγαλύτερη ακολουθία σωστών αγκυλώνΚαρφώστε

 

Αλγόριθμος  

  1. Δήλωση α Στοίβα.
  2. Διασχίστε το πλήρες κορδόνι και σπρώξτε όλες τις αγκύλες ανοίγματος στη στοίβα.
    1. Εάν δεν ανοίγει το βραχίονα, ελέγξτε αν η στοίβα δεν είναι κενή, τότε σημειώστε αυτό το ευρετήριο ως 1.
      1. Αποκτήστε το μέγεθος της στοίβας και σημειώστε αυτό το ευρετήριο σε 1 και ανοίξτε το επάνω στοιχείο από τη στοίβα.
    2. Εάν η στοίβα είναι κενή, σημειώστε ότι ο δείκτης έχει κλειστή αγκύλη ως 0.
  3. Περάστε μέχρι το μήκος της συμβολοσειράς και αθροίστε κάθε στοιχείο ως εξής.
    1. κλειστό βραχίονες [i] = κλειστό βραχίονες [i] + κλειστό βραχίονες [i-1]
    2. openingBrackets [i] = άνοιγμαBrackets [i] + άνοιγμαBrackets [i-1]
  4. Πάρτε το ερώτημα ως σημείο εκκίνησης και λήξης.
    1. Ελέγξτε εάν το άνοιγμαBrackets [startPoint-1] = άνοιγμαBrackets [startPoint]
      1. Επιστροφή (κλειστάBrackets [endPoint] - άνοιγμαBrackets [startPoint]) * 2.
    2. Επιστροφή αλλιώς (κλειστές αγκύλες [τελικό σημείο] - άνοιγμα αγκύλες [αρχικό σημείο] + 1) * 2.

εξήγηση  

Μας δίνεται μια σειρά ακολουθιών παρενθέσεων, στην οποία υπάρχει ο τύπος παρένθεσης '(' και ')' και δίνεται μια σειρά ερωτημάτων. Τα ερωτήματα δίνονται με τη μορφή αφετηρίας και τελικού σημείου του subarray. Ζητείται να μάθουμε το μέγιστο μήκος της σωστής ή ισορροπημένης παρένθεσης, εντός του δεδομένου εύρους. Οι σωστές ή ισορροπημένες αγκύλες μπορούν να θεωρηθούν ίσες με τις αγκύλες ανοίγματος ή κλεισίματος. Αλλά μας δίνεται μια σειρά, πρέπει να βρούμε το μέγιστο δυνατό μήκος με μια σωστή ακολουθία αγκυλών.

Βλέπε επίσης
Άθροισμα Λύσης Leetcode Subarrays Μονής Μονάδας

Για να το μάθετε, η δομή δεδομένων σαν στοίβα θα είναι επωφελής. Θα σπρώξουμε όλες τις αγκύλες ανοίγματος στη στοίβα, ώστε να βρούμε από πού πρέπει να ξεκινήσουμε. Εάν το τρέχον βραχίονα δεν είναι ένα άνοιγμα. Πρέπει να ελέγξουμε εάν η στοίβα δεν πρέπει να είναι κενή για να κάνουμε περαιτέρω εργασίες. Φυσικά, θα είναι ένα κλείσιμο. Εάν δεν είναι αγκύλη ανοίγματος, τότε επισημαίνουμε αυτό το δείκτη αγκύλης κλεισίματος ως 1. Και στο επόμενο βήμα, θα πάρουμε το μέγεθος της στοίβας και θα αντιμετωπίσουμε αυτό το μέγεθος ως ευρετήριο και θα επισημάνουμε αυτόν τον δείκτη ως 1 άνοιγμα βραχιόνων, και ανοίξτε το στοιχείο της στοίβας. Περάστε μέχρι το μήκος της συμβολοσειράς και αθροίστε κάθε τιμή του άνοιγμα βραχιόνων κλείσιμο βραχιολιών και αποθηκεύστε το άθροισμα σε κάθε ευρετήριο.

Πάρτε τα ερωτήματα ως είσοδο και ελέγξτε το κλείσιμο βραχιολιών εάν η τιμή του σημείου εκκίνησης είναι ίση με την προηγούμενη τιμή του άνοιγμα βραχιόνων στη συνέχεια επιστρέψτε τον αριθμό ως το διπλάσιο της διαφοράς του κλείστρου μπλοκ [EndPoint] - του ανοίγματος Μπράκτιτ [startPoint]. Διαφορετικά, επιστρέψτε τον αριθμό ως διπλάσια από τη διαφορά του κλείστρου [EndPoint] - ανοίγματος των βραχιόνων [startPoint] + 1. Θα λάβουμε την επιθυμητή απάντηση.

Κώδικας  

Κωδικός C ++ για να απαντήσετε σε ερωτήματα εύρους για το Longest Correct Bracket Sub هيٺين

#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 για την απάντηση ερωτημάτων εύρους για το Longest Correct Subackence

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) χρόνος. Έτσι, η συνολική χρονική πολυπλοκότητα του αλγορίθμου είναι γραμμική.

Βλέπε επίσης
Πύργος του Ανόι

Διαστημική πολυπλοκότητα

O (n) όπου «Ν» είναι το μήκος της συμβολοσειράς. Δεδομένου ότι δημιουργήσαμε δύο πίνακες για την αποθήκευση του βραχίονα ανοίγματος και τον αριθμό των αγκυλών κλεισίματος. Η πολυπλοκότητα του διαστήματος είναι γραμμική.