Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.
In Etibarlı parantezlər Verdiyimiz LeetCode problemi sim yalnız '(', ')', '{', '}', '[' və ']' simvollarını ehtiva edən daxiletmə sətirinin etibarlı olub olmadığını müəyyənləşdirin. Burada biz sizə Etibarlı Mötərizələr LeetCode Həllini təqdim edəcəyik.
Giriş sətri aşağıdakı hallarda etibarlıdır:
- Açıq mötərizələr eyni tip mötərizələrlə bağlanmalıdır.
- ()
- []
- {}
- Açıq mötərizələr düzgün qaydada bağlanmalıdır.
- ()][ etibarlı deyil
- () {[]} etibarlıdır
- [() {}] etibarlıdır
Mündəricat
misal
Input: str = “[] {() ()}”
Buraxılış: Verilən sətirdə mötərizələr var.
Düzgün parantezlər üçün alqoritm
n: simli uzunluq
str: giriş sətri
- Bir yığını S elan edin və başlatın.
- İ-də 0-dan n-ə qədər bir döngə işlədin.
- Str [i] bir açılış mötərizəsidirsə, str [i] -i yığında itələyin.
- Str [i] bağlanma mötərizəsidirsə, iki ehtimal var:
- Yığmada mövcud olan üst mötərizə eyni tipli açılış mötərizəsidirsə, yığının üst elementini açın.
- Başqa, yalan qayıt.
- S. boş () qaytarın.
Addım-addım işləmə prosesi
str = [{} ()]
n = 6
1 Adım: açılış mötərizəsini alırıq [dolayısı ilə itələyin [yığında.
2 Adım: açma mötərizəsini alırıq {, dolayısı ilə yığını itələyin.
3 Adım: bir bağlanma mötərizəsi} və üst hissəsini alırıq qalaq is {, bu səbəbdən yığında pop əməliyyatı etmək.
4 Adım: açma mötərizəsini alırıq (dolayısı ilə itələyin (yığında).
5 Adım: bir bağlama mötərizəsi alırıq) və yığının üst hissəsidir (dolayısı ilə yığında pop əməliyyatı aparırıq).
6 Adım: bir bağlanma mötərizəsi alırıq] və yığının üstü [, deməli yığında pop əməliyyatı edin.
Etibarlı Mötərizələr üçün həyata keçirmə LeetCode Həlli
Düzgün parantezlər üçün C ++ proqramı
#include<bits/stdc++.h>
using namespace std;
bool isValid(string s) {
stack<char> bracket;
for (char& c : s) {
switch (c) {
case '(': bracket.push(c); break;
case '{': bracket.push(c); break;
case '[': bracket.push(c); break;
case ')': if (bracket.empty() || bracket.top()!='(') return false; else bracket.pop(); break;
case '}': if (bracket.empty() || bracket.top()!='{') return false; else bracket.pop(); break;
case ']': if (bracket.empty() || bracket.top()!='[') return false; else bracket.pop(); break;
default: ;
}
}
return bracket.empty() ;
}
int main(){
string s = "[[]{}]()";
bool check = isValid(s);
if(check){
cout<<"The given string contains valid parentheses.";
}
else{
cout<<"The given string contains invalid parentheses.";
}
}
The given string contains valid parentheses.
Düzgün parantezlər üçün JAVA proqramı
import java.util.*;
public class Main
{
public static boolean isValid(String s) {
Stack<Character> bracket = new Stack<>();
for (char c : s.toCharArray()) {
switch (c) {
case '(': bracket.push(c); break;
case '{': bracket.push(c); break;
case '[': bracket.push(c); break;
case ')': if (bracket.empty() || bracket.peek()!='(') return false; else bracket.pop(); break;
case '}': if (bracket.empty() || bracket.peek()!='{') return false; else bracket.pop(); break;
case ']': if (bracket.empty() || bracket.peek()!='[') return false; else bracket.pop(); break;
default: ;
}
}
return bracket.isEmpty();
}
public static void main(String[] args) {
String s = "{}[)(]";
boolean check = isValid(s);
if(check){
System.out.println("The given string contains valid parentheses.");
}
else{
System.out.println("The given string contains invalid parentheses.");
}
}
}
The given string contains invalid parentheses.
Mürəkkəblik
Zaman mürəkkəbliyi
O (n)
burada n verilmiş simli bir dəfə keçdiyimiz üçün verilən simin uzunluğu.
Yığındakı pop (), top () və push () əməliyyatı davamlı vaxt tələb edir.
Kosmik mürəkkəblik
O (n)
Əlavə bir yığın sahəsi istifadə edə bildiyimiz üçün və ən pis halda yığının ölçüsü n / 2 ola bilər
