Spiral Matrix

Q: מהי סיבוכיות הזמן והמרחב של מטריצה ספירלית?

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

בינונימתמטיקה וסימולציה מערכים ומחרוזות

+10

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

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

פונקציה

spiralOrder(matrix: integer-2d-array) → integer-array

matrixinteger-2d-array: רשת המספרים השלמים, כרשימה של שורות באורך שווה
מחזירהinteger-array: כל הערכים של המטריצה בסדר ספירלי בכיוון השעון, החל מהפינה השמאלית העליונה

אילוצים

1 ≤ m, n ≤ 80, כאשר m = matrix.length ו-n = matrix[i].length
לכל שורה יש אותו אורך n.
-100 ≤ matrix[i][j] ≤ 100

דוגמאות

קלט: matrix = [[1, 2, 3], [10, 11, 4], [9, 12, 5], [8, 7, 6]]
פלט: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
הסבר: הערכים עולים בספירלה. הטבעת החיצונית מציגה את 1, 2, 3 לאורך החלק העליון, את 4, 5, 6 כלפי מטה בצד ימין, את 7, 8 לאורך החלק התחתון בחזרה ואת 9, 10 כלפי מעלה בצד שמאל. השכבה הפנימית היא עמודה אחת, שקוראים פעם אחת מלמעלה למטה: 11, 12.

קלט: matrix = [[7, 1, 5, 3], [2, 9, -4, 6], [8, 0, 4, -1]]
פלט: [7, 1, 5, 3, 6, -1, 4, 0, 8, 2, 9, -4]
הסבר: הטבעת החיצונית נותנת 7, 1, 5, 3, אחר כך 6, -1 לאורך הצד הימני כלפי מטה, 4, 0, 8 בחזרה לאורך החלק התחתון ו-2 כלפי מעלה בצד השמאלי. מה שנותר הוא השורה היחידה 9, -4, שקוראים פעם אחת משמאל לימין.

+15 בדיקות נסתרות בשליחה

שאלת המשך

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

רמזים

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

נפתחו 0 מתוך 3

פתרון

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

התקדם ופנה ימינה כשנתקלים בחסימה

האינטואיציה

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

שמרו את הכיוון כאינדקס d לתוך שתי מערכים קטנים, dr = [0, 1, 0, -1] ו-dc = [1, 0, -1, 0], כך שפנייה ימינה היא d = (d+1) % 4. שמרו רשת בוליאנית seen בגודל המטריצה. בדוגמה הראשונה הצועד קורא את 1, 2, 3, מגיע לקצה הימני ופונה למטה כדי לקרוא את 4, 5, 6, פונה שמאלה כדי לקרוא את 7, 8 ולמעלה כדי לקרוא את 9, 10. מעל 10 נמצא 1, שכבר נקרא, ולכן הוא פונה ימינה אל 11. מימין ל-11 נמצא 4, שכבר נקרא, ולכן הוא פונה למטה אל 12.

הריצו את הלולאה בדיוק m × n פעמים, פעם אחת לכל תא, ולעולם לא תצטרכו לזהות את הסוף. אחרי הקריאה האחרונה, הצועד עשוי להיות פונה אל קיר, אבל הוא לא יתקדם שוב. כל תא נקרא פעם אחת, ולכן זמן הריצה הוא O(m × n). רשת seen דורשת זיכרון נוסף של O(m × n), שאותו הגישה הבאה חוסכת.

אלגוריתם

התחל בשורה 0, בעמודה 0, כשאתה פונה ימינה, עם רשת seen שכל ערכיה false.
חזור על הפעולה m × n פעמים: הוסף את הערך הנוכחי וסמן את התא שלו כ-seen.
חשב את התא הבא בכיוון הנוכחי. אם הוא מחוץ למטריצה או שכבר סומן, פנה ימינה וחשב אותו שוב.
עבור לתא הזה.
החזר את הערכים לפי הסדר שבו הוספת אותם.

def spiralOrder(matrix):
    rows, cols = len(matrix), len(matrix[0])
    seen = [[False] * cols for _ in range(rows)]
    # Directions in clockwise order: right, down, left, up.
    dr = [0, 1, 0, -1]
    dc = [1, 0, -1, 0]
    r = c = d = 0
    result = []
    for _ in range(rows * cols):
        result.append(matrix[r][c])
        seen[r][c] = True
        nr, nc = r + dr[d], c + dc[d]
        # Blocked by the edge or by a cell already read: turn right.
        if not (0 <= nr < rows and 0 <= nc < cols) or seen[nr][nc]:
            d = (d + 1) % 4
            nr, nc = r + dr[d], c + dc[d]
        r, c = nr, nc
    return result

קלפו את השכבות בעזרת ארבעה גבולות

האינטואיציה

הספירלה היא סדרה של טבעות מקוננות. תארו את הטבעת הנוכחית באמצעות ארבעה גבולות: שורות top עד bottom, עמודות left עד right. בסיבוב אחד קוראים את השורה העליונה מ־left עד right, את העמודה הימנית מ־top+1 כלפי מטה עד bottom, את השורה התחתונה מ־right-1 בחזרה עד left, ואת העמודה השמאלית מ־bottom-1 כלפי מעלה עד top+1. כל צד מתחיל תא אחד אחרי סוף הצד שקדם לו, כך שכל פינה נקראת בדיוק פעם אחת. לאחר מכן מזיזים את כל ארבעת הגבולות צעד אחד פנימה וחוזרים על הפעולה כל עוד top ≤ bottom וגם left ≤ right.

המלכודת היא טבעת שעובייה שורה אחת או עמודה אחת, שבה הדרך חזרה עוברת על תאים שכבר נקראו. בדוגמה השנייה, אחרי הטבעת החיצונית הגבולות הם top = bottom = 1, left = 1 ו־right = 2: השורה היחידה 9, -4. קוראים את שני הערכים בשורה העליונה, ובעמודה הימנית אין תאים מתחת ל־top. אבל השורה התחתונה היא אותה שורה, והליכה לאחור לאורכה תוסיף את 9 פעם נוספת. לכן הולכים לאורך השורה התחתונה והעמודה השמאלית רק כאשר top < bottom וגם left < right. הדוגמה השלישית היא המקרה ההפוך: בעמודה היחידה 4, 1, 7, הליכה חזרה כלפי מעלה לאורך העמודה השמאלית תקרא שוב את 1.

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

אלגוריתם

הגדירו top = 0, bottom = m-1, left = 0, right = n-1.
כל עוד top ≤ bottom וגם left ≤ right, קראו את השורה העליונה מ-left עד right ואת העמודה הימנית מ-top+1 עד bottom.
אם top < bottom וגם left < right, קראו את השורה התחתונה מ-right-1 עד left ואת העמודה השמאלית מ-bottom-1 עד top+1.
הוסיפו אחת ל-top ול-left, והחסירו אחת מ-bottom ומ-right.
החזירו את הערכים לפי סדר הקריאה שלהם.

def spiralOrder(matrix):
    top, bottom = 0, len(matrix) - 1
    left, right = 0, len(matrix[0]) - 1
    result = []
    while top <= bottom and left <= right:
        # Top row, left to right, then right column, top to bottom.
        for c in range(left, right + 1):
            result.append(matrix[top][c])
        for r in range(top + 1, bottom + 1):
            result.append(matrix[r][right])
        # A layer one row or one column thick has no way back:
        # walking back would read the same cells again.
        if top < bottom and left < right:
            # Bottom row, right to left, then left column, bottom to top.
            for c in range(right - 1, left - 1, -1):
                result.append(matrix[bottom][c])
            for r in range(bottom - 1, top, -1):
                result.append(matrix[r][left])
        # Step in to the next layer.
        top += 1
        bottom -= 1
        left += 1
        right -= 1
    return result

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

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

קריאה של השכבה האחרונה פעמיים כשהיא שורה אחת או עמודה אחת. ללא הבדיקה top < bottom ו-left < right, הדוגמה השנייה מסתיימת ב-9, -4, 9 והשלישית קוראת 4, 1, 7, 1.
קריאה של פינה פעמיים. אם כל צלע מתחילה בתא הראשון שלה ומסתיימת בתא האחרון שלה, כל פינה נקראת על ידי שתי צלעות. התחילו כל צלע תא אחד אחרי המקום שבו הצלע הקודמת הסתיימה.
הפעלת הלולאה כל עוד top < bottom במקום top ≤ bottom. כך נעצרים לפני אמצע ריבוע בעל מספר אי-זוגי של שורות: במטריצה בגודל 3 × 3 הערך שבמרכז לעולם אינו נקרא.
בלבול בין שורות לעמודות במטריצה שאינה ריבועית. שימוש ב-matrix.length לשני הגבולות מצליח בכל בדיקה עם מטריצה ריבועית ונכשל במטריצה בגודל 3 × 4.
שכחת מקרי הקלט הצרים: שורה אחת, עמודה אחת, תא אחד. כל אחד מהם הוא שכבה יחידה שלעולם אינה מגיעה לשורה התחתונה או לעמודה השמאלית.
ב-R, הביטוי a:b סופר לאחור כאשר a > b, לכן טווח ריק כמו 3:2 נותן 3, 2 במקום כלום; הוסיפו תנאי שמגן מפני כך או השתמשו ב-seq_len. ב-Lua וב-R, מספור השורות והעמודות מתחיל ב-1.

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

מהי סיבוכיות הזמן והמרחב של מטריצה ספירלית?

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

איך נמנעים מקריאת ערך פעמיים בסריקה ספירלית?

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

איך ממלאים מטריצה בסדר ספירלי במקום לקרוא אותה?

השתמש באותם ארבעת הגבולות ובאותם ארבעת הצדדים, אבל כתוב במקום לקרוא. שמור מונה שמתחיל ב־1 ואחסן אותו בכל תא תוך כדי המעבר, והוסף אחד בכל פעם. עבור מטריצה בגודל n × n המונה מסתיים ב־n², והדוגמה הראשונה שלמעלה היא התוצאה עבור רשת בגודל 4 × 3.

למה פנייה ימינה כשנתקלים בחסימה יוצרת ספירלה?

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

Python

def spiralOrder(matrix):
    # כתבו כאן את הקוד

מקרי בדיקה

מקרה 1

מקרה 2

מקרה 3

קלט

matrix = [[1, 2, 3], [10, 11, 4], [9, 12, 5], [8, 7, 6]]

צפוי

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]