Spiral Matrix

ŚrednieMatematyka i symulacja Tablice i napisy

+10

Otrzymujesz macierz liczb całkowitych z m wierszami i n kolumnami, podaną jako lista wierszy. Zwróć wszystkie jej wartości w kolejności spiralnej.

Zacznij w lewym górnym rogu i idź w prawo wzdłuż górnego wiersza, następnie w dół wzdłuż prawej kolumny, w lewo wzdłuż dolnego wiersza i w górę wzdłuż lewej kolumny. Kontynuuj ruch zgodnie z ruchem wskazówek zegara, zataczając coraz mniejsze kręgi, aż każda wartość zostanie odczytana dokładnie raz.

Funkcja

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

matrixinteger-2d-array: siatka liczb całkowitych w postaci listy wierszy o jednakowej długości
Zwracainteger-array: każda wartość macierzy w kolejności zgodnej z ruchem wskazówek zegara, zaczynając od lewego górnego rogu

Ograniczenia

1 ≤ m, n ≤ 80, gdzie m = matrix.length i n = matrix[i].length
Każdy wiersz ma tę samą długość n.
-100 ≤ matrix[i][j] ≤ 100

Przykłady

Wejście: matrix = [[1, 2, 3], [10, 11, 4], [9, 12, 5], [8, 7, 6]]
Wyjście: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
Wyjaśnienie: Wartości rosną wzdłuż spirali. Na zewnętrznym pierścieniu odczytujemy 1, 2, 3 wzdłuż górnej krawędzi, 4, 5, 6 w dół po prawej, 7, 8 z powrotem wzdłuż dolnej krawędzi, a 9, 10 w górę po lewej. Warstwa wewnętrzna to pojedyncza kolumna, którą odczytujemy raz od góry do dołu: 11, 12.

Wejście: matrix = [[7, 1, 5, 3], [2, 9, -4, 6], [8, 0, 4, -1]]
Wyjście: [7, 1, 5, 3, 6, -1, 4, 0, 8, 2, 9, -4]
Wyjaśnienie: Zewnętrzny pierścień daje 7, 1, 5, 3, następnie 6, -1 w dół po prawej stronie, 4, 0, 8 z powrotem wzdłuż dolnej krawędzi i 2 w górę po lewej. Pozostaje pojedynczy wiersz 9, -4, odczytywany raz od lewej do prawej.

+15 ukrytych testów przy wysłaniu

Pytanie dodatkowe

Czy możesz zamiast tego zwrócić wartości w kierunku przeciwnym do ruchu wskazówek zegara, zaczynając od lewego górnego rogu i najpierw przechodząc w dół lewej kolumny?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Nie ma tu żadnej sprytnej matematyki; problem polega na pilnowaniu szczegółów, a właśnie w tym miejscu rozwiązania zawodzą. Każdy narożnik trzeba odczytać raz, a nie dwa razy, a najbardziej wewnętrzna warstwa może składać się z jednego wiersza lub jednej kolumny, po której pełne okrążenie przeszłoby ponownie po tych samych wartościach. Możesz poruszać się jak robot, który skręca w prawo, gdy napotka przeszkodę, i pamięta, które komórki już odczytał. Możesz też obierać macierz, pierścień po pierścieniu, za pomocą czterech zmniejszających się granic, co nie wymaga dodatkowej pamięci.

Idź i skręć w prawo, gdy napotkasz przeszkodę

Intuicja

Wyobraź sobie wędrowca w lewym górnym polu, zwróconego w prawo. Odczytuje pole, na którym stoi, a następnie próbuje zrobić krok naprzód. Jeśli ten krok oznaczałby wyjście poza macierz lub wejście na pole, które już odczytał, skręca w prawo (w prawo, w dół, w lewo, w górę, a potem znów w prawo) i zamiast tego idzie w tym kierunku. Ta zasada rysuje spiralę: krawędzie macierzy zatrzymują pierwsze okrążenie, a dotychczas odczytane pola działają jak ściany podczas każdego kolejnego okrążenia.

Przechowuj kierunek jako indeks d w dwóch małych tablicach: dr = [0, 1, 0, -1] i dc = [1, 0, -1, 0], dzięki czemu skręt w prawo to d = (d+1) % 4. Przygotuj siatkę wartości logicznych seen o rozmiarze macierzy. W pierwszym przykładzie wędrowiec odczytuje 1, 2, 3, napotyka prawą krawędź i skręca w dół, odczytując 4, 5, 6, skręca w lewo, odczytując 7, 8, a następnie w górę, odczytując 9, 10. Nad 10 znajduje się 1, już odczytane, więc wędrowiec skręca w prawo i przechodzi na 11. Na prawo od 11 znajduje się 4, już odczytane, więc skręca w dół i przechodzi na 12.

Wykonaj pętlę dokładnie m × n razy, po jednym razie na każde pole, a nie trzeba będzie wykrywać końca. Po ostatnim odczycie wędrowiec może być zwrócony w stronę ściany, ale nie wykona już kolejnego kroku. Każde pole jest odczytywane raz, więc złożoność czasowa wynosi O(m × n). Siatka seen wymaga dodatkowej pamięci rzędu O(m × n), którą eliminuje następne podejście.

Algorytm

Rozpocznij w wierszu 0, kolumnie 0, zwrócony w prawo, z siatką seen, w której wszystkie wartości są fałszywe.
Powtórz m × n razy: dodaj bieżącą wartość i oznacz jej komórkę jako odwiedzoną.
Oblicz następną komórkę w bieżącym kierunku. Jeśli znajduje się poza macierzą lub została już odwiedzona, skręć w prawo i oblicz ją ponownie.
Przejdź do tej komórki.
Zwróć wartości w kolejności, w jakiej je dodano.

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

Obierz warstwy za pomocą czterech granic

Intuicja

Spirala to zbiór zagnieżdżonych pierścieni. Opisz bieżący pierścień za pomocą czterech granic: wiersze od top do bottom, kolumny od left do right. Jeden obieg odczytuje górny wiersz od left do right, prawą kolumnę od top+1 w dół do bottom, dolny wiersz od right-1 z powrotem do left, a lewą kolumnę od bottom-1 w górę do top+1. Każdy bok zaczyna się o jedną komórkę za końcem poprzedniego boku, więc każdy narożnik jest odczytywany dokładnie raz. Następnie przesuń wszystkie cztery granice o jeden krok do środka i powtarzaj, dopóki top ≤ bottom i left ≤ right.

Pułapką jest pierścień o grubości zaledwie jednego wiersza lub jednej kolumny, w którym droga powrotna przebiega przez już odczytane komórki. W drugim przykładzie po przejściu zewnętrznego pierścienia granice wynoszą top = bottom = 1, left = 1 i right = 2: pojedynczy wiersz 9, -4. Górny wiersz odczytuje obie wartości, a prawa kolumna nie ma nic poniżej top. Dolny wiersz jest jednak tym samym wierszem, a przejście po nim z powrotem dodałoby 9 po raz drugi. Dlatego przechodź po dolnym wierszu i lewej kolumnie tylko wtedy, gdy top < bottom i left < right. Trzeci przykład przedstawia przypadek odwrotny: w pojedynczej kolumnie 4, 1, 7 powrót w górę lewą kolumną odczytałby ponownie 1.

Każda wartość jest odczytywana raz, więc czas działania wynosi O(m × n) — to najmniejsza możliwa wartość, ponieważ odpowiedź zawiera wszystkie wartości. Poza pamięcią potrzebną na odpowiedź potrzeba czterech liczb całkowitych.

Algorytm

Ustaw top = 0, bottom = m-1, left = 0, right = n-1.
Dopóki top ≤ bottom i left ≤ right, odczytaj górny wiersz od left do right oraz prawą kolumnę od top+1 do bottom.
Jeśli top < bottom i left < right, odczytaj dolny wiersz od right-1 do left oraz lewą kolumnę od bottom-1 do top+1.
Dodaj jeden do top i left, odejmij jeden od bottom i right.
Zwróć wartości w kolejności, w jakiej zostały odczytane.

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

Pułapki i przypadki brzegowe

Pętle są krótkie, więc błędy kryją się w narożnikach i ostatniej warstwie.

Dwukrotne odczytanie ostatniej warstwy, gdy ma jeden wiersz lub jedną kolumnę. Bez sprawdzenia top < bottom i left < right drugi przykład kończy się na 9, -4, 9, a trzeci odczytuje 4, 1, 7, 1.
Dwukrotne odczytanie narożnika. Jeśli każdy bok biegnie od swojej pierwszej komórki do ostatniej, każdy narożnik zostanie odczytany przez dwa boki. Rozpocznij każdy bok o jedną komórkę za miejscem, w którym kończy się poprzedni.
Użycie pętli z warunkiem top < bottom zamiast top ≤ bottom. Pętla zatrzymuje się przed środkiem kwadratu o nieparzystym boku: w macierzy 3 × 3 wartość środkowa nigdy nie zostaje odczytana.
Pomylenie wierszy i kolumn w macierzy, która nie jest kwadratem. Użycie matrix.length dla obu granic działa dla każdej testowej macierzy kwadratowej, ale zawodzi dla macierzy 3 × 4.
Pomijanie macierzy o małych wymiarach: jednego wiersza, jednej kolumny lub jednej komórki. Każda z nich składa się z jednej warstwy, która nigdy nie dociera do dolnego wiersza ani lewej kolumny.
W R wyrażenie a:b odlicza w dół, gdy a > b, więc pusty zakres, taki jak 3:2, daje 3, 2 zamiast niczego; zabezpiecz go lub użyj seq_len. W Lua i R indeksowanie wierszy i kolumn zaczyna się od 1.

Najczęstsze pytania4

Jaka jest złożoność czasowa i pamięciowa problemu „Spiral Matrix”?

Oba podejścia odczytują każdą wartość tylko raz, więc złożoność czasowa wynosi O(m × n), a żadne rozwiązanie nie może być lepsze, ponieważ odpowiedź zawiera każdą wartość. Odczytywanie warstw przy użyciu czterech granic wymaga O(1) dodatkowej pamięci poza odpowiedzią. Przechodzenie z zakrętem po napotkaniu przeszkody używa siatki O(m × n), aby zapamiętać, które komórki zostały odczytane.

Jak uniknąć dwukrotnego odczytania wartości podczas przechodzenia spiralnego?

Powtórzenia pojawiają się w dwóch miejscach. W narożnikach zacznij każdy bok o jedną komórkę dalej niż kończył się poprzedni bok, aby każdy narożnik należał tylko do jednego boku. W ostatniej warstwie odczytuj dolny wiersz i lewą kolumnę tylko wtedy, gdy warstwa ma więcej niż jeden wiersz i więcej niż jedną kolumnę, ponieważ w przeciwnym razie droga powrotna przebiega przez komórki, które zostały już odczytane.

Jak wypełnić macierz spiralnie, zamiast ją odczytywać?

Użyj tych samych czterech granic i tych samych czterech boków, ale zamiast odczytywać, zapisuj. Utrzymuj licznik zaczynający się od 1 i zapisuj jego wartość w każdej komórce, którą mijasz, za każdym razem zwiększając go o jeden. W przypadku macierzy n × n licznik kończy na wartości n², a pierwszy przykład powyżej pokazuje wynik dla siatki 4 × 3.

Dlaczego skręt w prawo, gdy droga jest zablokowana, powoduje powstanie spirali?

Na pierwszym okrążeniu wędrowiec skręca przy czterech krawędziach macierzy. Podczas każdego kolejnego okrążenia komórki odczytane wcześniej działają jak ściany, więc każde okrążenie skręca o jedną komórkę przed pierścieniem, który wędrowiec przeszedł poprzednio. Dzięki temu każde okrążenie pozostaje wewnątrz poprzedniego, tworząc spiralę. Wędrowiec nie musi wiedzieć, na której warstwie się znajduje — wystarczy, że sprawdzi, czy następna komórka jest wolna.

Python

def spiralOrder(matrix):
    # Wpisz kod tutaj

Przypadki testowe

Przypadek 1

Przypadek 2

Przypadek 3

Wejście

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

Oczekiwane

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