최소 브래킷 반전

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

최소 브래킷 반전 문제에서 우리는 현 '{'및 '}'문자의 표현식 만 포함하는 s. 식의 균형을 맞추는 데 필요한 최소 대괄호 반전 수를 찾으십시오.

핀

예

입력 : s =“} {”

출력: 2

입력 : s =“{{{”

출력: 주어진 표현은 균형을 이룰 수 없습니다.

최소 브래킷 반전을위한 알고리즘

1. '{'및 '}'문자의 표현식 만 포함하는 문자열 s를 초기화하십시오.
2. mod 2 문자열의 크기가 0이 아닌지 확인하고 -1을 반환합니다.
3. 그렇지 않으면 스택 데이터 구조.
4. 주어진 문자열을 순회하고 문자열의 현재 인덱스에있는 문자가 '}'와 같지 않거나 스택의 크기가 0인지 확인하고 스택에있는 문자열의 현재 인덱스에있는 문자를 푸시하고 그렇지 않으면 스택 맨 위에있는 요소는 '{'이고 스택 맨 위를 팝하거나 스택에있는 문자열의 현재 인덱스에있는 문자를 푸시합니다.
5. 정수 변수를 만들고 스택의 크기를 저장합니다. 또한 카운터 변수를 만들어 대괄호를 계산하고 0으로 초기화합니다.
6. 스택이 비어 있지 않고 스택 맨 위에있는 요소가 '{'와 같을 때 트래버스하고 스택 맨 위에있는 요소를 팝하고 카운터를 1 씩 증가시킵니다.
7. 스택의 크기가 미리 저장되어 있던 정수 변수를 2로 나누어 카운터 변수 mod 2에 더합니다. 더한 후 결과를 반환합니다.
8. 반환 된 값이 -1인지 확인하고 "주어진 표현식은 균형을 맞출 수 없습니다"를 인쇄하고 그렇지 않으면 반환 된 값을 인쇄합니다.

최소 브래킷 반전을위한 C ++ 프로그램

#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

최소 브래킷 반전을위한 Java 프로그램

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

최소 브래킷 반전을위한 복잡성 분석

시간 복잡성 : O (n) 여기서 n은 주어진 표현식의 문자 수입니다.

공간 복잡성 : O (n) n 개의 문자에 공백을 사용했기 때문입니다.

참조