Палиндромын жагсаалттай Leetcode шийдэл


Хэцүү байдлын түвшин Easy
Байнга асуудаг Adobe Амазоны Apple-ийн Bloomberg Капитал Нэг Cisco Facebook-ийн Google-ийн Хүлээн авах Intel IXL Microsoft- Nutanix Oracle-ийн Paytm Snapchat Uber Yandex
Холбогдсон жагсаалт Хоёр заагч

“Палиндромын холбосон жагсаалт” асуудалд бид өгөгдсөн дан ганц бүхэл тоо эсэхийг шалгах ёстой холбоотой жагсаалт нь палиндром юмуу үгүй ​​юу.

Жишээ нь

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

Тайлбар # 1: Эхлэл ба арын бүх элементүүд ижил утгатай тул жагсаалт нь палиндром юм.

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

Тайлбар # 2: Жагсаалт нь палиндром биш юм, учир нь нааш цааш нь оруулсан элементүүд ижил биш байна

Хандалт (Сэтгэгдэл бичих)

Палиндромын шинж чанарыг шалгахын тулд массивын арын цэгээс бид зангилааны дэлгэрэнгүй мэдээллийг авах шаардлагатай байгааг анзаарахад хялбар юм. Энэ тохиолдолд бид дангаараа холбосон жагсаалт, бид ямар ч зангилаа хүрэхийн тулд зөвхөн урагш давтаж чадна гэсэн үг юм. Тиймээс зангилааг ар талаас нь барихын тулд зарим өгөгдлийн бүтцийг ашиглах нь чухал болж байна стек хамгийн сүүлийн зангилаагаа хамгийн дээд талд хадгалдаг тул боломжтой хувилбар юм. Бид мөн адил рекурсийг ашиглаж болно. Рекурси нь зангилааны утгыг урвуу дарааллаар авах гоёмсог юм. Илүү сайн ойлгохын тулд доорхи ерөнхий псевдо кодыг авч үзье.

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

Дээрх код нь эхлээд хэвлэгддэг зүүн модны зангилаа, учир нь бид зангилааныхаа утгыг хэвлэхээс өмнө аль ч язгуурын зүүн хүүхдүүд рүү шилжих функцийг рекурсив байдлаар дууддаг. Үүнтэй адил бид ашиглаж болно давтлага Эхлээд сүүлчийн зангилаанууд руу шилжихэд функц буцаж эргэх үед бид зангилааны утгыг урвуу дарааллаар авах болно. Бид урагш давтахын тулд хувьсагчийг ашиглана. Ийм байдлаар бид элементүүдийг харьцуулахын тулд давталтын давталтын утга ба урвуу зангилааны утгыг рекурсоор олж авч болно.

Алгоритм

  1. Чиг үүрэг isPalindrome () жагсаалт байгаа эсэхийг буцааж өгөхөд ашигладаг толгой Палиндром юмуу үгүй ​​юу
  2. Бид нэртэй ангийн өгөгдлийн гишүүнийг зарлаж байна урд дамжуулалтыг давтах зорилгоор зангилаа хадгалах
  3. In isPalindrom ():
    • Эхлүүлэх урд = толгой
    • буцах palindromeCheck (толгой)
  4. In palindromeCheck (одоогийн):
    • If одоогийн is тэг:
      • буцах үнэн
    • If palindromeCheck (одоо байгаа) is хуурамч:
      • буцах хуурамч
    • If одоогийн. утга is үгүй биш тэнцүү урд. утга
      • буцах хуурамч
    • урд хэсгийг дараах байдлаар нэмэгдүүлэх:
      • урд = урд тал
    • буцах үнэн Бид бүх шалгалтыг хийсэн
  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) recursion ашиглан жагсаалтыг нэг удаа тойрон гарахдаа Энд N = жагсаалтад байгаа зангилааны тоо.

Сансрын нарийн төвөгтэй байдал

O (N) зангилаа үүсгэж байгаа эсэхийг шалгах рекурсив функц гэж нэрлэдэг N санах ой дахь жаазыг овоолох.

Хандалт (Бусад талыг буцаах)

Рекурс хийхэд ашиглагдах орон зайг арилгах цорын ганц арга бол тухайн жагсаалтыг байрандаа өөрчлөх явдал юм. Бид холбосон жагсаалтын хоёр дахь талыг эргүүлж, дараа нь хоёулаа хоёуланд нь хоёр давталтын давталтыг ашиглан харгалзах утгууд тэнцүү эсэхийг шалгана. Энэ процессын хувьд бид дараахь зүйлийг хийх хэрэгтэй.

  • Жагсаалтын дунд хэсгийг олоорой, ингэснээр бид хоёрдугаар хагасыг эргүүлж болно.
  • жагсаалтын хоёр дахь хагасыг буцаах функцийг бий болгох
  • эхний ба хоёрдугаар хагас тэнцүү байгаа эсэхийг шалгана уу

Дээрх бүгдийг шугаман хугацаанд хийж болно. Холбогдсон жагсаалтыг эргүүлсний дараа бид хоёрдугаар хагасыг дуустал шалгаж эхэлнэ.

Палиндромын жагсаалттай Leetcode шийдэл

Алгоритм

  1. If толгой is тэг:
    • үнэнийг буцаана
  2. Ашиглан холбосон жагсаалтын дунд хэсгийг ол middleOfList (толгойүйл ажиллагаа:
    • Хоёр заагчийг эхлүүлнэ үү удаан болон хурдан хоёулаа жагсаалтын толгой руу заажээ
    • хүртэл хурдан. дараагийн болон хурдан.дэргэдээ хоёулаа үгүй биш хүчингүй:
      1. Инфляци удаан 1 он гэхэд удаан = удаашралтай
      2. Инфляци хурдан 2 он гэхэд хурдан = хурдан.дараагийн. дараагийн
    • удаан заагч одоо жагсаалтын дунд хэсгийг заана
    • буцах удаан
  3. Одоо бид дуудлага хийх жагсаалтын хоёр дахь хэсгийг буцаана reverseList (толгой = дунд, дараагийн) үйл ажиллагаа
    • Эхлэл prev = тэг
    • бол толгой тэг биш байна:
      • Дараагийн зангилааг түр зуурын хувьсагч дотор хадгална ирэх
      • Ашиглан заагчийн чиглэлийг буцаана head.next = өмнөх
      • өмнөх = толгой
      • Ашиглан жагсаалтад урагшлах толгой = дараагийн
    • буцах prev
  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) бид зөвхөн тогтмол нэмэлт зайг ашигладаг тул.