İki Sırala Siyahını Leetcode Solutions birləşdirin

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Çiy kərpic Amazon alma Bloomberg Capital One Facebook google IBM microsoft Kahin
alqoritmlər kodlaşdırma müsahibə müsahibə hazırlığı LeetCode LeetCodeSolutions Bağlı siyahıBaxılıb 104

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.

Bağlı siyahılar xətti xüsusiyyətlərinə görə massivlərə bənzəyirlər. Ümumi sıralanmış bir sıra yaratmaq üçün iki sıralanmış massivi birləşdirə bilərik. Bu problemdə, iki sıralanmış əlaqəli siyahını birləşdirməliyik yerində sıralanmış bir şəkildə hər iki siyahının elementlərini ehtiva edən yeni bir siyahı qaytarmaq.

misal

İki Sırala Siyahını Leetcode Solutions birləşdirinPin

L1 = 1   ->   2   ->   9
L2 = 1   ->   3   ->   4
1 1 2 3 4 9

Yanaşma

Bunun ən sadə yolu istifadə etmək olardı iki göstərici texnika. Yeni bir boş siyahı yaradın. Hər iki göstərici arasında daha kiçik elementləri əlavə edin və müvafiq göstəricini artırın. Bu yaxşı bir yanaşmadır, ancaq yer yeyən əlavə bir siyahının yaradılmasını tələb edir.

Optimal yanaşma yalnız etmək üçün daimi yer istehlak etməlidir yerində çeşidləmə. Təkrarlanan yanaşmanı izləyə bilərik. Artıq hər iki siyahıda da qovşaqlarımız var. Yeni bir siyahı göstəricisi və sonrakı “növbəti göstəricilər”Yaddaşdakı əvvəlcədən təyin edilmiş qovşaqlara işarə etməlidir. Bu müddətdə biz yaratırıq No. yeni qovşaqlar.

Alqoritm (sadəlövh yanaşma)

  1. Bir funksiya yaradın mergeTwoSortedLists () arqument olaraq iki siyahı göstəricisini götürür
  2. Siyahılardan biri belədirsə SIFIR, digərini qaytarın
  3. Bir yaradın temp hər iki siyahının başları arasında daha kiçik düyünü göstərəcək dəyişən
  4. İndi ən azı nəticəmizə bir düyün əlavə olunur, buna görə bir baş artırılmalıdır
  5. Bu bir alt problem yaradır. Beləliklə, eyni rekursiv funksiyanı çağırın və tempə əlavə edin
  6. Əgər List1.value <List2.value
    • temp = yeni ListNode (List1.value) , temp-> next = mergeTwoSortedLists (List1-> sonrakı, List2)
  7. List2.value <= List1.value olarsa
    • temp = yeni ListNode (List2.value) , temp-> next = mergeTwoSortedLists (List1, List2-> növbəti)
  8. Qayıtmaq temp istədiyiniz siyahını əldə etmək

Alqoritm (Optimal)

  1. Çağırılacaq yeni bir siyahı göstəricisi yaradın dummy_head
  2. Qorumaq “baş”(Göstəricini kopyalayın) ki, siyahıya daxil ola bilək baş ünvanı.
  3. The "növbəti göstəricilər”Dummy_head, elə bir şəkildə idarə olunmalıdır ki, siyahılardakı əvvəlcədən təyin olunmuş qovşaqlara işarə etsin l1l2.
  4. Yuxarıdakı tapşırığı aşağıdakı yollarla edə bilərik:
    • Siyahıları başlarından başlayan göstəricilərlə təkrarlamağa davam edin.
    • Siyahılardan biri tamamilə keçilmədikdə:
      • İki siyahı göstəricisindən daha kiçik dəyərli düyünü əlavə edin dummy_head, müvafiq göstəricini artırmaq.
    • İndi göstəricilərdən ən azı biri SIFIR. Beləliklə, əlavə edin boş deyil saxta baş üçün siyahı.
  5. Qayıt baş saxta siyahının.

Həyata keçirilməsi

İki Sırala Siyahını Birləşdirmək üçün C ++ Proqramı

Sadəlövh yanaşma

#include <bits/stdc++.h>
using namespace std;

struct listNode
{
    int value;
    listNode* next;

    listNode(int x)
    {
        value = x;
        next = NULL;
    }
};

listNode* mergeTwoSortedLists(listNode* l1 , listNode* l2)
{
    if(!l1)
        return l2;
    if(!l2)
        return l1;

    listNode* temp;
    if(l1->value < l2->value)
    {
        temp = new listNode(l1->value);
        temp->next = mergeTwoSortedLists(l1->next , l2);
    }
    else
    {
        temp = new listNode(l2->value);
        temp->next = mergeTwoSortedLists(l1 , l2->next);
    }

    return temp;
}


void print(listNode* head)
{
    while(head)
    {
        cout << head->value << " ";
        head = head->next;
    }
    cout << '\n';
    return;
}


int main()
{
    listNode* l1 = new listNode(1);
    l1->next = new listNode(2);
    l1->next->next = new listNode(9);

    listNode* l2 = new listNode(1);
    l2->next = new listNode(3);
    l2->next->next = new listNode(4);

    print(mergeTwoSortedLists(l1 , l2));
    return 0;
}

Optimal metod

#include <bits/stdc++.h>
using namespace std;

struct listNode
{
    int value;
    listNode* next;

    listNode(int x)
    {
        value = x;
        next = NULL;
    }
};


listNode* mergeTwoSortedLists(listNode* l1 , listNode* l2)
{
    listNode *dummy_head = new listNode(-1) , *prehead = dummy_head;
    while(l1 && l2)
    {
        if(l1->value < l2->value)
        {
            dummy_head->next = l1;
            l1 = l1->next;
        }
        else
        {
            dummy_head->next = l2;
            l2 = l2->next;
        }
        dummy_head = dummy_head->next;
    }

    dummy_head->next = (l1 ? l1 : l2);
    return prehead->next;
}



void print(listNode* head)
{
    while(head)
    {
        cout << head->value << " ";
        head = head->next;
    }
    cout << '\n';
    return;
}


int main()
{
    listNode* l1 = new listNode(1);
    l1->next = new listNode(2);
    l1->next->next = new listNode(9);

    listNode* l2 = new listNode(1);
    l2->next = new listNode(3);
    l2->next->next = new listNode(4);

    print(mergeTwoSortedLists(l1 , l2));
    return 0;
}
1 1 2 3 4 9

İki Sırala Siyahını Birləşdirmək üçün Java Proqramı

Sadəlövh yanaşma

class listNode
{
    int value;
    listNode next;

    listNode(int x)
    {
        value = x;
        next = null;
    }
}

class merge_two_sorted_lists
{
    public static void print(listNode head)
    {
        while(head != null)
        {
            System.out.print(head.value + " ");
            head = head.next;
        }
        return;
    }


    public static listNode mergeTwoSortedLists(listNode l1 , listNode l2)
    {
        if(l1 == null)
            return l2;
        if(l2 == null)
            return l1;

        listNode temp;
        if(l1.value < l2.value)
        {
            temp = new listNode(l1.value);
            temp.next = mergeTwoSortedLists(l1.next , l2);
        }
        else
        {
            temp = new listNode(l2.value);
            temp.next = mergeTwoSortedLists(l1 , l2.next);
        }

        return temp;
    }

    public static void main(String args[])
    {
        listNode l1 = new listNode(1);
        l1.next = new listNode(2);
        l1.next.next = new listNode(9);

        listNode l2 = new listNode(1);
        l2.next = new listNode(3);
        l2.next.next = new listNode(4);

        print(mergeTwoSortedLists(l1 , l2));
    }
}

Optimal metod

class listNode
{
    int value;
    listNode next;

    listNode(int x)
    {
        value = x;
        next = null;
    }
}

class merge_two_sorted_lists
{
    public static void print(listNode head)
    {
        while(head != null)
        {
            System.out.print(head.value + " ");
            head = head.next;
        }
        return;
    }


    public static listNode mergeTwoSortedLists(listNode l1 , listNode l2)
    {
        listNode dummy_head = new listNode(-1) , prehead = dummy_head;
        while(l1 != null && l2 != null)
        {
            if(l1.value < l2.value)
            {
                dummy_head.next = l1;
                l1 = l1.next;
            }
            else
            {
                dummy_head.next = l2;
                l2 = l2.next;
            }
            dummy_head = dummy_head.next;
        }

        dummy_head.next = ((l1 != null) ? l1 : l2);
        return prehead.next;
    }

    public static void main(String args[])
    {
        listNode l1 = new listNode(1);
        l1.next = new listNode(2);
        l1.next.next = new listNode(9);

        listNode l2 = new listNode(1);
        l2.next = new listNode(3);
        l2.next.next = new listNode(4);

        print(mergeTwoSortedLists(l1 , l2));
    }
}
1 1 2 3 4 9

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi İki Sırala Siyahını Birləşdirmək

O (N + M), hara NM iki siyahının uzunluqlarıdır. Hər iki yanaşmada hər iki siyahıdan bir dəfə keçirik, buna görə hər iki alqoritm xətti olur.

Kosmik Mürəkkəblik İki Sırala Siyahını Birləşdirmək

Optimal yanaşmada yalnız bizim olduğumuzu anlamaq vacibdir göstəriciləri idarə etmək. Beləliklə, dəyişənlər üçün sabit yer yaddaş istifadəsini hesablayır. Buna görə də optimal metodun bir kosmik mürəkkəbliyi vardır O (1). O (N + M) məkan müzakirə edilən sadəlövh yanaşmada istifadə olunur.

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