Spiral Matrix

MedioMatematica e simulazione Array e stringhe

+10

Ti viene data una matrice di interi con m righe e n colonne, fornita come elenco di righe. Restituisci tutti i suoi valori in ordine a spirale.

Inizia dall'angolo in alto a sinistra e procedi verso destra lungo la riga superiore, poi scendi lungo la colonna destra, vai a sinistra lungo la riga inferiore e risali lungo la colonna sinistra. Continua a girare verso l'interno in senso orario finché ogni valore non è stato letto esattamente una volta.

Funzione

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

matrixinteger-2d-array: la griglia di numeri interi, come elenco di righe della stessa lunghezza
Restituisceinteger-array: ogni valore della matrice in ordine a spirale in senso orario, iniziando dall'angolo in alto a sinistra

Vincoli

1 ≤ m, n ≤ 80, dove m = matrix.length e n = matrix[i].length
Ogni riga ha la stessa lunghezza n.
-100 ≤ matrix[i][j] ≤ 100

Esempi

Input: matrix = [[1, 2, 3], [10, 11, 4], [9, 12, 5], [8, 7, 6]]
Output: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
Spiegazione: I valori aumentano lungo la spirale. L’anello esterno mostra 1, 2, 3 lungo il lato superiore, 4, 5, 6 scendendo lungo il lato destro, 7, 8 tornando indietro lungo il lato inferiore e 9, 10 salendo lungo il lato sinistro. Lo strato interno è un’unica colonna, da leggere una sola volta dall’alto verso il basso: 11, 12.

Input: matrix = [[7, 1, 5, 3], [2, 9, -4, 6], [8, 0, 4, -1]]
Output: [7, 1, 5, 3, 6, -1, 4, 0, 8, 2, 9, -4]
Spiegazione: L’anello esterno restituisce 7, 1, 5, 3, poi 6, -1 scendendo lungo il lato destro, 4, 0, 8 tornando lungo il lato inferiore e 2 salendo lungo il lato sinistro. Ciò che rimane è l’unica riga 9, -4, letta una sola volta da sinistra a destra.

+15 test nascosti all’invio

Per approfondire

Puoi restituire invece i valori in ordine antiorario, iniziando dall'angolo in alto a sinistra e scendendo prima lungo la colonna di sinistra?

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

Qui non c’è matematica ingegnosa; il problema è tenere traccia dei valori, ed è proprio lì che le soluzioni si rompono. Ogni angolo va letto una volta sola, non due, e lo strato più interno può essere una sola riga o una sola colonna, dove un giro completo ripasserebbe sugli stessi valori. Puoi procedere come un robot che gira a destra ogni volta che trova la strada bloccata e ricorda quali celle ha letto. Oppure puoi sbucciare la matrice un anello alla volta con quattro limiti che si restringono, senza bisogno di memoria aggiuntiva.

Cammina e gira a destra quando incontri un ostacolo

Intuizione

Immagina un camminatore nella cella in alto a sinistra, rivolto verso destra. Legge la cella in cui si trova, poi prova a fare un passo in avanti. Se quel passo lo porterebbe fuori dalla matrice o su una cella che ha già letto, gira a destra (destra, giù, sinistra, su, poi di nuovo a destra) e fa un passo in quella direzione. Questa regola disegna la spirale: i bordi della matrice fermano il primo giro e le celle già lette fungono da muri per tutti i giri successivi.

Mantieni la direzione come indice d in due piccoli array, dr = [0, 1, 0, -1] e dc = [1, 0, -1, 0], così una svolta a destra è d = (d+1) % 4. Mantieni una griglia booleana seen delle stesse dimensioni della matrice. Nel primo esempio, il camminatore legge 1, 2, 3, incontra il bordo destro e gira verso il basso per leggere 4, 5, 6, gira a sinistra per leggere 7, 8 e verso l'alto per leggere 9, 10. Sopra 10 si trova 1, già letto, quindi gira a destra verso 11. A destra di 11 c'è 4, già letto, quindi gira verso il basso su 12.

Esegui il ciclo esattamente m × n volte, una per cella, e non dovrai mai rilevare la fine. Dopo l'ultima lettura il camminatore potrebbe trovarsi rivolto verso un muro, ma non farà altri passi. Ogni cella viene letta una volta, quindi il tempo è O(m × n). La griglia seen richiede O(m × n) di memoria aggiuntiva, che il prossimo approccio elimina.

Algoritmo

Parti dalla riga 0, colonna 0, rivolto a destra, con una griglia seen interamente impostata su false.
Ripeti m × n volte: aggiungi il valore corrente e segna la sua cella come visitata.
Calcola la cella successiva nella direzione corrente. Se si trova fuori dalla matrice o è già stata visitata, gira a destra e calcola nuovamente la cella.
Spostati in quella cella.
Restituisci i valori nell'ordine in cui li hai aggiunti.

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

Sbuccia gli strati con quattro limiti

Intuizione

La spirale è un insieme di anelli annidati. Descrivi l’anello corrente con quattro limiti: le righe da top a bottom, le colonne da left a right. Un giro legge la riga superiore da left a right, la colonna destra da top+1 fino a bottom, la riga inferiore da right-1 tornando a left e la colonna sinistra da bottom-1 risalendo fino a top+1. Ogni lato inizia una cella dopo la fine del lato precedente, così ogni angolo viene letto esattamente una volta. Poi sposta tutti e quattro i limiti di un passo verso l’interno e ripeti finché top ≤ bottom e left ≤ right.

La difficoltà è un anello spesso una sola riga o una sola colonna, in cui il percorso di ritorno passa su celle già lette. Nel secondo esempio, dopo l’anello esterno i limiti sono top = bottom = 1, left = 1 e right = 2: l’unica riga 9, -4. La riga superiore legge entrambi i valori e la colonna destra non ha celle sotto top. Ma la riga inferiore è quella stessa riga e percorrerla a ritroso aggiungerebbe 9 una seconda volta. Quindi percorri la riga inferiore e la colonna sinistra solo quando top < bottom e left < right. Il terzo esempio è il caso speculare: nell’unica colonna 4, 1, 7, risalire la colonna sinistra leggerebbe di nuovo 1.

Ogni valore viene letto una volta, quindi il tempo è O(m × n), il minimo possibile perché la risposta contiene tutti i valori. Oltre alla risposta, la memoria richiesta è di quattro interi.

Algoritmo

Imposta top = 0, bottom = m-1, left = 0, right = n-1.
Mentre top ≤ bottom e left ≤ right, leggi la riga superiore da left a right e la colonna destra da top+1 a bottom.
Se top < bottom e left < right, leggi la riga inferiore da right-1 a left e la colonna sinistra da bottom-1 a top+1.
Aggiungi uno a top e left, sottrai uno da bottom e right.
Restituisci i valori nell'ordine in cui li hai letti.

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

Trappole e casi limite

I cicli sono brevi, quindi i bug si trovano agli angoli e nell’ultimo strato.

Leggere due volte l’ultimo strato quando è composto da una riga o una colonna. Senza il controllo top < bottom e left < right, il secondo esempio termina con 9, -4, 9 e il terzo legge 4, 1, 7, 1.
Leggere due volte un angolo. Se ogni lato va dalla propria prima cella alla propria ultima cella, ogni angolo viene letto da due lati. Inizia ogni lato una cella dopo il punto in cui è terminato il lato precedente.
Usare il ciclo con top < bottom invece di top ≤ bottom. Ciò interrompe l’esecuzione prima del centro di un quadrato con un numero dispari di lati: in una matrice 3 × 3 il valore centrale non viene mai letto.
Confondere righe e colonne in una matrice non quadrata. Usare matrix.length per entrambi i limiti funziona con ogni test su una matrice quadrata, ma non con uno su una matrice 3 × 4.
Dimenticare gli input sottili: una riga, una colonna, una cella. Ognuno costituisce un singolo strato che non raggiunge mai la riga inferiore o la colonna sinistra.
In R, a:b conta all’indietro quando a > b, quindi un intervallo vuoto come 3:2 restituisce 3, 2 invece di niente; proteggilo oppure usa seq_len. In Lua e R, righe e colonne iniziano da 1.

Domande frequenti4

Qual è la complessità temporale e spaziale di Matrice a spirale?

Entrambi gli approcci leggono ogni valore una sola volta, quindi il tempo è O(m × n), e nessuna soluzione può fare di meglio perché la risposta contiene ogni valore. Sbucciare gli strati con quattro limiti usa O(1) di memoria aggiuntiva oltre alla risposta. La visita che svolta quando incontra un ostacolo usa una griglia O(m × n) per ricordare quali celle ha letto.

Come si evita di leggere due volte un valore durante una visita a spirale?

Ci sono due punti in cui si verificano ripetizioni. Agli angoli, inizia ogni lato una cella dopo la fine del lato precedente, così ogni angolo appartiene a un solo lato. Nell’ultimo strato, leggi la riga inferiore e la colonna sinistra solo quando lo strato ha più di una riga e più di una colonna, perché altrimenti il percorso di ritorno passa sopra celle che hai già letto.

Come si riempie una matrice in ordine a spirale invece di leggerne una?

Usa gli stessi quattro limiti e gli stessi quattro lati, ma scrivi invece di leggere. Mantieni un contatore che parte da 1 e memorizzalo in ogni cella man mano che procedi, incrementandolo ogni volta. Per una matrice n × n il contatore termina a n², e il primo esempio sopra è ciò che si ottiene per una griglia 4 × 3.

Perché svoltare a destra quando il passaggio è bloccato produce una spirale?

Al primo giro, il camminatore svolta ai quattro bordi della matrice. A ogni giro successivo, le celle già lette fungono da pareti, quindi il camminatore svolta una cella prima dell’anello percorso la volta precedente. In questo modo ogni giro resta all’interno del precedente, formando la spirale. Il camminatore non deve mai sapere in quale strato si trova, ma solo se la cella successiva è libera.

Python

def spiralOrder(matrix):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Caso 3

Input

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

Atteso

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