Cüt Leetcode Solutions-da qovşaqları dəyişdirin

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon alma Bloomberg Facebook microsoft
alqoritmlər kodlaşdırma müsahibə müsahibə hazırlığı LeetCode LeetCodeSolutions Bağlı siyahıBaxılıb 43

Bu problemin məqsədi verilmiş qovşaqları dəyişdirməkdir əlaqəli siyahı cüt-cüt, yəni hər iki bitişik düyünü dəyişdirmək. Yalnız siyahı qovşaqlarının dəyərini dəyişdirməyə icazə verilsəydi, problem əhəmiyyətsiz olardı. Beləliklə, qovşaq dəyərlərini dəyişdirməyə icazə verilmir.

misal

1 2 3 4
2 1 4 3
6 7 3
7 6 3

Yanaşma

İki düyünü bir cütə dəyişdirə biləcəyimizi görə bilərik. Buradakı mübadilə göstəricilərlə manipulyasiya etmək deməkdir ki, birinci qovşaq əlaqəli siyahının qalan hissəsinə qoşulacaq və ikinci qovşaq indi olur baş ilk düyünü göstərir.

Leetcode Solutions cütlüyündə bir siyahının qovşaqlarını dəyişdirinPin

Bu mübadildən sonra qalan siyahı, artıq ilkin problemin alt probleminə çevrilir. Beləliklə, eyni rekursiv funksiyanı siyahının qalan hissəsinə zəng edə bilərik. Burada izləməyimiz lazımdır baş İndi siyahının ikinci nodu artıq siyahının. Bu, kifayət qədər bir həlldir, ancaq yer yeyir, çünki rekursiya yaddaşda yığın çərçivələr yaradır.

Optimal metod asanlıqla iterativ şəkildə tətbiq olunan oxşar yanaşma kimi düşünülə bilər. Bu məqsədlə bir əvvəlki əvvəlki cütlüyün quyruğunu saxlayacaq qovşaq dəyişdirdik. Mövcud cütlüyün qovşaqlarını dəyişdirdikdən sonra əvvəlki cütün quyruğunu bu cütün başına bağlayırıq.

Alqoritm (Rekursiv yanaşma)

  1. Sadə əsas şərtlər, cütlük yaratmaq üçün iki qovşaq belə olmadıqda. Bu halda:
    • Siyahı ola bilər NULL və ya bir maddədən ibarət ola bilər.
    • Onu olduğu kimi qaytarın.
  2. İndi bir cütümüz var, istifadə edin ilkikinci cütümüzün birinci və ikinci maddələrini göstərmək.
  3. Bu ildən ilk düyün indi bu cütün quyruğu olacaq,
    1. növbəti cütdən başlayaraq rekursiv funksiyanı çağırın (sonra node) ikinci).
    2. Alt problem funksiya ilə həll olunur və əlavə olunur ilk düyün.
    3. İndi əlavə edin ilk qovluğu da var istirahət ona qoşulmuş siyahının, ikinci node ilə.
  4. İstədiyimiz üçün ikinci ilə dəyişdiriləcək qovşaq birinci, ikinci indi baş olacaq
    1. Qayıtmaq ikinci.

Alqoritm (Optimal)

  1. Bir yaradın əvvəlki bəzi saxta düyünü göstərən bir göstərici, onu qoruyun baş.
  2. Set sonrakı siyahının cari rəhbəri kimi əvvəlki qovşağın.
  3. Bu əvvəlki göstərici növbəti dəyişdirilmiş cütlüyə işarə edə bilər.
  4. Siyahı varsa NULL və ya yalnız bir element var
    • siyahını qaytarın
  5. Siyahının sona çatdığı və ya yalnız bir nodu qaldığı nöqtəyə çatana qədər təkrarlamağa davam edin:
    • Növbəti cütün ünvanını a temp dəyişən.
    • Bu cütdəki iki nodu dəyişdirin: ilk node və ikinci node
    • PrevNode-u bu cütün ikinci nodu ilə birləşdirin
    • PrevNode'u ilk node olaraq yeniləyin (indi quyruq olacağı üçün)
    • Başı = tempini yeniləyin ki, edə bilərik atılmaq növbəti cütə
  6. Siyahı hələ də ola bilər NULL və ya tək bir maddə qala bilər, beləliklə siyahının qalan hissəsi üçün prevNode-u bağlayın.
  7. lazımi siyahını almaq üçün dummy.next qayıdın.

Həyata keçirilməsi

C ++ proqramı, cütlüklərdə qovşaqları dəyişdirmək leetcode həll

Rekursiv yanaşma

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


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

listNode* swapNodesInPairs(listNode* head)
{
    if(head == NULL || head->next == NULL)
        return head;

    listNode* first = head , *second = head->next;
    first->next = swapNodesInPairs(head->next->next);

    second->next = first;
    return second;
}



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

    print(swapNodesInPairs(head));
    return 0;
}

Təkrarlanan yanaşma

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


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


listNode* swapNodesInPairs(listNode* head)
{
    if(head == NULL || head->next == NULL)
        return head;

    //initialise the prevNode
    listNode *prevNode = new listNode(-1) , *prehead = prevNode;
    prevNode->next = head;


    listNode *first , *second , *temp;
    //temporary variable to store first and second of every pair

    while(head != NULL && head->next != NULL)
    {
        first = head;
        second = head->next;

        temp = second->next;
        second->next = first;
        prevNode->next = second;
        //connecting previous node to the second of this pair


        prevNode = first;
        head = temp;
        //reinitialising previous node and head for next pair
    }

    prevNode->next = head;
    return prehead->next;
}


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

    print(swapNodesInPairs(head));
    return 0;
}
2 1 3

Qovşaqları cüt-cüt dəyişdirmək üçün Java proqramı leetcode həlləri

Rekursiv yanaşma

class listNode
{
    int value;
    listNode next;

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

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

    public static listNode swapNodesInPairs(listNode head)
    {
        if(head == null || head.next == null)
            return head;

        listNode first = head , second = head.next;

        first.next = swapNodesInPairs(head.next.next);
        second.next = first;

        return second;
    }

    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(4);

        print(swapNodesInPairs(head));
    }
}

Təkrarlanan yanaşma

class listNode
{
    int value;
    listNode next;

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

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

    public static listNode swapNodesInPairs(listNode head)
    {
        if(head == null || head.next == null)
            return head;

        //initialise the prevNode
        listNode prevNode = new listNode(-1) , prehead = prevNode;
        prevNode.next = head;


        listNode first , second , temp;
        //temporary variable to store first and second of every pair

        while(head != null && head.next != null)
        {
            first = head;
            second = head.next;

            temp = second.next;
            second.next = first;
            prevNode.next = second;
            //connecting previous node to the second of this pair


            prevNode = first;
            head = temp;
            //reinitialising previous node and head for next pair
        }

        prevNode.next = head;
        return prehead.next;
    }

    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(4);

        print(swapNodesInPairs(head));
    }
}
2 1 4 3

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi qovşaqları cüt-cüt dəyişdirmək

Rekursiv yanaşma: O (N), siyahıda yalnız bir keçid etdiyimiz üçün. Təkrarlanan yanaşma: O (N), yenə də tək bir ötürmə edirik.

Kosmik Mürəkkəblik qovşaqları cüt-cüt dəyişdirmək

Rekursiv yanaşma: O (N), çünki rekursiya yaddaşdakı hər zəng üçün yığın çərçivələri yaradır. Təkrarlanan yanaşma: O (1), çünki bəzi dəyişənlər üçün sabit yer istifadə olunur. Təkrarlanan yanaşma budur daha yaxşı.

Şərh yaz

Translate »