Minimum Mötərizənin Dönüşü

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

Minimum mötərizənin geri qaytarılması problemində, a verdik sim yalnız '{' və '}' simvollarının ifadəsini ehtiva edən s. Bir ifadəni balanslaşdırmaq üçün lazım olan minimum mötərizənin geri sayını tapın.

Minimum Mötərizənin DönüşüPin

misal

Giriş: s = “} {”

Çıxış: 2

Giriş: s = "{{{"

Çıxış: Verilən ifadə balanslaşdırıla bilməz.

Minimum Bracket Reversals üçün Alqoritm

  1. Yalnız '{' və '}' simvollarının ifadəsini ehtiva edən bir s sətirini işə salın.
  2. Mod 2 sətirinin ölçüsünün 0-a bərabər olmadığını yoxlayın, qayıdır -1.
  3. Başqa bir yaratmaq qalaq məlumatların quruluşu.
  4. Verilmiş sətirdən keçin və sətrin indiki indeksindəki simvolun '}' -ə bərabər olmadığını yoxlayın və ya yığının ölçüsü 0 olduğunu yoxlayın, xananı sətrin indiki indeksindəki işarəni basaraq yoxlayın yığının üstündəki element '{' dir, yığının üst hissəsini açın, əks halda simli yığının içindəki indiki göstəriciyə itələyin.
  5. Tam bir dəyişən yaradın və yığının ölçüsünü orada saxlayın. Mötərizələri saymaq və 0 olaraq başlatmaq üçün bir sayğac dəyişənini yaradın.
  6. Yığın boş olmadığı və yığının üst hissəsindəki element '{' ilə bərabər olduğu zaman keçin, elementi yığının üstündəki yerə qoyun və sayğacı 1 ilə artırın.
  7. Yığının ölçüsünün əvvəllər saxlanıldığı tam ədədi dəyişəni 2-yə bölün və onu 2 saylı dəyişənə əlavə edin. Əlavə etdikdən sonra nəticəni qaytarın.
  8. Qaytarılan dəyərin -1-ə bərabər olub olmadığını yoxlayın, “Verilən ifadə balanslaşdırıla bilməz” yazdırın, əks halda qaytarılmış dəyəri çap edin.

Minimum Bracket Reversals üçün C ++ Proqramı

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

int MinReversals(string s){ 
    int len = s.length(); 
    
    if(len%2){ 
        return -1;
    }
    
    stack<char> st; 
    
    for(int i=0; i<len; i++){ 
        if(s[i]=='}' && !st.empty()){
        
            if(st.top()=='{'){ 
                st.pop(); 
            }
            
            else{
                st.push(s[i]); 
            }
        } 
        else{
            st.push(s[i]); 
        }
    } 
    
    int red_len = st.size(); 
    int n = 0; 
    
    while(!st.empty() && st.top() == '{'){ 
        st.pop(); 
        n++; 
    } 
    
    return (red_len/2 + n%2); 
} 

int main(){ 
    string s = "}}{{"; 
    
    if(MinReversals(s) == -1){
        cout << "The given expression can not be balanced."; 
    }
    else{
        cout << MinReversals(s);
    }
    
    return 0; 
}
2

Minimum Bracket Reversals üçün Java Proqramı

import java.util.Stack; 
  
class countMinReversals{ 
  
    static int MinReversals(String s){ 
        int len = s.length(); 
      
        if(len%2 != 0){ 
            return -1; 
        }
      
        Stack<Character> st = new Stack<>(); 
          
        for(int i=0; i<len; i++){ 
            char c = s.charAt(i); 
            
            if(c =='}' && !st.empty()){ 
                if(st.peek()=='{'){ 
                    st.pop(); 
                }
                else{
                    st.push(c); 
                }
            } 
            else{
                st.push(c);
            }
        } 
      
        int red_len = st.size(); 
        int n = 0; 
        
        while(!st.empty() && st.peek() == '{'){ 
            st.pop(); 
            n++; 
        } 
      
        return(red_len/2 + n%2); 
    } 
      
    public static void main(String[] args){ 
        String s = "}}{{"; 
          
        if(MinReversals(s) == -1){
            System.out.println("The given expression can not be balanced."); 
        }
        else{
            System.out.println(MinReversals(s));
        }  
    } 
  
}
2

Minimum Bracket Reversals üçün Mürəkkəblik Analizi

Zamanın mürəkkəbliyi: O (n), burada n - verilən ifadədəki simvolların sayı.

Kosmik Mürəkkəblik: O (n), çünki n simvol üçün yer istifadə etdik.

References

Translate »