მიბმული სიის ელემენტების ამოღება Leetcode Solution  


Რთული ტური Easy
ხშირად ეკითხებიან Adobe Amazon Apple Bloomberg Capital One Facebook Google microsoft
ალგორითმები კოდირება ინტერვიუ ინტერვიუს მოსამზადებელი LeetCode LeetCodeSolutions მიბმული სია სუფთა შენახვის

პრობლემის განცხადება  

ამ პრობლემის დროს, ჩვენ გვაძლევენ დაკავშირებულს სია თავის კვანძებთან, რომლებსაც აქვთ მთელი მნიშვნელობები. ჩვენ უნდა წაშალოთ რამდენიმე კვანძი სიიდან, რომელთა მნიშვნელობის ტოლია ვალ პრობლემა არ საჭიროებს გადაჭრას ადგილზე მაგრამ ჩვენ განვიხილავთ ერთ ასეთ მიდგომას.

მაგალითი

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

მიბმული სიის ელემენტების ამოღება Leetcode Solution  

მიდგომა (რეკურსიული)  

შეგვიძლია რეგულარულად მოვუწოდოთ იმავე ფუნქციას, რომ დავაბრუნოთ საჭირო სიის სათაური. ამას ჩვენ მივაღწევთ მოცემული სიის შემდეგ სუფიქსებზე ფუნქციის გამოძახებით, გარკვეული პირობებით. ამასთან, ჩვენ უნდა მოვაგვაროთ ძირითადი საქმე, როდესაც სია ცარიელია. მხოლოდ ერთი განსაკუთრებული შემთხვევაა:

თუ სიის სათაურს აქვს ტოლი მნიშვნელობა 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;
}

ჯავა პროგრამა

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). როგორც კოდი შემდეგია კუდის რეკურსია.

მიდგომა (განმეორებითი)  

ნებისმიერი კვანძის წასაშლელად, ჩვენ უნდა გვქონდეს მისი წინა კვანძის მისამართი, რათა შეგვიძლია წინა წერტილი მივუთითოთ შემდეგზე. ეს იძლევა იდეის შენარჩუნებას წინა მაჩვენებელი, რომელიც დაგვეხმარება სიაში მითითებით მანიპულირებაში. ახლა მნიშვნელოვანი საკითხია ის, რომ სიაში პირველ კვანძს არ გააჩნია წინა კვანძი. ამრიგად, სიის დასაწყისში უნდა დავამატოთ sentinel კვანძი. ახლა ჩვენ შეგვიძლია სიაში პირველი კვანძის გავლა (კვანძი sentinel კვანძთან) და შემდეგი ორი პირობის წინაშე ვდგავართ:

1.) კვანძი-> მნიშვნელობა == val: ამ შემთხვევაში, ჩვენ დავაყენებთ წინა-> შემდეგი = კვანძი-> შემდეგი. ეს დააკავშირებს მიმდინარე კვანძს წინა კვანძთან და წაშლის მიმდინარე კვანძს შემდეგის გამოყენებით: წაშლა (მიმდინარეNode)

2.) წინააღმდეგ შემთხვევაში, ჩვენ მხოლოდ მითითებული პრევ = თავი მომავალი კვანძებისთვის.

დასასრულს, sentinel- ის შემდეგი არის საჭირო სია.

განხორციელება უკავშირდება სიაში ელემენტები 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;
}

ჯავა პროგრამა

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), რადგან ჩვენ მხოლოდ მუდმივი მეხსიერების სივრცე გვაქვს.