Etibarlı Mötərizələr LeetCode Həlli

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Çiy kərpic Amazon alma Çovğun Bloomberg ByteDance Expedia Facebook Goldman Sachs google IBM lyft microsoft Kahin Spotify Zillow
BufferedOutputStream SimBaxılıb 196

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:

  1. Açıq mötərizələr eyni tip mötərizələrlə bağlanmalıdır.
    • ()
    • []
    • {}
  2. Açıq mötərizələr düzgün qaydada bağlanmalıdır.
    • ()][ etibarlı deyil
    • () {[]} etibarlıdır
    • [() {}] etibarlıdır

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

  1. Bir yığını S elan edin və başlatın.
  2. İ-də 0-dan n-ə qədər bir döngə işlədin.
    1. Str [i] bir açılış mötərizəsidirsə, str [i] -i yığında itələyin.
    2. 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.
  3. 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.

Etibarlı Mötərizələr LeetCode HəlliPin

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.

Etibarlı parantezlərPin

 

4 Adım: açma mötərizəsini alırıq (dolayısı ilə itələyin (yığında).

Pin

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).

 

Etibarlı parantezlərPin
Etibarlı parantezlər

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 LeetCode HəlliPin

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

References

Crack Sistemi Dizayn Müsahibələri
Translate »
1