N-ci qovşağı siyahının sonundan çıxarın Leetcode Həll

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon American Express alma Bloomberg Facebook google microsoft PayPal Über
Bağlı siyahı Walmart Qlobal texnologiyaBaxılıb 74

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

N-ci nodu Siyahının Sonundan Sil Leetcode Həlli – sizə əlaqələndirilmiş siyahının başlığının verildiyini və bu siyahının sonundan n-ci qovşağı silməyiniz lazım olduğunu bildirir.

Bu nodu sildikdən sonra dəyişdirilmiş siyahının başını qaytarın.

Misal:

N-ci qovşağı siyahının sonundan çıxarın Leetcode HəllPin

N-ci qovşağı siyahının sonundan çıxarın Leetcode HəllPin

Pin

Pin

Pin

Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]

Explanation:

Input: head = [1], n = 1
Output: []

Explanation:

  • Siyahının son nodeunu silməliyik.
  • Düyünü çıxardıqdan sonra boş bir siyahımız var.

Yanaşma

Idea:

  1. Bu problemi həll etmək üçün əsas fikir istifadə etməkdir üç dəyişən node ünvanlarını saxlayan.
    • qarağat = O, əlaqəli siyahıda təkrarlamaq üçün istifadə olunan cari node ünvanını saxlayacaq.
    • Başlamaq = O, silinəcək qovşağın ünvanını saxlayacaq (siyahının sonundan n-ci node).
    • prev = O, qovşağın başlanğıcının əvvəlki qovşağının ünvanını saxlayacaq.
  2. Qeyd edək ki, silinən qovşaq və başlıq arasındakı məsafə əlaqəli siyahı is mn və qovşağın silinməsi ilə əlaqəli siyahının sonu arasındakı məsafə n-dir, burada m = əlaqəli siyahının uzunluğu.
  3. Yuxarıdakı müşahidə bunu deməyə əsas verir curr dəyişənini əlaqəli siyahının başından başlayınəlaqəli siyahıda irəlilədikcə hər dəfə n-i azaldın. Bizdə olan kimi n qeyri-müsbət qiymət kimi, başlanğıc dəyişənini əlaqəli siyahının başının ünvanı ilə işə salın və n qeyri-müsbət olduqda hər dəfə başlanğıc dəyişənini, eləcə də əvvəlki dəyişəni artırın.
  4. Addım 3 səmərəli işləyir, çünki n qeyri-müsbət olduqdan sonra curr dəyişəninin əhatə etdiyi məsafə nə olursa olsun, əlaqəli siyahının başından başlanğıc dəyişəninin əhatə etdiyi məsafəyə bərabər olacaqdır. mn. Beləliklə, başlanğıc dəyişənində saxlanılan son ünvandan n-ci node ilə yekunlaşacağıq.
  5. Başlanğıc dəyişənində olan qovşağı silin, əvvəlki növbəti node ünvanını başlanğıc növbəti ünvan kimi təyin etməklə.
  6. Daha yaxşı başa düşmək üçün kodu yoxlayın.

 

Kodu

N-ci nodu siyahının sonundan çıxarın Leetcode C++ Həlli:

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *prev = nullptr,*curr = head,*start = nullptr;
        while(curr!=nullptr){
            n--;
            curr = curr->next;
            if(n<=0){
                if(start==nullptr){
                    start = head;
                }
                else{
                    prev = start;
                    start = start->next;
                }
            }
        }
        if(prev==nullptr){
            return start->next;
        }
        prev->next = start->next;
        return head;
    }
};

N-ci qovşağı siyahının sonundan çıxarın Leetcode Java Həlli:

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode curr = head;
        ListNode prev = null;
        ListNode start = null;
        while(curr!=null){
            n = n - 1;
            curr = curr.next;
            if(n<=0){
                if(start==null){
                    start = head;
                }
                else{
                    prev = start;
                    start = start.next;
                }
            }
        }
        if(prev==null){
            return start.next;
        }
        prev.next = start.next;
        return head;
    }
}

Siyahının sonundan N-ci qovşağın çıxarılması üçü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 (N), burada N = əlaqəli siyahının uzunluğu, çünki biz bütün əlaqəli siyahı üçün bir dəfə təkrar edirik.

Kosmik Mürəkkəblik

Yuxarıdakı kodun kosmik mürəkkəbliyi O (1) çünki biz daimi əlavə yerdən istifadə edirik.

arayış https://en.wikipedia.org/wiki/Linked_list

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