Байланышкан тизме элементтерин Leetcode чечиминен алып салыңыз  


Кыйынчылык деңгээли жеңил
Көп суралган Adobe Amazon алма Bloomberg Capital One Facebook Гугл Microsoft
Алгоритмы коддоо интервью интервью даярдоо LeetCode LeetCodeSolutions Байланышкан тизме Таза сактоо

Маселени билдирүү  

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

мисал

List = 1 -> 2 -> 2 -> 3 -> 4 , val = 2
1 3 4
List = 2 -> 2 -> 2 -> 2 , val = 2
Empty List

Байланышкан тизме элементтерин Leetcode чечиминен алып салыңызтөөнөч  

Мамиле (рекурсивдүү)  

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

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

Байланышкан тизме элементтерин алып салуу Leetcode Solution

C ++ программасы

#include <bits/stdc++.h>

using namespace std;

struct listNode
{
    int value;
    listNode* next;
    listNode(int x)
    {
        value = x;
        next = NULL;
    }
};

void print(listNode* head)
{
    if(head == NULL) {
        cout << "Empty List\n";
        return;
    }
    while(head)
    {
        cout << head->value << " ";
        head = head->next;
    }
    cout << '\n';
    return;
}

listNode* removeElements(listNode* head, int val) {
    if(head == NULL) {
        return head;
    }
    if(head->value == val) {
        listNode* temp = head->next;
        head->next = NULL;
        delete(head);
        return removeElements(temp , val);
    }

    head->next = removeElements(head->next , val);
    return head;
}

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

    int val = 2;
    print(removeElements(head , val));
    return 0;
}

Java программасы

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

class remove_linked_list_elements {
    public static void print(listNode head) {
        if(head == null) {
            System.out.println("Empty List");
            return;
        }
        while(head != null)
        {
            System.out.print(head.value + " ");
            head = head.next;
        }
        System.out.println();
        return;
    }

    public static listNode removeElements(listNode head, int val) {
        if(head == null) {
            return head;
        }
        if(head.value == val) {
            return removeElements(head.next , val);
        }

        head.next = removeElements(head.next , val);
        return head;
    }

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

        int val = 2;
        print(removeElements(head , val));
    }
}
1 3 4

Санды Комплементтин Leetcode Чечиминин Комплекстүүлүгүн Талдоо

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

O (N), мында N = тизменин узундугу. Эң начар учурда ар бир элементке бир эле жолу барабыз.

ошондой эле
Суу ташкынын толтуруу LeetCode

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

O (1). Код төмөнкүдөй куйрук рекурсия.

Мамиле (кайталоо)  

Кандайдыр бир түйүндү жок кылуу үчүн, анын мурунку түйүнүнүн дарегин алышыбыз керек, ошондо биз мурунку чекитти кийинки баскычка жасай алабыз. Бул идеяны сактап калуу идеясын берет мурунку Тизмедеги көрсөткүчтөрдү башкарууга жардам бере турган көрсөткүч. Эми, маанилүү жагдай, тизмедеги биринчи түйүндүн мурунку түйүнү жок. Ошентип, биз тизменин башына күзөтчү түйүнүн кошушубуз керек. Эми, биз тизмедеги биринчи түйүн аркылуу өтө алабыз (күзөтчү түйүндүн жанындагы түйүн) жана төмөнкү эки шартка туш болобуз:

1.) node-> value == val: Бул учурда, биз орнотобуз prev-> next = node-> next. Бул учурдагы түйүндүн мурункусун учурдагы түйүн менен кийинки байланыштырып, учурдагы түйүндү жок кылат: жок кылуу (currentNode)

2.) Болбосо, жөн эле койдук мурунку = баш алдыдагы түйүндөр үчүн.

Акыр-аягы, күзөттүн кийинки бөлүгү талап кылынган тизме болуп саналат.

Байланышкан тизме элементтерин алып салуу Leetcode Solution

C ++ программасы

#include <bits/stdc++.h>

using namespace std;

struct listNode
{
    int value;
    listNode* next;
    listNode(int x)
    {
        value = x;
        next = NULL;
    }
};

void print(listNode* head)
{
    if(head == NULL) {
        cout << "Empty List\n";
        return;
    }
    while(head)
    {
        cout << head->value << " ";
        head = head->next;
    }
    cout << '\n';
    return;
}

listNode* removeElements(listNode* head, int val) {
    listNode *dummy = new listNode(-1) , *prev = dummy , *toDelete;
    dummy->next = head;

    while(head != NULL) {
        if(head->value == val) {
            toDelete = head;
            prev->next = head->next;
            head = head->next;
            toDelete->next = NULL;
        }
        else {
            toDelete = NULL;
            prev = head;
            head = head->next;
        }
        if(toDelete != NULL)
            delete(toDelete);
    }

    return dummy->next;
}

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

    int val = 2;
    print(removeElements(head , val));
    return 0;
}

Java программасы

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

class remove_linked_list_elements {
    public static void print(listNode head) {
        if(head == null) {
            System.out.println("Empty List");
        return;
        }
        while(head != null)
        {
            System.out.print(head.value + " ");
            head = head.next;
        }
        System.out.println();
        return;
    }

    public static listNode removeElements(listNode head, int val) {
        listNode dummy = new listNode(-1) , prev = dummy , toDelete;
        dummy.next = head;

        while(head != null) {
            if(head.value == val) {
                prev.next = head.next;
            }
            else {
                prev = head;
            }
            head = head.next;
        }

        return dummy.next;
    }

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

        int val = 2;
        print(removeElements(head , val));
    }
}
1 3 4

Байланышкан тизме элементтерин алып салуу татаалдыгын талдоо Leetcode Solution

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

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

ошондой эле
Сорттолгон массивдерди Leetcode Solution менен бириктирүү

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

O (1), биз болгону туруктуу эс тутум мейкиндиги.

1