Mötərizədə Leetcode Həllini yaradın

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Çiy kərpic Amazon alma Bloomberg ByteDance C3 IoT Facebook google Intuit microsoft Kahin Spotify Tesla Über
Geri qayıtma Dinamik proqramlaşdırma Sim Walmart Qlobal texnologiyaBaxılıb 58

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.

Problem bəyanat

The Mötərizələr yaradın LeetCode Həlli - “Yaratmaq Parantezlər” ifadəsi n dəyərinin verildiyini bildirir. Biz n cüt mötərizənin bütün kombinasiyalarını yaratmalıyıq.

Cavabı düzgün qurulmuş mötərizələrin sətirlərinin vektoru şəklində qaytarın.

Misal:

Input:  n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

Explanation:

  • Bütün düzgün formalı mötərizələr bunlardır:- [“((()))”,”(()())”,”(())()”,”()())”,”()() ()”].
Input:  n = 1
Output: ["()"]

Explanation:

  • Bütün düzgün formalı mötərizələr bunlardır:- [“()”].

Yanaşma

Idea:

  1. Bu problemi həll etmək üçün əsas fikir istifadə etməkdir Recursion.
  2. Qəddar qüvvə yanaşması hər bir indeksdə hər növ mötərizəni nəzərdən keçirmək və rekursiyanın növbəti addımına keçmək və bunun düzgün formalaşmış mötərizələrə gətirib çıxarıb-aparmadığını yoxlamaqdır? Əgər Bəli, sətri cavabımız kimi saxlayın, əks halda geri çəkilin.
  3. Effektiv həll üçün boş sətirlə başlayın və n açıq və qapalı mötərizələrin sayı (çünki biz n cüt yaratmalıyıq).
  4. At rekursiyanın hər bir addımı, aşağıdakı hallara aiddir:
    1. Baza işi: Bir sıra açıq və qapalı mötərizələrin hər ikisi olduqda n-ə bərabərdir, cari sətri cavabımız kimi saxlayın.
    2. Açılış mötərizələrinin sayı olduqda ciddi şəkildə azdır n-dən çox, biz indi açıq mötərizəni yerləşdirə bilərik.
    3. Bağlama mötərizələrinin sayı olduqda ciddi şəkildə azdır bağlama mötərizələrinin sayından daha çox, biz indi bağlama mötərizəsini yerləşdirməliyik.
  5. Baza hərfinə çatdıqda, düzgün tərtib edilmiş mötərizələrdən ibarət olan cavabımızda formalaşmış sətri saxlayacağıq.
  6. Bütün düzgün qurulmuş mötərizələri sətir vektoru şəklində cavabımız kimi qaytarın.

Kodu

Mötərizələr yaradın Leetcode C++ Həlli:

class Solution {
public:
    vector<string> ans;
    void recurse(string s,int open,int close,int n){
        if(open==n and close==n){
            ans.push_back(s);
            return;
        }
        if(open<n)
            recurse(s+"(",open+1,close,n);
        if(close<open)
            recurse(s+")",open,close+1,n);
    }
    vector<string> generateParenthesis(int n) {
        recurse("",0,0,n);
        return ans;
    }
};

Mötərizələr yaradın Leetcode Java Həlli:

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> list = new ArrayList<String>();
        backtrack(list, "", 0, 0, n);
        return list;
    }
    public void backtrack(List<String> list, String str, int open, int close, int max){
        if(str.length() == max*2){
            list.add(str);
            return;
        }        
        if(open < max){
            backtrack(list, str+"(", open+1, close, max);
        }
        if(close < open){
            backtrack(list, str+")", open, close+1, max);
        }
    }
}

Mötərizələr yaratmaq üçün mürəkkəblik təhlili Leetcode həlli

Zamanın mürəkkəbliyi

Yuxarıdakı kodun zaman mürəkkəbliyi O(2^(2N)) çünki ən pis halda biz mötərizələrin açılması və bağlanması üçün bütün imkanları nəzərdən keçirməliyik, burada N = formalaşdırmalı olduğumuz cütlərin sayı.

Kosmik Mürəkkəblik

Yuxarıdakı kodun kosmik mürəkkəbliyi O (N). 

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