ຜະສົມຜະສານສອງລາຍການ Leetcode Solutions


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ Adobe Amazon ຈາກຫນາກແອບເປີ Bloomberg Capital One ເຟສບຸກ ກູໂກ IBM Microsoft Oracle
ບັນຊີທີ່ເຊື່ອມໂຍງ

ບັນຊີລາຍຊື່ທີ່ເຊື່ອມໂຍງ ແມ່ນຂ້ອນຂ້າງຄ້າຍຄືຂີໃນຄຸນລັກສະນະເສັ້ນຊື່ຂອງມັນ. ພວກເຮົາສາມາດປະສົມປະສານກັບສອງຂອດເພື່ອຈັດເປັນແຖວທີ່ຈັດລຽງ ລຳ ດັບໂດຍລວມ. ໃນບັນຫານີ້, ພວກເຮົາຕ້ອງໄດ້ລວມເອົາສອງລາຍການທີ່ເຊື່ອມໂຍງເຂົ້າກັນ ໃນ​ສະ​ຖານ​ທີ່ ເພື່ອກັບຄືນບັນຊີລາຍຊື່ ໃໝ່ ເຊິ່ງມີສ່ວນປະກອບຂອງທັງສອງລາຍການໃນແບບທີ່ຈັດໄວ້.

ຍົກຕົວຢ່າງ

ຜະສົມຜະສານສອງລາຍການ Leetcode Solutions

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

ວິທີການ

ວິທີທີ່ງ່າຍທີ່ສຸດທີ່ຈະເຮັດມັນແມ່ນການໃຊ້ ສອງຕົວຊີ້ ເຕັກນິກ. ສ້າງບັນຊີລາຍຊື່ເປົ່າ ໃໝ່. ຕື່ມໃສ່ສ່ວນປະກອບທີ່ນ້ອຍກວ່າທັງສອງຈຸດແລະເພີ່ມຕົວຊີ້ທີ່ສອດຄ້ອງກັນ. ນີ້ແມ່ນວິທີການທີ່ດີແຕ່ຮຽກຮ້ອງໃຫ້ມີການສ້າງລາຍຊື່ພິເສດທີ່ບໍລິໂພກພື້ນທີ່.

ວິທີການທີ່ດີທີ່ສຸດຄວນຈະໃຊ້ພື້ນທີ່ຄົງທີ່ເທົ່ານັ້ນທີ່ຈະເຮັດ ໃນ​ສະ​ຖານ​ທີ່ ຈັດຮຽງ. ພວກເຮົາສາມາດປະຕິບັດຕາມວິທີການທີ່ກ່າວມານັ້ນ. ພວກເຮົາມີຂໍ້ມູນທີ່ເກັບໄວ້ໃນທັງສອງລາຍການ. ສ້າງຕົວຊີ້ທິດທາງ ໃໝ່ ແລະການຕິດຕໍ່ມາຂອງມັນ“ຈຸດຕໍ່ໄປ” ຄວນຊີ້ໃຫ້ເຫັນຂໍ້ທີ່ ກຳ ນົດໄວ້ໃນຄວາມຊົງ ຈຳ. ໃນຂະບວນການນີ້, ພວກເຮົາສ້າງ no ຂໍ້ ໃໝ່.

ສູດການຄິດໄລ່ (ວິທີການ Naive)

  1. ສ້າງ ໜ້າ ທີ່ ບັນຊີລາຍຊື່ທຸລະກິດ () ທີ່ໃຊ້ເວລາສອງຕົວຊີ້ບອກລາຍຊື່ເປັນການໂຕ້ຖຽງ
  2. ຖ້າຫາກວ່າບັນຊີລາຍຊື່ໃດກໍ່ຕາມແມ່ນ NULL, ກັບຄືນອີກອັນ ໜຶ່ງ
  3. ສ້າງເປັນ ວັດລົມ ຕົວແປທີ່ຈະຊີ້ໄປທີ່ໂຫນດນ້ອຍກວ່າ ໝູ່ ໃນບັນດາຫົວ ໜ້າ ຂອງທັງສອງລາຍການ
  4. ໃນປັດຈຸບັນ, ຢ່າງຫນ້ອຍ, ຫນຶ່ງ node ແມ່ນເພີ່ມຂື້ນກັບຜົນໄດ້ຮັບຂອງພວກເຮົາ, ດັ່ງນັ້ນຫນຶ່ງຫົວຄວນເພີ່ມຂື້ນ
  5. ສິ່ງນີ້ສ້າງຮູບແບບຍ່ອຍ. ສະນັ້ນ, ໃຫ້ໂທຫາຟັງຊັນທີ່ເອີ້ນຫາແບບດຽວກັນນີ້ແລະຕື່ມໃສ່ກັບ temp
  6. ຖ້າ List1.value <List2.value
    • ອຸນຫະພູມ = ListNode ໃໝ່ (List1.value) , temp-> ຕໍ່ໄປ = ບັນຊີລາຍຊື່ທຸລະກິດ (ລາຍຊື່ 1-> ຕໍ່ໄປ, ລາຍການທີ 2)
  7. ຖ້າ List2.value <= List1.value
    • ອຸນຫະພູມ = ListNode ໃໝ່ (List2.value) , temp-> ຕໍ່ໄປ = ບັນຊີລາຍຊື່ລວມ (ບັນຊີ 1, ບັນຊີ 2-> ຕໍ່ໄປ)
  8. Return ວັດລົມ ເພື່ອໃຫ້ໄດ້ບັນຊີລາຍຊື່ທີ່ຕ້ອງການ

ສູດການຄິດໄລ່ (ດີທີ່ສຸດ)

  1. ສ້າງຕົວຊີ້ທິດທາງ ໃໝ່ ເຊິ່ງຈະຖືກເອີ້ນ ຫົວ dummy_
  2. ຮັກສາ“ກ່ອນກ່ອນເວລາ” (ສຳ ເນົາຕົວຊີ້) ເພື່ອໃຫ້ພວກເຮົາສາມາດເຂົ້າເບິ່ງລາຍຊື່ໄດ້ ຫົວຫນ້າ ທີ່ຢູ່.
  3. ການ "ຈຸດຕໍ່ໄປ” ຂອງ dummy_head ຄວນຖືກ ໝູນ ໃຊ້ໃນແບບທີ່ມັນຊີ້ໃຫ້ເຫັນຂໍ້ທີ່ ກຳ ນົດໄວ້ໃນລາຍການ l1 ແລະ l2.
  4. ພວກເຮົາສາມາດເຮັດວຽກງານຂ້າງເທິງນີ້ໄດ້ໃນວິທີການດັ່ງຕໍ່ໄປນີ້:
    • ຮັກສາລາຍການດ້ວຍຈຸດຊີ້ເລີ່ມຈາກຫົວຂອງພວກເຂົາ.
    • ເວັ້ນເສຍແຕ່ວ່າ ໜຶ່ງ ໃນບັນຊີລາຍຊື່ຖືກໂອນໄປ ໝົດ:
      • ຕິດຕໍ່ໃສ່ໂຫນດທີ່ມີຄຸນຄ່າຂະ ໜາດ ນ້ອຍກວ່າຈາກສອງຕົວຊີ້ໄປທີ່ ຫົວ dummy_, ເພີ່ມຕົວຊີ້ທີ່ສອດຄ້ອງກັນ.
    • ໃນປັດຈຸບັນ, ຢ່າງຫນ້ອຍຫນຶ່ງໃນຈຸດແມ່ນ NULL. ດັ່ງນັ້ນ, ຕື່ມຂໍ້ມູນໃສ່ ບໍ່ແມ່ນ ບັນຊີລາຍຊື່ຂອງຫົວ dummy.
  5. ກັບໄປ ຫົວຫນ້າ ຂອງບັນຊີລາຍຊື່ dummy.

ການປະຕິບັດ

ໂປຣແກຣມ C ++ ທີ່ຈະລວມຕົວສອງແຖວທີ່ມີລາຍຊື່

ວິທີການ Naive

#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

Java Program ເພື່ອລວມຕົວສອງແຖວທີ່ມີລາຍຊື່

ວິທີການ Naive

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

ການວິເຄາະຄວາມສັບສົນ

ຄວາມສັບສົນເວລາ ການຜະສົມຜະສານລາຍຊື່ສອງແຖວ

O (N + M), ບ່ອນທີ່ N ແລະ M ແມ່ນຄວາມຍາວຂອງສອງລາຍການ. ພວກເຮົາລວບລວມບັນຊີລາຍຊື່ທັງສອງຄັ້ງໃນທັງສອງວິທີການ, ດັ່ງນັ້ນທັງສອງສູດການຄິດໄລ່ແມ່ນເປັນເສັ້ນ.

ຄວາມສັບສົນໃນອະວະກາດ ການຜະສົມຜະສານລາຍຊື່ສອງແຖວ

ໃນວິທີການທີ່ດີທີ່ສຸດ, ມັນເປັນສິ່ງ ສຳ ຄັນທີ່ຈະເຂົ້າໃຈວ່າພວກເຮົາມີແຕ່ຄົນດຽວ ໝູນ ໃຊ້ຜູ້ຊີ້ ນຳ. ດັ່ງນັ້ນ, ພື້ນທີ່ຄົງທີ່ ສຳ ລັບບັນຊີຕົວແປ ສຳ ລັບການ ນຳ ໃຊ້ຫນ່ວຍຄວາມ ຈຳ. ເພາະສະນັ້ນ, ວິທີການທີ່ດີທີ່ສຸດມີຄວາມສັບສົນພື້ນທີ່ຂອງ O (1). O (N + M) ພື້ນທີ່ຖືກ ນຳ ໃຊ້ໃນວິທີການທີ່ໂງ່ຈ້າທີ່ຖືກສົນທະນາ.