Μέγιστο βάθος ένθεσης του Parentheses Leetcode Solution


Επίπεδο δυσκολίας Εύκολος
Συχνές ερωτήσεις Bloomberg
κορδόνι

Δήλωση προβλήματος

Σε αυτό το πρόβλημα, μας παρέχονται έγκυρες παρενθέσεις κορδόνι (vps) με ορισμένους αριθμούς, ορισμένους τελεστές (π.χ. +, -, *) και κάποιες παρενθέσεις (π.χ. '(', ')').
Οι έγκυρες συμβολοσειρές παρενθέσεων (vps) είναι:

  1.  ""
  2. "D" όπου d είναι οποιοσδήποτε αριθμός
  3. "(A)" εάν το A είναι έγκυρη συμβολοσειρά παρενθέσεων
  4. "A * B" εάν * είναι οποιοσδήποτε χειριστής και τα A και B είναι έγκυρα συμβολοσειρά παρενθέσεων.

Στόχος μας είναι να βρούμε το μέγιστο βάθος των παρενθέσεων στη δεδομένη συμβολοσειρά.
e.g. “(1+(2*3)+((8)/4))+1”
μπορούμε να δούμε ότι στον αριθμό 8 βρίσκεται εντός του μέγιστου αριθμού παρενθέσεων και το βάθος παρενθέσεων υπάρχει 3. Θα εξάγουμε 3.

Μέγιστο βάθος ένθεσης του Parentheses Leetcode Solution
Ας δούμε ένα ακόμη παράδειγμα,
e.g. “1+(2*3)/(2-1)”
το vps 2 * 3 ή άλλο vps 2-1, και τα δύο βρίσκονται στο μέγιστο βάθος παρενθέσεων, δηλαδή 1.

Παράδειγμα

s = "(1+(2*3)+((8)/4))+1"
3

Επεξήγηση:

Το ψηφίο 8 βρίσκεται μέσα σε 3 ένθετες παρενθέσεις στη συμβολοσειρά.

s = "(1)+((2))+(((3)))"
3

Προσέγγιση

Μας δίνεται ότι η συμβολοσειρά είναι vps και πρέπει απλώς να μάθουμε το μέγιστο βάθος παρενθέσεων. Έτσι, μπορούμε απλώς να επικεντρωθούμε στις παρενθέσεις και να αγνοήσουμε άλλους χαρακτήρες (αριθμούς και τελεστές).

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

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

Εκτέλεση

Πρόγραμμα C ++ για το μέγιστο βάθος ένθεσης του Parentheses Leetcode Solution

#include <iostream>
using namespace std;

int maxDepth(string s) 
{
    int ans=0,k=0;
    for(int i=0;i<s.length();i++)
    {
        if(s[i]=='(')k++;
        else if(s[i]==')')k--;
        ans=ans>k?ans:k;
    }
    return ans;
}
int main()
{
    cout<<maxDepth("(1)+((2))+(((3)))");
}
3

Πρόγραμμα Java για το μέγιστο βάθος ένθεσης του Parentheses Leetcode Solution

import java.util.*;
import java.lang.*;

class Solution
{  
    public static int maxDepth(String s) 
    {
        int ans=0,k=0;
        for(int i=0;i<s.length();i++)
        {
            if(s.charAt(i)=='(')k++;
            else if(s.charAt(i)==')')k--;
            ans=Math.max(ans,k);
        }
        return ans;
    }
    
    public static void main(String args[])
    {
        System.out.println(maxDepth("(1)+((2))+(((3)))"));
    }
}
3

Ανάλυση πολυπλοκότητας για το μέγιστο βάθος ένθεσης του Parentheses Leetcode Solution

Χρόνος πολυπλοκότητας

Επί): Διασχίζουμε τη δεδομένη έκφραση από αριστερά προς τα δεξιά. Έτσι, είναι O (n) όπου το n είναι μήκος της δεδομένης συμβολοσειράς.

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

O (1): Δεν έχουμε χρησιμοποιήσει σταθερούς επιπλέον χώρους. Έτσι, η πολυπλοκότητα του διαστήματος είναι Ο (1).