Reverse Nodes in k-Group

Q: מהי סיבוכיות הזמן והמקום של היפוך צמתים בקבוצות של k?

היא פועלת בזמן O(L) עבור רשימה של L צמתים: כל צומת נספר פעם אחת והופך פעם אחת. הגרסה שפועלת במקום משתמשת בזיכרון נוסף של O(1); העתקת הערכים למערך משתמשת ב-O(L).

Q: מה קורה לקבוצה האחרונה אם יש בה פחות מ־k צמתים?

הוא שומר על הסדר המקורי. ספרו k צמתים לפני היפוך כל קבוצה; אם מגיעים קודם לסוף הרשימה, השאירו את השאר כפי שהם.

קשהרשימה מקושרת

+10

רשימה מקושרת חד-כיוונית מאוחסנת בשני מערכים בעלי אותו אורך. צומת i מכיל את values[i] ומקושר לצומת next[i]; הערך -1 מסיים את הרשימה, והראש הוא צומת 0. הצמתים עשויים להיות מאוחסנים בכל סדר, לכן יש לעקוב אחר הקישורים ולא אחר סדר המערך.

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

פונקציה

reverseKGroup(next: integer-array, values: integer-array, k: integer) → integer-array

nextinteger-array: האינדקס של הצומת שאליו כל צומת מקשר, או ‎-1 עבור הצומת האחרון
valuesinteger-array: הערך שמכיל כל צומת
kinteger: מספר הצמתים בכל קבוצה שיש להפוך את סדרם
מחזירהinteger-array: הערכים לפי הסדר החדש ברשימה

אילוצים

1 ≤ L ≤ 5000, כאשר L הוא האורך של next ושל values.
-1000 ≤ values[i] ≤ 1000
1 ≤ k ≤ L
כל next[i] הוא -1 או אינדקס של צומת מ־0 עד L-1.
החל מהצומת 0, הרשימה מבקרת בכל צומת בדיוק פעם אחת ואז מגיעה ל־-1. אין מעגל.

דוגמאות

קלט: next = [2, 3, 4, -1, 1]values = [1, 4, 2, 5, 3]k = 2
פלט: [2, 1, 4, 3, 5]
הסבר: הרשימה נקראת 1, 2, 3, 4, 5 (צמתים 0, 2, 4, 1, 3). הזוגות 1, 2 ו-3, 4 הפוכים, ו-5 לבדו קצר מ-k = 2, ולכן הוא נשאר אחרון.

קלט: next = [5, 3, 6, -1, 7, 2, 4, 1]values = [10, 70, 30, 80, 50, 20, 40, 60]k = 3
פלט: [30, 20, 10, 60, 50, 40, 70, 80]
הסבר: הרשימה קוראת 10, 20, ..., 80. הקבוצות 10, 20, 30 ו-40, 50, 60 הפוכות. 70, 80 קצרה יותר מ-k = 3, ולכן היא שומרת על הסדר שלה.

קלט: next = [2, -1, 1]values = [7, 9, 3]k = 3
פלט: [9, 3, 7]
הסבר: המערך נקרא 7, 9, 3, אבל הרשימה נקראת 7, 3, 9. כאשר k שווה לאורך, כל הרשימה היא קבוצה אחת ויוצאת הפוכה: 9, 3, 7.

שאלת המשך

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

רמזים

פתחו אותם אחד אחד. כל רמז חושף קצת יותר.

נפתחו 0 מתוך 3

פתרון

היפוך של רשימה שלמה מתבצע במעבר אחד של היפוכי קישורים. כאן ההיפוכים נעצרים כל k צמתים, ויש לחבר כל קבוצה שהופכת לחלק שלפניה ולצמתים שאחריה. אפשר להעתיק את הערכים למערך ולהפוך קבוצות, או לקשר מחדש כל קבוצה במקומה תוך שימוש בזיכרון נוסף של O(1).

העתיקו את הערכים והפכו את הסדר של כל בלוק

האינטואיציה

עבור מצומת 0 באמצעות node = next[node] והעתק את הערכים למערך לפי סדר הרשימה. כעת הקבוצות הן מקטעי האינדקסים 0 עד k-1, k עד 2k-1, וכן הלאה: הפוך כל מקטע שנכנס בשלמותו, והשאר מקטע אחרון קצר יותר ללא שינוי. הפעולה אורכת זמן O(L) וזיכרון נוסף O(L), והיא לעולם אינה נוגעת בקישור.

אלגוריתם

עבור מהצומת 0 עד -1 והוסף את values[node] למערך.
עבור start = 0, k, 2k, ... כל עוד start + k ≤ L: הפוך את הבלוק מאינדקס start עד start+k-1.
השאר בלוק קצר יותר בסוף כפי שהוא.
החזר את המערך.

def reverseKGroup(next, values, k):
    # Read the values in list order.
    order = []
    node = 0
    while node != -1:
        order.append(values[node])
        node = next[node]
    # Reverse every full block of k; a shorter last block stays as it is.
    for start in range(0, len(order) - k + 1, k):
        order[start:start + k] = order[start:start + k][::-1]
    return order

הפוך כל קבוצה במקומה על ידי חיבור מחדש

האינטואיציה

כדי להפוך רשימה שלמה, עוברים עליה עם prev ועם node ומגדירים next[node] = prev. קבוצה היא אותה לולאה שרצה k פעמים, כאשר prev מתחיל ב-after, הצומת שמופיע מיד אחרי הקבוצה. הצומת הראשון בקבוצה הופך לאחרון שלה ומקושר ל-after, כך ששאר הרשימה נשארת מחוברת.

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

עוברים על כל צומת פעמיים, פעם אחת לספירה ופעם אחת להיפוך: זמן O(L) וכמה מספרים שלמים בזיכרון (O(L) ב-R, שמעתיקה את וקטור הקישורים בשינוי הראשון שלו).

אלגוריתם

התחל עם head = 0, prevTail = -1, groupStart = 0.
התקדם k צעדים מ־groupStart אל after; אם הגעת ל־-1 קודם, עבור לשלב 5.
כאשר prev = after ו־node = groupStart, חזור k פעמים: שמור את next[node], הגדר next[node] = prev, והתקדם עם שניהם.
אם prevTail הוא -1, הגדר head = prev; אחרת הגדר next[prevTail] = prev. הגדר prevTail = groupStart, groupStart = after; עבור לשלב 2.
אסוף את הערכים החל מ־head.

def reverseKGroup(next, values, k):
    head = 0           # the list's head; changes after the first group
    prev_tail = -1     # last node of the groups already reversed
    group_start = 0
    while True:
        # Find the node right after this group, or stop if fewer than k remain.
        after, count = group_start, 0
        while after != -1 and count < k:
            after = next[after]
            count += 1
        if count < k:
            break
        # Turn the group's k links around. Its first node ends up last
        # and links to the node after the group.
        prev, node = after, group_start
        for _ in range(k):
            following = next[node]
            next[node] = prev
            prev, node = node, following
        # prev is the group's new first node: hang it after the previous group.
        if prev_tail == -1:
            head = prev
        else:
            next[prev_tail] = prev
        prev_tail = group_start
        group_start = after
    # Walk the relinked list from its head.
    result = []
    node = head
    while node != -1:
        result.append(values[node])
        node = next[node]
    return result

מלכודות ומקרי קצה

היפוך הקבוצה הקצרה האחרונה. סופרים k צמתים לפני ההיפוך; אי אפשר לבטל קישור שהתהפך בלי מעבר נוסף.
מתחילים את ההיפוך עם prev = -1, כמו בהיפוך מלא. הזנב הקצר נושר: הדוגמה הראשונה מחזירה 2, 1, 4, 3.
לא מקשרים את הצומת האחרון בקבוצה הקודמת לצומת הראשון החדש. הוא עדיין מצביע על הצומת הראשון הישן, ולכן k-1 צמתים נעלמים.
קוראים את התשובה מהצומת 0, או קוראים את values משמאל לימין. אחרי שקבוצה של k ≥ 2 מתהפכת, הצומת 0 אינו הראש, וסדר המערך מעולם לא היה סדר הרשימה.
משתמשים באינדקסים שמתחילים מ־0 ב־Lua וב־R, שהמערכים שלהן מתחילים מ־1. שומרים על אינדקסי צמתים שמתחילים מ־0 וקוראים next[node + 1].

שאלות נפוצות3

מהי סיבוכיות הזמן והמקום של היפוך צמתים בקבוצות של k?

היא פועלת בזמן O(L) עבור רשימה של L צמתים: כל צומת נספר פעם אחת והופך פעם אחת. הגרסה שפועלת במקום משתמשת בזיכרון נוסף של O(1); העתקת הערכים למערך משתמשת ב-O(L).

מה קורה לקבוצה האחרונה אם יש בה פחות מ־k צמתים?

הוא שומר על הסדר המקורי. ספרו k צמתים לפני היפוך כל קבוצה; אם מגיעים קודם לסוף הרשימה, השאירו את השאר כפי שהם.

למה פתרונות לבעיה הזו משתמשים בצומת דמה?

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

def reverseKGroup(next, values, k):
    # כתבו כאן את הקוד

בדיקה #1

בדיקה #2

בדיקה #3

ארגומנטים

next = [2, 3, 4, -1, 1]
values = [1, 4, 2, 5, 3]
k = 2

הפלט הצפוי

[2, 1, 4, 3, 5]