Artan Əməliyyat Leetcode Həlli ilə Stack dizayn edin

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon google microsoft Sprinklr
Geyim Layihə Qalaq tiktokBaxılıb 81

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 Artan əməliyyat Leetcode həlli ilə bir yığın dizayn edin -  aşağıdakı əməliyyatları səmərəli şəkildə dəstəkləyən bir yığın dizayn etməyimiz lazım olduğunu bildirir.

  • Maksimum tutumu təyin edin qalaq.
  • Yığın ölçüsü yığının maksimum tutumundan ciddi şəkildə azdırsa, təkan əməliyyatını səmərəli şəkildə yerinə yetirin.
  • Yığın boş deyilsə, pop əməliyyatını səmərəli şəkildə yerinə yetirin və açılan elementi qaytarın.
  • Artırma əməliyyatını yığının ilk k elementinə yerinə yetirin.

Artan Əməliyyat Leetcode Həlli ilə Stack dizayn edinPin

Misal:

Input: ["CustomStack","push","push","pop","push","push","push","increment","increment","pop","pop","pop","pop"]
[[3],[1],[2],[],[2],[3],[4],[5,100],[2,100],[],[],[],[]]
Output: [null,null,null,2,null,null,null,null,null,103,202,201,-1]

Explanation:

  • Maksimum tutumu 3 olan yığını işə salın.
  • 1 dəyəri olan elementi itələyin, yığın = [1].
  • 2 dəyəri olan elementi itələyin, yığın = [1,2].
  • elementi yığından çıxarın, yığın = [1]. Çıxış: 2.
  • 2 dəyəri olan elementi itələyin, yığın = [1,2].
  • 3 dəyəri olan elementi itələyin, yığın = [1,2,3].
  • 4 dəyəri olan itə elementi. Stack maksimum tutumuna çatdığından başqa elementi itələyə bilmərik.
  • Aşağı 5 elementi 100 dəyəri ilə artırın, yığın = [101,102,103].
  • Aşağı 2 elementi 100 dəyəri ilə artırın, yığın = [201,202,103].
  • elementi yığından çıxarın, yığın = [201,202]. Çıxış: 103.
  • elementi yığından çıxarın, yığın = [201]. Çıxış: 202.
  • elementi yığından çıxarın, yığın = []. Nəticə: 201.
  • elementi yığından çıxarın. Yığın boş olduğundan, çıxış: -1.

Yanaşma

Idea:

  1. Bu problemi səmərəli şəkildə həll etmək üçün əsas fikir saxlamaqdır bir sıra ölçüləri maksimuma bərabərdir yığının tutumu.
  2. İndeks dəyişənini qoruyun Bu indeks-1 elementlərini ifadə edəcək elementlər artıq yığına itələnmişdir və yeni element indeksə bərabər mövqedə itələnəcəkdir.
  3. Təkan əməliyyatı üçün, indeks yığının maksimum tutumundan az və ya ona bərabər olduqda element yığına itələnəcək.
  4. Pop əməliyyatı üçün, element yalnız yığın boş deyilsə çıxarılacaq.
  5. Artırma əməliyyatı üçün, yığının ilk k elementini verilmiş qiymətlə artırmalıyıq. Beləliklə, biz təkrarlayacağıq və bütün bu elementləri verilmiş dəyərlə artıracağıq. Yığında k elementdən azdırsa, yığının bütün elementlərini artırmalıyıq.

Kodu

Artan əməliyyat Leetcode C++ həlli ilə stek dizayn edin:

class CustomStack {
public:
    vector<int> st;
    int index,maxCapacity;
    CustomStack(int maxSize) {
        index = 0;
        maxCapacity = maxSize;
        st.assign(maxSize+1,0);
    }    
    void push(int x) {
        if(index!=maxCapacity){
            st[++index] = x;
        }
    }    
    int pop() {
        if(!index){
            return -1;
        }
        return st[index--];
    }    
    void increment(int k, int val) {
        for(int i=1;i<=k && i<=index;i++){
            st[i] += val;
        }
    }
};

Artan əməliyyat Leetcode Java Həlli ilə Stack dizayn edin:

class CustomStack {
    int[] st;
    int index,maxCapacity;
    public CustomStack(int maxSize) {
        index = 0;
        maxCapacity = maxSize;
        st = new int[maxSize+1];      
    }
    public void push(int x) {
        if(index!=maxCapacity){
            st[++index] = x;
        }
    }
    public int pop() {
        if(index==0){
            return -1;
        }
        return st[index--];
    }
    public void increment(int k, int val) {
        for(int i=1;i<=k && i<=index;i++){
            st[i] += val;
        }
    }
}

Artan Əməliyyat Leetcode Həlli ilə Yığın Dizaynı üçün Mürəkkəblik Təhlili

Zamanın mürəkkəbliyi

Yuxarıdakı kodun zaman mürəkkəbliyi O (maksimum Ölçü) çünki ən pis halda k yığının maksimum tutumuna bərabərdir.

Kosmik Mürəkkəblik

Yuxarıdakı kodun kosmik mürəkkəbliyi O (maksimum Ölçü) çünki biz yığının maksimum tutumuna bərabər ölçülər massivini saxlayırıq.

Referans: https://en.wikipedia.org/wiki/Stack_(abstract_data_type)

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