ပေးထားသောအဖွင့်အပိတ်ကွင်းအတွက်အပိတ်အပိတ်၏အညွှန်းကိုဖော်ပြပါ


ခက်ခဲအဆင့် လွယ်ကူသော
မကြာခဏမေးတယ် Adobe က အမေဇုံ Flipkart Oracle က OYO အခန်းများ Snapdeal Walmart ဓာတ်ခွဲခန်းများ ရတနာ
အခင်းအကျင်း စုပုံထား ကြိုး

ပြProbleနာဖော်ပြချက်

ပေးထားသော ကြိုး s / length နှင့် s ၏တန်ဖိုးနှင့်အဖွင့်စတုရန်းကွင်းခတ်၏ညွှန်းကိန်းကိုကိုယ်စားပြုသည့်ကိန်းတစ်ခု။ ပေးထားသောအဖွင့်အပိတ်ကွင်းအတွက်အပိတ်အပိတ်၏အညွှန်းကိုဖော်ပြပါ။

ပေးထားသောအဖွင့်အပိတ်ကွင်းအတွက်အပိတ်အပိတ်၏အညွှန်းကိုဖော်ပြပါ

နမူနာ

s = "[ABC[23]][89]"

index = 0
8
s = "[C-[D]]"

index = 3
5
s = "E-[FX]]"

index = 0
-1

ချဉ်းကပ်နည်း

တစ်ဦးကိုသုံးပါ စုပုံထား ၏ဒေတာဖွဲ့စည်းပုံ ကိန်း ပေးထားသော string ကိုဖွင့်ကွင်းခတ်၏အညွှန်းကိုသိမ်းဆည်းရန်ရိုက်ပါ။ ပေးထားသောမှတဆင့်ကြားမှာစတင်ပါ ကြိုး ပေးထားသောအညွှန်းကိန်းကနေစတင်။ ဖွင့်လှစ် bracket ကကြုံတွေ့လျှင် stack ထဲမှာတွန်း။ ကြုံတွေ့ရသောပိတ်ပွဲကွင်းဆက်တိုင်းအတွက် stack မှအဖွင့်အပိတ်ကွင်းတစ်ခုပေါ်လာပါ။ အကယ်၍ stack သည်အချည်းနှီးဖြစ်နေပါကဆိုလိုသည်မှာ stack ၏အရွယ်အစားသည်အချို့သောညွှန်းကိန်းများတွင် ၀ ဖြစ်သည်။ index ကို print ထုတ်ပါ။ ကျန်ပုံနှိပ် -0 ။

algorithm

  1. အရှည် / အရွယ်အစားတစ်ခု string ကို s ကိုအစပြု n နှင့်အဖွင့်စတုရန်းကွင်းခတ်၏အညွှန်းကိန်းကိုကိုယ်စားပြုတစ်ခုကိန်းတန်ဖိုး။
  2. ပေးထားသော string တွင်ပေးထားသောအဖွင့် bracket အဘို့အပိတ် bracket ၏အညွှန်းကိန်းကိုရှာရန် function ကိုဖန်တီးပါ။ ၎င်းသည် expression ကိုဖော်ပြသည့် string value နှင့် parameter တစ်ခုအနေဖြင့်ပေးထားသော string ထဲတွင်ဖွင့်နေသော bracket ၏အညွှန်းကိုကိုယ်စားပြုသည့် integer တန်ဖိုးဖြစ်သည်။
  3. ပေးထားသောအညွှန်းကိန်းရှိအက္ခရာသည်ဖွင့်ထားသောကွင်းခတ်နှင့်မတူကိုစစ်ဆေးပါ (ဆိုလိုသည်မှာ '[', print -1, and return) ။
  4. ထိုနောက်ပေးထားသော string ၏အဖွင့်အပိတ်၏အညွှန်းကိုသိမ်းဆည်းရန် integer အမျိုးအစား၏ stack ဒေတာဖွဲ့စည်းပုံကိုဖန်တီးပါ။
  5. ပေးထားသောအညွှန်းကိန်းမှစတင်သောပေးထားသော string ကို ဖြတ်၍ string အတွင်းရှိလက်ရှိအညွှန်းကိန်းသည်အဖွင့်ကွင်းခတ်နှင့်တူညီမှုရှိမရှိစစ်ဆေးပါ၊ stack အတွင်းရှိလက်ရှိအညွှန်းကိန်းရှိစာလုံးကိုတွန်းသွင်း / ထည့်ပါ။
  6. သို့မဟုတ်ပါက string အတွင်းရှိလက်ရှိအညွှန်းကိန်း၏အက္ခရာသည်အပိတ်ပိတ်ထားသောကွင်းခတ်နှင့်ညီလျှင်ဆိုလိုသည်မှာ stack ၏ထိပ်ရှိ element ကို pop / ဖယ်ရှားပါ။ ထိုနောက် stack ဗလာဟုတ်မဟုတ်စစ်ဆေးသည်။ stack အရွယ်အစားသည် 0 နှင့်ညီသည်၊ လက်ရှိအညွှန်းကိုပြန်ရိုက်ပါ။
  7. ပုံနှိပ် -1 ။

ကုဒ်

ဖွင့်လှစ် bracket ကများအတွက်သက်ဆိုင်ရာပိတ်ပွဲ bracket ကရှာဖွေ C ++ အစီအစဉ်

#include <bits/stdc++.h> 
using namespace std; 
  
void test(string expression, int index){ 
    int i; 
      
    if(expression[index]!='['){ 
        cout << "-1\n"; 
        return; 
    } 
      
    stack <int> st; 
      
    for(i = index; i < expression.length(); i++){ 
          
        if(expression[i] == '['){ 
            st.push(expression[i]);
        }
          
        else if(expression[i] == ']'){ 
            st.pop(); 
            if(st.empty()){ 
                cout << i << "\n"; 
                return; 
            } 
        } 
    } 
      
    cout << "-1\n"; 
} 
  
int main() { 
    string s = "[ABC[23]][89]";
    int index = 0;
    
    test(s, index); 
    
    return 0; 
}
8

ဖွင့်လှစ် bracket ကိုများအတွက်သက်ဆိုင်ရာပိတ်ပွဲ bracket ကရှာဖွေ Java ပရိုဂရမ်

import java.util.Stack; 

class FindIndex{ 
  
    static void test(String expression, int index){ 
        int i; 
  
        if(expression.charAt(index) != '['){ 
            System.out.print("-1\n"); 
            return; 
        } 
  
        Stack<Integer> st = new Stack<>(); 
  
        for(i = index; i < expression.length(); i++){ 
  
            if(expression.charAt(i) == '['){ 
                st.push((int) expression.charAt(i)); 
            } 
            
            else if(expression.charAt(i) == ']'){ 
                st.pop(); 
                if(st.empty()){ 
                    System.out.print( i ); 
                    return; 
                } 
            } 
        } 
  
        System.out.print("-1\n"); 
    } 
  
    public static void main(String[] args){
        String s = "[ABC[23]][89]";
        int index = 0;
        
        test(s, index); 
    } 
}
8

ရှုပ်ထွေးဆန်းစစ်ခြင်း

အချိန်ရှုပ်ထွေး

အို (n) ဘယ်မှာ n ပေးထားသော string ကို s ရဲ့အရှည်သည်။ ကျွန်ုပ်တို့သည် string ရှိရရှိနိုင်သည့်စာလုံးများအားလုံးကိုဖြတ်ကျော်သွားသောကြောင့်အချိန်ရှုပ်ထွေးမှုမှာ linear ဖြစ်သည်။

အာကာသရှုပ်ထွေးမှု

အို ()) ကျွန်ုပ်တို့သည်ပေးထားသော string ၏အက္ခရာများကိုသိမ်းဆည်းရန်နေရာလွတ်ကိုသုံးသောကြောင့်ဖြစ်သည်။ နေရာရှုပ်ထွေးမှုသည်ကွင်းခတ်အရေအတွက်ပေါ်မူတည်သည်။ ဒါပေမယ့်အဆိုးဆုံးကတော့ဇာတ်ကောင်အားလုံးဟာစတုရန်းကွင်းခတ်ထားနိုင်ပါတယ်။ ထို့ကြောင့်အာကာသရှုပ်ထွေးမှုသည်လည်း linear ဖြစ်သည်။

ကိုးကား