Палиндромдун шилтеме тизмеси Leetcode чечими


Кыйынчылык деңгээли жеңил
Көп суралган Adobe Amazon алма Bloomberg Capital One Cisco Facebook Гугл кармоо Intel IXL Microsoft Nutanix Oracle Paytm снэпчат Uber Яндекс
Байланышкан тизме Эки көрсөткүч

"Палиндромго шилтеме берилген тизме" маселесинде, биз берилген бир бүтүн санды текшеришибиз керек байланышкан тизме палиндром болуп саналат же жок.

мисал

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

Түшүндүрмө # 1: Тизме палиндромдук, анткени башынан жана артынан бардык элементтер мааниси боюнча бирдей.

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

Түшүндүрмө # 2: Тизме палиндром эмес, анткени алды жактагы жана арткы элементтер бирдей эмес.

Мамиле (Recursion)

Палиндромдун касиеттерин текшерүү үчүн, массивдин арт жагындагы түйүндөрдүн деталдары болушу керектигин байкоо оңой. Бул учурда бизде а жалгыз байланышкан тизме, биз каалаган түйүнгө жетүү үчүн гана алдыга кайталай алабыз. Ошентип, арткы түйүндөрдү кармоо үчүн айрым маалымат структурасын колдонуу маанилүү болуп калат чөмөлө мүмкүн болгон вариант, анткени ал эң акыркы түйүндү жогору жагында кармайт. Биз ошондой эле рекурсияны колдоно алабыз. Рекурсия - бул түйүндүн маанилерин тескери тартипте алуу. Жакшыраак түшүнүү үчүн төмөндөгү жалпы псевдокодду карап көрүңүз:

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

Жогорудагы код алгач басып чыгарат сол дарактын түйүндөрү, анткени биз функцияны рекурстуу түрдө түйүндүн өзүн басып чыгаруудан мурун каалаган тамырдын сол балдарына өтүү деп атайбыз. Ошо сыяктуу эле, биз колдоно алабыз рекурсия адегенде акыркы түйүндөргө өтүү үчүн жана функция артка кайтканда, биз түйүндүн маанилерин тескери тартипте алабыз. Биз алдыга кайталоо үчүн өзгөрмө колдонобуз, ага рекурсия таасир этпейт. Ошентип, элементтерди салыштыруу үчүн рекурсия жолу менен алынган итератордун маанисин жана тескери түйүндүн маанисин салыштыра алабыз.

Algorithm

  1. Функция isPalindrome () менен тизме болгонун кайтаруу үчүн колдонулат баш палиндром болуп саналат же жок
  2. Аттуу класстын маалымат мүчөсү деп жарыялайбыз алдыңкы форварддык кайталоолор үчүн түйүндөрдү сактоо
  3. In isPalindrom ():
    • Initialize алдыңкы = баш
    • return palindromeCheck (баш)
  4. In palindromeCheck (учурдагы):
    • If учурдагы is нөл:
      • кайра чыныгы
    • If palindromeCheck (current.next) is жалган:
      • кайра жалган
    • If current.value is жок барабар front.value
      • кайра жалган
    • алдыңкы бөлүктү төмөнкүдөй көбөйтүү
      • front = front.next
    • кайра чыныгы бардык текшерүүлөрдү жүргүзгөндөй эле
  5. Жыйынтыгын басып чыгарыңыз

Палиндромдун Байланыштуу Тизмек 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

Палиндромго байланышкан тизме Leetcode чечиминин татаалдыгын талдоо

Убакыт татаалдыгы

O (N) бир жолу рекурсияны колдонуп тизмеден өтсөк. Бул жерде, N = тизмедеги түйүндөрдүн саны.

Космостун татаалдыгы

O (N) ар бир түйүндүн түзүлүшүн текшерүү үчүн рекурсивдүү функция деп атасак болот N эстутумга кадрларды топтоо.

Ыкма (башка жарымын тескери)

Рекурсияда колдонулган мейкиндиктен арылуунун бирден-бир жолу - берилген тизмени ордунда өзгөртүү. Шилтемеленген тизменин экинчи жарымын артка кайтарып, андан соң эки мааниде эки алга жылдыргычты колдонуп, тиешелүү маанилердин барабар экендигин текшеребиз. Бул процесс үчүн төмөнкүлөр керек:

  • экинчи жарымын артка кайтарышыбыз үчүн, тизменин ортосун тап.
  • тизменин экинчи жарымын өзгөртүү функциясын түзүү
  • биринчи жана экинчи жарым тең экендигин текшерүү

Жогоруда айтылгандардын бардыгын сызыктуу убакытта жасоого болот. Шилтемеленген тизмени артка кайтаргандан кийин, экинчи жарым аяктаганга чейин текшере баштайбыз.

Палиндромдун шилтеме тизмеси Leetcode чечими

Algorithm

  1. If баш is нөл:
    • return true
  2. Шилтеме аркылуу тизменин ортосун тап middleOfList (башмилдети:
    • Эки көрсөткүчтү баштаңыз жай жана орозо экөө тең тизменин башын көрсөтүп жатышат
    • чейин fast.next жана fast.next.next экөө тең жок нөл:
      1. Көбөйтүү жай 1-жылга чейин, жай = жай.кийинки
      2. Көбөйтүү орозо 2-жылга чейин, fast = fast.next.next
    • жай көрсөткүч эми тизменин ортосун көрсөтөт
    • кайра жай
  3. Азыр биз чакыруу тизменин экинчи жарымын артка кайтарабыз reverseList (баш = middle.next) милдети
    • Баштоо мурунку = нөл
    • жатканда баш нөл эмес:
      • Кийинки түйүндү убактылуу өзгөрүлмө катары сактоо кийинки
      • Колдонуу менен көрсөткүчтү тескери буруңуз head.next = мурунку
      • мурунку = баш
      • Колдонуу менен тизмеде алдыга жылуу баш = кийинки
    • кайра мурунку
  4. Эми, эки көрсөткүчкө көңүл буруңуз ptr1 жана ptr2 эки жарымынан тең кайталоо:
    1. ptr1 = баш
    2. ptr2 = баштоо экинчи жарым
    3. жатканда ptr2 нөл эмес:
      1. if ptr1.Наркы барабар эмес ptr2.Наркы
        1. кайра жалган
    4. кайра чыныгы биринчи жана экинчи жарымында ар бир түйүндү текшергендей
  5. Жыйынтыгын басып чыгарыңыз

Палиндромдун Байланыштуу Тизмек 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

Палиндромго байланышкан тизме Leetcode чечиминин татаалдыгын талдоо

Убакыт татаалдыгы

O (N) биз сызык циклдарын колдонуп, тизменин ортосун таап, тескери буруп, эки жарымын тең салыштырып жатабыз. Бул жерде, N = тизменин көлөмү.

Космостун татаалдыгы

O (1) анткени биз туруктуу кошумча мейкиндикти гана колдонобуз.