Palindrome Linked စာရင်း Leetcode ဖြေရှင်းချက်  


ခက်ခဲအဆင့် လွယ်ကူသော
မကြာခဏမေးတယ် Adobe က အမေဇုံ Apple ဘလွန်းဘာ့ဂ် Capital One Cisco သည် Facebook က Google ဆုပ်ကိုင် Intel က IXL Microsoft က Nutanix Oracle က Paytm Snapchat Uber Yandex
algorithms coding အင်တာဗျူး အင်တာဗျူး LeetCode LeetCodeSolutions ချိတ်ဆက်စာရင်း နှစ်ခုထောက်ပြ

ပြindနာ“ Palindrome Linked List” တွင်ကျွန်ုပ်တို့သည်တစ်ခုတည်းသောကိန်းပြည့်ဟုတ်မဟုတ်ကိုစစ်ဆေးရပါမည် ဆက်စပ်စာရင်း palindrome လားမပါဘူး။

နမူနာ  

List = {1 -> 2 -> 3 -> 2 -> 1}
true

ရှင်းလင်းချက် # 1ဖြေ - စာရင်းက palindrome ဖြစ်တယ်။ ဘာလို့လဲဆိုတော့ start နဲ့ back က element အားလုံးတန်ဖိုးအတူတူပဲ။

List = {1 -> 2 -> 3 -> 4 -> 5}
false

ရှင်းလင်းချက် # 2ဖြေ - စာရင်းက palindrome မဟုတ်ပါဘူး။

ချဉ်းကပ်မှု (နေ့တိုင်းပြန်လည်စတင်မည် 

palindrome ဂုဏ်သတ္တိများကိုစစ်ဆေးရန်အတွက် array ၏နောက်ဖက်ရှိ node များ၏အသေးစိတ်အချက်အလက်များကိုကျွန်ုပ်တို့လိုအပ်သည်ကိုသတိပြုမိရန်လွယ်ကူသည်။ ဤကိစ္စတွင်ကျွန်ုပ်တို့သည်တစ် ဦး ရှိသည် တစ်ယောက်တည်း link list သည်မည်သည့် node ကိုမဆိုရောက်ရှိရန်ရှေ့ဆက်သွားနိုင်သည်ဟုဆိုလိုသည်။ ထို့ကြောင့်၊ ဥပမာကျောရိုးမှ node များကိုထိန်းသိမ်းရန်ဒေတာဖွဲ့စည်းပုံကိုအသုံးပြုရန်အရေးကြီးသည် စုပုံထား ထိပ်ဆုံးရှိနောက်ဆုံးပေါ် node ကိုသိမ်းထားသကဲ့သို့ဖြစ်နိုင်သော option တစ်ခုဖြစ်သည်။ ငါတို့သည်လည်းအလားတူ recursion ကိုသုံးနိုင်သည်။ Recursion သည် node တန်ဖိုးများကိုပြောင်းပြန်အစဉ်လိုက်အဆင်ပြေစေရန်ပြုလုပ်ပေးသည်။ ပိုမိုနားလည်ရန်အောက်ဖော်ပြပါအထွေထွေ pseudocode ကိုစဉ်းစားပါ -

inorderTraversal(root)
{
    if(root == null)
        return;
    inorderTraversal(root.left);
    print(root.data);
    inorderTraversal(root.right);
}

အပေါ်ကကုဒ်ကိုအရင်ရိုက်တယ် လက်ဝဲဘက် သစ်ပင်အတွင်းရှိ node များသည် function ကို nurs ၏တန်ဖိုးကိုမပုံနှိပ်မီမည်သည့်အမြစ်မှကျန်ရှိသောကလေးများထံသို့သွားရန် function ကိုခေါ်သောကြောင့်ဖြစ်သည်။ အလားတူပဲကျနော်တို့ကိုသုံးနိုင်သည် ပြန်လည် ပထမဆုံး node ကိုအရင်သွားရန်နှင့် function သည်နောက်သို့ပြန်သွားပါက node တန်ဖိုးများကိုပြောင်းပြန်နိုင်ရန်ဖြစ်သည်။ ကျနော်တို့က recursion အားဖြင့်ထိခိုက်လိမ့်မည်သည့် forward iterate ဖို့ variable ကိုသုံးပါလိမ့်မယ်။ ဤနည်းအားဖြင့်ကျွန်ုပ်တို့သည် iterator ၏ forward နှင့် element များကိုနှိုင်းယှဉ်ရန် recursion မှရရှိသော reverse node ၏တန်ဖိုးကိုနှိုင်းယှဉ်နိုင်သည်။

လည်းကြည့်ရှုပါ
အိုင်ပီလိပ်စာ Leetcode Solution ကိုသတ်မှတ်ခြင်း

algorithm

  1. function တစ်ခု isPalindrome () နှင့်အတူစာရင်းတစ်ခုရှိမရှိပြန်လာရန်အသုံးပြုသည် ဦးခေါင်း palindrome သို့မဟုတ်မဖြစ်ပါတယ်
  2. ကျနော်တို့အမည်ရှိအတန်း၏ဒေတာအဖွဲ့ဝင်ကြေညာ ရှေ့ ရှေ့သို့ကြားမှာများအတွက် node များသိုလှောင်ရန်
  3. In isPalindrom ():
    • စတငျ ရှေ့ = ခေါင်း
    • palindromeCheck ကိုပြန်သွားပါ (ဦး ခေါင်း)
  4. In palindromeCheck (ယခု):
    • If ယခု is တရားမဝင်သော:
      • ပြန်လာ စစ်မှန်တဲ့
    • If palindromeCheck (လက်ရှိ) is မမှန်သော:
      • ပြန်လာ မမှန်သော
    • If လက်ရှိ is မဟုတ် ညီမျှသည် မင်္ဂလာပါ
      • ပြန်လာ မမှန်သော
    • ရှေ့တိုးသည်
      • ရှေ့ = front.next
    • ပြန်လာ စစ်မှန်တဲ့ ငါတို့ရှိသမျှသည်စစ်ဆေးမှုများဖျော်ဖြေအဖြစ်
  5. ရလဒ်ပုံနှိပ်ပါ

Palindrome Linked List Leetcode ဖြေရှင်းချက်၏အကောင်အထည်ဖော်မှု

C ++ အစီအစဉ်

#include <bits/stdc++.h>
using namespace std;
struct listNode
{
    int value;
    listNode* next;
    listNode(int x)
    {
        value = x;
        next = NULL;
    }
};

bool palindromeCheck(listNode* head)
{
    if(head == NULL)
        return true;
    if(!palindromeCheck(head->next))
        return false;
    if(front->value != head->value)
        return false;
    front = front->next;
    return true;
}

bool isPalindrome(listNode* head)
{
    front = head;
    return palindromeCheck(head);
}

int main()
{
    listNode* head = new listNode(1);
    head->next = new listNode(2);
    head->next->next = new listNode(3);
    head->next->next->next = new listNode(2);
    head->next->next->next->next = new listNode(1);

    cout << (isPalindrome(head) ? "true\n" : "false\n");
    return 0;
}

Java အစီအစဉ်

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

class palindrome_linked_list
{
    static listNode front;
    public static void main(String args[])
    {
        listNode head = new listNode(1);
        head.next = new listNode(2);
        head.next.next = new listNode(3);
        head.next.next.next = new listNode(2);
        head.next.next.next.next = new listNode(1);

        System.out.println((isPalindrome(head)) ? "true" : "false");
    }

    static boolean palindromeCheck(listNode head)
    {
        if(head == null)
            return true;
        if(!palindromeCheck(head.next))
            return false;
        if(front.value != head.value)
            return false;
        front = front.next;
        return true;
    }

    static boolean isPalindrome(listNode head)
    {
        front = head;
        return palindromeCheck(head);
    }
}
true

Palindrome Linked List Leetcode ဖြေရှင်းချက်၏ရှုပ်ထွေးအားသုံးသပ်ခြင်း

အချိန်ရှုပ်ထွေး

အို (N) ကျွန်တော်တစ်ချိန်က recursion သုံးပြီးစာရင်းဖြတ်သန်းအဖြစ်။ ဤတွင် N = စာရင်းထဲတွင် node များအရေအတွက်။

လည်းကြည့်ရှုပါ
Binary သစ်ပင် Serialize နှင့် Deserialize

အာကာသရှုပ်ထွေးမှု

အို (N) node ဖန်တီးတိုင်းကိုစစ်ဆေးရန် recursive function ကိုခေါ်သည် N မှတ်ဉာဏ်ထဲမှာ frames များကို stack ။

ချဉ်းကပ်မှု (အခြားတစ်ဝက်ကိုပြောင်းပြန်)  

recursion တွင်အသုံးပြုသောအာကာသကိုဖယ်ရှားရန်တစ်ခုတည်းသောနည်းလမ်းမှာပေးထားသောစာရင်းအားနေရာတွင်ပြုပြင်ခြင်းဖြစ်သည်။ ကျနော်တို့ချိတ်ဆက်စာရင်း၏ဒုတိယတစ်ဝက် reverse နှင့်ထို့နောက်သက်ဆိုင်ရာတန်ဖိုးများကိုတန်းတူရှိမရှိစစ်ဆေးနိုင်ရန်နှစ် ဦး စလုံးနှစ်ခုလုံးအတွက် forward ကြားမှာနှစ်ခုကိုအသုံးပြုပါ။ ဤလုပ်ငန်းစဉ်အတွက်ကျွန်ုပ်တို့သည် -

  • ဒုတိယတစ်ဝက်ကိုပြန်ပြောင်းနိုင်အောင်စာရင်းရဲ့အလယ်ကိုရှာပါ။
  • စာရင်း၏ဒုတိယတစ်ဝက်ကို reverse ရန် function ကိုဖန်တီးပါ
  • ပထမနှင့်ဒုတိယတစ်ဝက်သည်ညီမျှမှုရှိမရှိစစ်ဆေးပါ

အထက်ဖော်ပြပါအရာအားလုံးကို linear အချိန်တွင်လုပ်ဆောင်နိုင်သည်။ ကျနော်တို့လင့်ခ်လုပ်ထားတဲ့ list ကိုပြန်ပြင်ပြီးတဲ့နောက်ဒုတိယတစ်ဝက်မပြီးမချင်းစစ်ဆေးပါတယ်။

Palindrome Linked စာရင်း Leetcode ဖြေရှင်းချက်တွယ်အပ်

algorithm

  1. If ဦးခေါင်း is တရားမဝင်သော:
    • ပြန်လာပါ
  2. သုံးပြီးချိတ်ဆက်စာရင်း၏အလယ်ကိုရှာပါ middleOfList (ဦးခေါင်းfunction ကို:
    • နှစ်ခုထောက်ပြ Initialize နှေးနှေး နှင့် လျင်မြန်စွာ နှစ် ဦး စလုံးစာရင်း၏ ဦး ခေါင်းကိုညွှန်ပြ
    • မှီတိုငျအောငျ မြန် နှင့် မြန်ဆန် နှစ်ခုလုံးက မဟုတ် တရားမဝင်သော
      1. တိုး နှေးနှေး ၂၀၂၂ ခုနှစ်တွင် နှေးကွေး = slow.next
      2. တိုး လျင်မြန်စွာ ၂၀၂၂ ခုနှစ်တွင် အစာရှောင်ခြင်း = fast.next.next
    • နှေးနှေး pointer ယခုစာရင်း၏အလယ်ကိုညွှန်ပြ
    • ပြန်လာ နှေးနှေး
  3. ယခုကျွန်ုပ်တို့သည်ခေါ်ဆိုမှု၏ဒုတိယတစ်ဝက်ကိုပြောင်းပြန်လုပ်သည် reverseList (ဦး ခေါင်း = အလယ်အလတ်) function ကို
    • ကန ဦး prev = တရားမဝင်သော
    • စဉ်တွင် ဦးခေါင်း null မဟုတ်ပါဘူး:
      • လာမယ့် node ကိုယာယီ variable ထဲမှာသိမ်းထားပါ လာမယ့်
      • အသုံးပြုခြင်းဖြင့် pointer ဦး တည်ချက်ကိုပြောင်းပါ head.next = ရှေ့သို့
      • prev = ဦး ခေါင်း
      • သုံးပြီးစာရင်းထဲတွင်ရှေ့ဆက်ပါ head = နောက်
    • ပြန်လာ prev
  4. အခုတော့နှစ်ခုထောက်ပြ intialise ptr1 နှင့် ptr2 နှစ်ဖက်စလုံးကိုဖြတ်ပြီးကြားဖြတ်ရန်
    1. ptr1 = ဦး ခေါင်း
    2. ptr2 = စတင်ပါ ဒုတိယတစ်ဝက်၏
    3. စဉ်တွင် ptr2 null မဟုတ်ပါဘူး:
      1. if ptr1.အဘိုး ညီမျှသည်မဟုတ် ptr2.အဘိုး
        1. ပြန်လာ မမှန်သော
    4. ပြန်လာ စစ်မှန်တဲ့ ကျွန်တော်ပထမနှင့်ဒုတိယတစ်ဝက်တွင် node တိုင်းကိုစစ်ဆေးသည်
  5. ရလဒ်ပုံနှိပ်ပါ
လည်းကြည့်ရှုပါ
K သည်အချည်းနှီးသော slot နှစ်ခု LeetCode

Palindrome Linked List Leetcode ဖြေရှင်းချက်၏အကောင်အထည်ဖော်မှု

C ++ အစီအစဉ်

#include <bits/stdc++.h>
using namespace std;
struct listNode
{
    int value;
    listNode* next;
    listNode(int x)
    {
        value = x;
        next = NULL;
    }
};

listNode* middleOfList(listNode* head)
{
    listNode *slow = head , *fast = head;
    while(fast->next != NULL && fast->next->next != NULL)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

listNode* reverseList(listNode* head)
{
    listNode *prev = NULL;
    while(head != NULL)
    {
        listNode* next = head->next;
        head->next = prev;
        prev = head;
        head = next;
    }
    return prev;
}

bool isPalindrome(listNode* head)
{
    if(head == NULL)
        return true;
    listNode* middleNode = middleOfList(head);
    listNode* startOfSecondHalf = reverseList(middleNode->next);

    listNode *ptr1 = head , *ptr2 = startOfSecondHalf;
    while(ptr2 != NULL)
    {
        if(ptr1->value != ptr2->value)
            return false;
        ptr1 = ptr1->next;
        ptr2 = ptr2->next;
    }
    return true;
}

int main()
{
    listNode* head = new listNode(1);
    head->next = new listNode(2);
    head->next->next = new listNode(3);
    head->next->next->next = new listNode(2);
    head->next->next->next->next = new listNode(1);

    cout << (isPalindrome(head) ? "true\n" : "false\n");
    return 0;
}

Java အစီအစဉ်

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

class palindrome_linked_list
{
    public static void main(String args[])
    {
        listNode head = new listNode(1);
        head.next = new listNode(2);
        head.next.next = new listNode(3);
        head.next.next.next = new listNode(2);
        head.next.next.next.next = new listNode(1);

        System.out.println((isPalindrome(head)) ? "true" : "false");
    }

    static listNode middleOfList(listNode head)
    {
        listNode slow = head , fast = head;
        while(fast.next != null && fast.next.next != null)
        {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    static listNode reverseList(listNode head)
    {
        listNode prev = null;
        while(head != null)
        {
            listNode next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }

    static boolean isPalindrome(listNode head)
    {
        if(head == null)
            return true;
        listNode middleNode = middleOfList(head);
        listNode startOfSecondHalf = reverseList(middleNode.next);

        listNode ptr1 = head , ptr2 = startOfSecondHalf;
        while(ptr2 != null)
        {
            if(ptr1.value != ptr2.value)
                return false;
            ptr1 = ptr1.next;
            ptr2 = ptr2.next;
        }
        return true;
    }
}
true

Palindrome Linked List Leetcode ဖြေရှင်းချက်၏ရှုပ်ထွေးအားသုံးသပ်ခြင်း

အချိန်ရှုပ်ထွေး

အို (N) ကျနော်တို့ linear loops တွေကိုသုံးတဲ့အခါ list ရဲ့အလယ်ကိုရှာပြီး၎င်းကိုပြန်ပြောင်းပါ။ ဒီမှာ, N = စာရင်း၏အရွယ်အစား။

လည်းကြည့်ရှုပါ
element အားလုံးအား k ထက်နည်းသည်သို့မဟုတ်ညီမျှစေရန်အနည်းဆုံးလဲလှယ်ရေးအစီအစဉ်များလိုအပ်သည်

အာကာသရှုပ်ထွေးမှု

အို (၁) ကျွန်တော်သာစဉ်ဆက်မပြတ်အပိုအာကာသကိုသုံးပါအဖြစ်။