החלף צמתים בזוגות פתרונות Leetcode


רמת קושי בינוני
נשאל לעתים קרובות אמזון בעברית תפוח עץ בלומברג פייסבוק מיקרוסופט
רשימה מקושרת

מטרת הבעיה היא להחליף צמתים נתון רשימה מקושרת בזוגות, כלומר החלפת כל שני צמתים סמוכים. אם מותר לנו להחליף רק את ערך צמתי הרשימה, הבעיה תהיה טריוויאלית. לכן, אסור לנו לשנות את ערכי הצומת.

דוגמה

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

גישה

אנו יכולים להבחין כי אנו יכולים להחליף את שני הצמתים בזוג. החלפה כאן פירושה לתפעל את המצביעים כך שהצומת הראשון מחובר לשאר הרשימה המקושרת והצומת השני הופך כעת ראש מצביע על הצומת הראשון.

החלף צמתים של רשימה בזוגות פתרונות Leetcode

הרשימה שנותרה לאחר החלפה זו הופכת כעת לבעיית משנה של הבעיה הראשונית. אז נוכל לקרוא לאותה פונקציה רקורסיבית לשאר הרשימה. כאן, עלינו לעקוב אחר כך שה- ראש של הרשימה הוא למעשה למעשה הצומת השני ברשימה. זהו פיתרון מספיק אך גוזל מקום מכיוון שרקורציה יוצרת מסגרות מחסנית בזיכרון.

ניתן לחשוב בקלות על השיטה האופטימלית כגישה דומה המיושמת באופן איטרטיבי. לשם כך עלינו ליצור קודם צומת שיאחסן את הזנב של הזוג הקודם שהחלפנו. לאחר החלפת הצמתים של הזוג הנוכחי, אנו מחברים את הזנב של הזוג הקודם לראש הזוג הזה.

אלגוריתם (גישה רקורסיבית)

  1. תנאי בסיס פשוטים הם כאשר אין אפילו שני צמתים ליצירת זוג. במקרה הזה:
    • הרשימה יכולה להיות NULL או יכול לכלול פריט אחד.
    • החזירו אותו כמו שהוא.
  2. עכשיו שיש לנו זוג, השתמש א ו שני לציון פריטים ראשונים ושניים של הזוג שלנו.
  3. מאז א צומת יהפוך כעת לזנב של הזוג הזה,
    1. קוראים לפונקציה הרקורסיבית החל מהזוג הבא (צומת אחרי שני).
    2. בעיית המשנה נפתרת על ידי הפונקציה ומוסיפה אותה א צוֹמֶת.
    3. עכשיו, צרף את א צומת, שיש בו גם את שאר של הרשימה המחוברת אליו, לצומת השני.
  4. מכיוון שאנחנו רוצים את שני צומת שאפשר להחליף איתו שנייה ראשונה יהפוך לראש עכשיו,
    1. לחזור שְׁנִיָה.

אלגוריתם (אופטימלי)

  1. צור קודם מצביע שמצביע על צומת דמה כלשהו, ​​לשמור על מראש.
  2. לקבוע הבא של הצומת הקודם כראש הרשימה הנוכחי.
  3. המצביע הקודם הזה יכול להצביע על הזוג שהוחלף הבא.
  4. אם הרשימה היא NULL או שיש בו רק אלמנט אחד
    • להחזיר את הרשימה
  5. המשיכו לחזור עד שנגיע לנקודה בה הרשימה מסתיימת או שנשאר רק צומת אחד:
    • אחסן את כתובת הזוג הבא ב- טמפ משתנה
    • החלף את שני הצמתים בזוג זה: הצומת הראשון והצומת השני
    • חבר את הקוד הקודם לצומת השני של זוג זה
    • עדכן את הקוד הקודם כצומת הראשון (מכיוון שהוא יהפוך לזנב עכשיו)
    • עדכן ראש = temp כך שנוכל לקפוץ לזוג הבא
  6. הרשימה עדיין יכולה להיות NULL או יכול להישאר פריט בודד, אז חבר את קוד הקוד לשאר הרשימה.
  7. החזר dummy.next כדי לקבל את הרשימה הנדרשת.

יישום

תוכנית C ++ להחלפת צמתים בזוגות פתרון leetcode

גישה רקורסיבית

#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;
}

גישה איטרטיבית

#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

תוכנית Java להחלפת צמתים בזוגות פתרונות leetcode

גישה רקורסיבית

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));
    }
}

גישה איטרטיבית

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

ניתוח מורכבות

מורכבות זמן להחליף צמתים בזוגות

גישה רקורסיבית: עַל), שכן אנו מבצעים רק מעבר אחד ברשימה. גישה איטרטיבית: עַל), שוב אנו מבצעים מעבר יחיד.

מורכבות בחלל להחליף צמתים בזוגות

גישה רקורסיבית: עַל), שכן הרקורסיה יוצרת מסגרות מחסנית לכל שיחה בזיכרון. גישה איטרטיבית: O (1), כמרווח קבוע משמש לכמה משתנים. כאן נמצאת הגישה האיטרטיבית מוטב.