Bir simli içəridəki parantezin maksimum dərinliyini tapın

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon Facebook
Qalaq SimBaxılıb 32

Bir s s verilmişdir. Verilən iç içə mötərizənin maksimum dərinliyini yazdırmaq üçün kodu yazın sim.

Bir simli içəridəki parantezin maksimum dərinliyini tapınPin

misal

Giriş: s = "(a (b) (c) (d (e (f) g) h) I (j (k) l) m)")

Çıxış: 4

Giriş: s = "(p ((q)) ((s) t))"

Çıxış: 3

Stack istifadə

Alqoritm

  1. N uzunluğunda bir s sətir başlayın.
  2. Bir yaradın qalaq maksimum dəyəri və cari maksimum dəyərini saxlamaq və dəyərlərini 0 olaraq təyin etmək üçün parantezi və iki dəyişəni saxlamaq.
  3. Sətrdən keçin və cari simvolun açılış mötərizəsi olub olmadığını yoxlayın, yığına itələyin və cari maksimum dəyəri artırın. Cari maksimum dəyər maksimum dəyərdən böyükdürsə, maksimum dəyəri cari maksimum dəyər kimi yeniləyin.
  4. Başqa bir cari xarakter bağlanma mötərizəsidirsə, yığının üst simvolunu açın. Cari maksimum dəyərin 0-dan böyük olduğunu və açılan simvolun açılış mötərizəsi olub olmadığını yoxlayın, cari maksimum dəyəri başqa return -1 -ə endirin.
  5. Yığın boş deyilsə, -1-ə qayıdın.
  6. Başqa bir şey maksimum dəyəri qaytarır.

C ++ Proqramı bir sətirdə iç içə mötərizənin maksimum dərinliyini tapmaq

#include <bits/stdc++.h> 
using namespace std; 

class Stack{  
    public: 
        int top;  
        unsigned capacity;  
        char* array;  
};  
  
Stack* createStack(unsigned capacity){  
    Stack* stack = new Stack(); 
    stack->capacity = capacity;  
    stack->top = -1;  
    stack->array = new char[(stack->capacity * sizeof(char))];  
    return stack;  
}  
  
int isFull(Stack* stack){ 
    return stack->top == stack->capacity - 1; 
}  
  
int isEmpty(Stack* stack){ 
    return stack->top == -1;
}  
  
void push(Stack* stack, char item){  
    if(isFull(stack))  
        return;  
    stack->array[++stack->top] = item;  
}  
  
char pop(Stack* stack){  
    if(isEmpty(stack))  
        return -1;  
    return stack->array[stack->top--];  
}  

int maxDepth(string s){ 
    int n = s.length();  
    Stack* stack = createStack(n);
    int current_max = 0; 
    int max = 0;   
  
    for(int i = 0; i<n; i++){
        
        if(s[i] == '('){ 
            push(stack, s[i]);
            current_max++; 
  
            if(current_max > max){ 
                max = current_max;
            }    
        } 
        
        else if(s[i] == ')'){ 
            char c = pop(stack);
            if((current_max > 0) && (c == '(')){ 
                current_max--; 
            }    
            else{
                return -1;
            }    
        } 
    } 
  
    if(!isEmpty(stack)){ 
        return -1; 
    }    
  
    return max; 
} 
  
int main(){
    
    string s = "( a(b) (c) (d(e(f)g)h) I (j(k)l)m)"; 
    cout<<maxDepth(s); 
    
    return 0; 
}
4

Bir simli iç içə mötərizənin maksimum dərinliyini tapmaq üçün Java Proqramı

import java.util.*; 
  
class Stack{ 
    int size; 
    int top; 
    char[] a;  
  
    boolean isEmpty(){ 
        return(top < 0); 
    } 
      
    Stack(int n){ 
        top = -1; 
        size = n; 
        a = new char[size]; 
    } 
  
    boolean push(char x){ 
        if (top >= size){ 
            System.out.println("Stack Overflow"); 
            return false; 
        } 
        else{ 
            a[++top] = x; 
            return true; 
        } 
    } 
  
    char pop(){ 
        if(top < 0){ 
            System.out.println("Stack Underflow"); 
            return 0; 
        } 
        else{ 
            char x = a[top--]; 
            return x; 
        } 
    } 
}

class Depth{
    
    static int maxDepth(String s){
        
        int current_max = 0;
        int max = 0; 
        int n = s.length(); 
        Stack stack = new Stack(n);
  
        for(int i = 0; i < n; i++){ 
            if(s.charAt(i) == '('){ 
                current_max++; 
                stack.push(s.charAt(i));
  
                if(current_max > max){ 
                    max = current_max; 
                } 
            } 
            else if(s.charAt(i) == ')'){ 
                
                char c = stack.pop();
                
                if((current_max > 0) && (c == '(')){ 
                    current_max--; 
                } 
                else{ 
                    return -1; 
                } 
            } 
        } 
  
        if(!stack.isEmpty()){ 
            return -1; 
        } 
  
        return max; 
    } 
  
    public static void main(String[] args){
        
        String s = "( a(b) (c) (d(e(f)g)h) I (j(k)l)m)"; 
        System.out.println(maxDepth(s)); 
        
    } 
}
4

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi: O (n), burada n simin ölçüsüdür.

Köməkçi məkan: O (n), çünki n işarəsini saxlamaq üçün yığında yer istifadə etdik.

Stack istifadə etmədən

Alqoritm

  1. N uzunluğunda bir s sətir başlayın.
  2. Maksimum dəyəri və cari maksimum dəyərini saxlamaq və dəyərlərini 0 olaraq təyin etmək üçün iki dəyişən yaradın.
  3. Simdən keçin və cari simvolun açılış mötərizəsi olub olmadığını yoxlayın, cari maksimum dəyəri artırın. Cari maksimum dəyər maksimum dəyərdən böyükdürsə, maksimum dəyəri cari maksimum dəyər kimi yeniləyin.
  4. Cari xarakter bağlanma mötərizəsi olarsa, başqa 0-dan çox olarsa cari maksimum dəyəri azaldır.
  5. Cari maksimum dəyər 0-a bərabər deyilsə, -1 qaytarın.
  6. Başqa bir şey maksimum dəyəri qaytarır.

C ++ Proqramı bir sətirdə iç içə mötərizənin maksimum dərinliyini tapmaq

#include <iostream> 
using namespace std; 
  
int maxDepth(string s){ 
    int current_max = 0; 
    int max = 0;   
    int n = s.length(); 
  
    for(int i = 0; i<n; i++){ 
        if(s[i] == '('){ 
            current_max++; 
  
            if(current_max > max){ 
                max = current_max;
            }    
        } 
        else if(s[i] == ')'){ 
            if(current_max > 0){ 
                current_max--; 
            }    
            else{
                return -1;
            }    
        } 
    } 
  
    if(current_max != 0){ 
        return -1; 
    }    
  
    return max; 
} 
  
int main(){
    
    string s = "( a(b) (c) (d(e(f)g)h) I (j(k)l)m)"; 
    cout<<maxDepth(s); 
    
    return 0; 
}
4

Bir simli iç içə mötərizənin maksimum dərinliyini tapmaq üçün Java Proqramı

class Depth{
    
    static int maxDParenthesis(String s){
    
        int currentmax = 0;
        int max = 0; 
        int n = s.length(); 
  
        for(int i = 0; i < n; i++){ 
            if(s.charAt(i) == '('){ 
                currentmax++; 
  
                if(currentmax > max){ 
                    max = currentmax; 
                } 
            } 
            else if(s.charAt(i) == ')'){ 
                if(currentmax > 0){ 
                    currentmax--; 
                } 
                else{ 
                    return -1; 
                } 
            } 
        } 
    
        if(currentmax != 0){ 
            return -1; 
        } 
        
        return max; 
    } 
    
    public static void main(String[] args){
    
        String s = "( a(b) (c) (d(e(f)g)h) I (j(k)l)m)";
        
        System.out.println( maxDParenthesis(s) ); 
    
    } 
}
4

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi: O (n), burada n simin ölçüsüdür.

Köməkçi məkan: O (1), çünki daimi əlavə yer istifadə etdik.

References

Translate »