နှစ် ဦး ခွဲခြားစာရင်း Leetcode ဖြေရှင်းချက်ပေါင်းစည်း


ခက်ခဲအဆင့် လွယ်ကူသော
မကြာခဏမေးတယ် Adobe က အမေဇုံ Apple ဘလွန်းဘာ့ဂ် Capital One Facebook က Google IBM က Microsoft က Oracle က
ချိတ်ဆက်စာရင်း

ချိတ်ဆက်စာရင်းများ အတော်လေးသူတို့ရဲ့ linear ဂုဏ်သတ္တိများအတွက် Array ကိုကဲ့သို့ဖြစ်ကြ၏။ စုစုပေါင်းခွဲထားသောခင်းကျင်းမှုတစ်ခုကိုဖွဲ့စည်းရန်အတွက်နှစ်မျိုးခွဲခြားထားသည့် Array ကိုပေါင်းစည်းနိုင်သည်။ ဤပြproblemနာတွင်ကျွန်ုပ်တို့သည်နှစ် ဦး ခွဲထားသောဆက်စပ်စာရင်းနှစ်ခုကိုပေါင်းစည်းရမည် အရပျ၌ နှစ်ခုလုံးစာရင်း၏ဒြပ်စင်တစ်ခုစီထားသောဖက်ရှင်အတွက်ပါရှိသောစာရင်းအသစ်ပြန်သွားဖို့။

နမူနာ

နှစ် ဦး ခွဲခြားစာရင်း Leetcode ဖြေရှင်းချက်ပေါင်းစည်း

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

ချဉ်းကပ်နည်း

ထိုသို့ပြုရန်အရိုးရှင်းဆုံးနည်းမှာအသုံးပြုခြင်းဖြစ်သည် two-pointer နည်းပညာ။ စာရင်းအသစ်တခုကိုဖန်တီးပါ။ သေးငယ်တဲ့ element တွေကို pointers နှစ်ခုကြားမှာထည့်ပြီးသက်ဆိုင်ရာ pointer ကိုတိုးပါ။ ၎င်းသည်ကောင်းမွန်သောချဉ်းကပ်မှုတစ်ခုဖြစ်သည်။ သို့သော်နေရာထပ်ဖြည့်သောအပိုစာရင်းတစ်ခုလိုအပ်သည်။

Optimal Approach သည်လုပ်ရန်အတွက်စဉ်ဆက်မပြတ်နေရာတစ်ခုကိုလောင်စေသင့်သည် နေရာ မျိုး။ ကျနော်တို့ကြားမှာချဉ်းကပ်နည်းကိုလိုက်နာနိုင်ပါတယ်။ စာရင်းနှစ်ခုလုံးတွင် node များသိမ်းထားပြီးဖြစ်သည်။ list pointer အသစ်တစ်ခုကို၎င်း၊လာမည့်ထောက်ပြ"မှတ်ဉာဏ်ထဲမှာကြိုတင်သတ်မှတ်ထားသော node များညွှန်ပြသင့်ပါတယ်။ ဤလုပ်ငန်းစဉ်တွင်ကျွန်ုပ်တို့ဖန်တီးသည် အဘယ်သူမျှမ node အသစ်များ။

Algorithm (နုံချဉ်းကပ်နည်း)

  1. function တစ်ခုဖန်တီးပါ mergeTwoSortedLists () ကြောင်းအငြင်းပွားမှုများအဖြစ်နှစ်ခုစာရင်းထောက်ပြသည်
  2. စာရင်းတစ်ခုခုကိုဖြစ်ပါတယ်လျှင် null အခြားတစ်ခုသို့ပြန်သွားပါ
  3. တစ်ဦး Create အပူချိန် နှစ်ခုလုံးစာရင်း၏ခေါင်းများအကြားသေးငယ် node ကိုညွှန်ပြလိမ့်မည်ဟု variable ကို
  4. အနည်းဆုံးတော့ကျွန်ုပ်တို့၏ရလဒ်တွင်အနည်းဆုံး node တစ်ခုကိုထည့်သွင်းထားသဖြင့်ခေါင်းတစ်လုံးတိုးရမည်
  5. ၎င်းသည် subproblem ကိုဖန်တီးသည်။ ဒါကြောင့်တူညီတဲ့ recursive function ကိုခေါ်ပြီး၎င်းကို temp သို့ထည့်ပါ
  6. List1.value <List2.value လျှင်
    • temp = ListNode အသစ် (List1.value) , Temp-> လာမယ့် = mergeTwoSortedLists (List1-> နောက်၊ List2)
  7. List2.value <= List1.value လျှင်
    • temp = ListNode အသစ် (List2.value) , Temp-> လာမယ့် = mergeTwoSortedLists (List1, List2-> next)
  8. ပြန်လာ အပူချိန် လိုချင်သောစာရင်းရရန်

Algorithm (အကောင်းဆုံး)

  1. ခေါ်လိမ့်မည်သည့်စာရင်း pointer အသစ်တစ်ခုကိုဖန်တီးပါ ကဗျာ။
  2. ၎င်း၏ထိန်းသိမ်းရန်preheadကျွန်တော်တို့စာရင်းကိုဝင်ရောက်နိုင်အောင်” (pointer copy) ဦးခေါင်း လိပ်စာ။
  3. အဆိုပါ "လာမည့်ထောက်ပြ"dummy_head ၏" ကိုစာရင်းထဲတွင်ကြိုတင်သတ်မှတ်ထားသော node များညွှန်ပြသောထိုကဲ့သို့သောလမ်းအတွက်ကြိုးကိုင်ရပါမည် l1 နှင့် l2.
  4. အထက်ပါတာဝန်များကိုအောက်ပါနည်းလမ်းများဖြင့်ကျွန်ုပ်တို့ပြုလုပ်နိုင်သည်။
    • စာရင်းများကိုသူတို့၏ခေါင်းများမှစတင်သောအမှတ်အသားများဖြင့်တည့်တည့်ဆက်ထားပါ။
    • စာရင်းတစ်ခုမှလုံးဝကိုမကျော်ဖြတ်ပါက:
      • list point နှစ်ခုမှတန်ဖိုးနည်း node ကိုထပ်ထည့်ပါ dummy_head, သက်ဆိုင်ရာ pointer ကိုတိုး။
    • အခုတော့ထောက်ပြအနည်းဆုံးဖြစ်ပါတယ် null ။ ဒီတော့ append non-null အဆိုပါ Dummy ခေါင်းကိုစာရင်းပြုစုပါ။
  5. ပြန်လာ ဦးခေါင်း အဆိုပါ Dummy စာရင်း၏။

အကောင်အထည်ဖော်ရေး

နှစ်မျိုးခွဲထားသောစာရင်းနှစ်ခုကိုပေါင်းစည်းရန် C ++ အစီအစဉ်

နုံချဉ်းကပ်နည်း

#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;
}

အကောင်းဆုံးနည်းလမ်း

#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

Sorted Lists နှစ်ခုကိုပေါင်းစည်းရန် Java Program

နုံချဉ်းကပ်နည်း

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));
    }
}

အကောင်းဆုံးနည်းလမ်း

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

ရှုပ်ထွေးဆန်းစစ်ခြင်း

အချိန်ရှုပ်ထွေး နှစ် ဦး ခွဲခြားစာရင်းပေါင်းစည်းရန်

အို (N + M)၊ ဘယ်မှာ N နှင့် M နှစ်ခုစာရင်းများ၏အရှည်ဖြစ်ကြသည်။ ကျနော်တို့နှစ် ဦး စလုံးချဉ်းကပ်မှုအတွက်တစ်ကြိမ်စာရင်းနှစ်ခုလုံးဖြတ်သန်း, ဒါကြောင့် algorithms နှစ် ဦး စလုံး linear ဖြစ်ကြသည်။

အာကာသရှုပ်ထွေးမှု နှစ် ဦး ခွဲခြားစာရင်းပေါင်းစည်းရန်

အကောင်းဆုံးချဉ်းကပ်မှုတွင်နားလည်ရန်အရေးကြီးသည် အဆိုပါထောက်ပြ manipulate။ ဒီတော့ variable များအတွက်အမြဲတမ်းနေရာဟာ memory memory ကိုသုံးတယ်။ ထို့ကြောင့်အကောင်းဆုံးနည်းလမ်းမှာအာကာသရှုပ်ထွေးမှုရှိသည် အို (၁). အို (N + M) အာကာသကိုဆွေးနွေးထားတဲ့နုံချဉ်းကပ်မှုတွင်အသုံးပြုသည်။