Spiral Matrix

OrtaMatematik ve simülasyon Diziler ve dizgiler

+10

m satır ve n sütundan oluşan, satırların listesi olarak verilen bir tamsayı matrisi alırsın. Tüm değerlerini spiral sırayla döndür.

Sol üst köşeden başla ve üst satır boyunca sağa ilerle, ardından sağ sütun boyunca aşağı, alt satır boyunca sola ve sol sütun boyunca yukarı git. Her değer tam olarak bir kez okunana kadar saat yönünde içe doğru dönmeye devam et.

Fonksiyon

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

matrixinteger-2d-array: eşit uzunluktaki satırlardan oluşan bir liste olarak tamsayı ızgarası
Döndürürinteger-array: matrisin her bir değeri, sol üst köşeden başlayarak saat yönünde spiral sırayla

Kısıtlar

1 ≤ m, n ≤ 80; burada m = matrix.length ve n = matrix[i].length
Her satırın uzunluğu n ile aynıdır.
-100 ≤ matrix[i][j] ≤ 100

Örnekler

Girdi: matrix = [[1, 2, 3], [10, 11, 4], [9, 12, 5], [8, 7, 6]]
Çıktı: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
Açıklama: Değerler spiral boyunca sayarak ilerler. Dış halkada üst tarafta 1, 2, 3, sağ tarafta aşağı doğru 4, 5, 6, alt tarafta geriye doğru 7, 8 ve sol tarafta yukarı doğru 9, 10 okunur. İç katman tek bir sütundur ve yukarıdan aşağıya bir kez okunur: 11, 12.

Girdi: matrix = [[7, 1, 5, 3], [2, 9, -4, 6], [8, 0, 4, -1]]
Çıktı: [7, 1, 5, 3, 6, -1, 4, 0, 8, 2, 9, -4]
Açıklama: Dış halka 7, 1, 5, 3 değerlerini verir; ardından sağ taraftan aşağı doğru 6, -1, alt kısım boyunca geri dönerek 4, 0, 8 ve sol taraftan yukarı doğru 2 gelir. Geriye, soldan sağa bir kez okunan tek satır 9, -4 kalır.

Gönderirken +15 gizli test

Ek soru

Değerleri bunun yerine saat yönünün tersine, sol sütunda aşağı doğru ilerleyerek sol üst köşeden başlayıp döndürebilir misin?

İpuçları

Tek tek açın. Her biri biraz daha fazlasını gösterir.

3 ipucundan 0 açıldı

Çözüm

Burada zekice bir matematik yok; sorun kayıt tutmakta ve çözümlerin bozulduğu yer de kayıt tutma aşamasıdır. Her köşe iki kez değil, bir kez okunmalıdır ve en içteki katman tek bir satır ya da tek bir sütun olabilir; bu durumda tam bir tur, aynı değerlerin üzerinden yeniden geçer. Engellendiğinde sağa dönen ve okuduğu hücreleri hatırlayan bir robot gibi ilerleyebilirsin. Ya da matrisi, ek bellek gerektirmeyen dört daralan sınır kullanarak her seferinde bir halkasını soyarak ilerleyebilirsin.

Engel olduğunda yürü ve sağa dön

Sezgi

Sağ üst köşede, sağa bakan bir yürüyeni gözünde canlandır. Üzerinde durduğu hücreyi okur, sonra ileri doğru adım atmaya çalışır. Bu adım matrisin dışına çıkmasına veya daha önce okuduğu bir hücreye basmasına neden olacaksa sağa döner (sağ, aşağı, sol, yukarı, sonra tekrar sağ) ve onun yerine o yönde adım atar. Bu kural spirali çizer: matrisin kenarları ilk turu durdurur, şimdiye kadar okunan hücreler ise sonraki her tur için duvar görevi görür.

Yönü, iki küçük diziye indeks olarak kullanacağın d değişkeninde tut: dr = [0, 1, 0, -1] ve dc = [1, 0, -1, 0]. Böylece sağa dönüş d = (d+1) % 4 olur. Matris boyutunda bir boolean seen ızgarası tut. İlk örnekte yürüyen 1, 2, 3 değerlerini okur, sağ kenara gelince aşağı döner ve 4, 5, 6 değerlerini okur; sola dönüp 7, 8 değerlerini, ardından yukarı dönüp 9, 10 değerlerini okur. 10 değerinin üstünde, daha önce okunmuş olan 1 bulunur; bu yüzden sağa dönerek 11 hücresine geçer. 11 hücresinin sağında, okunmuş olan 4 vardır; bu yüzden aşağı dönerek 12 hücresine geçer.

Döngüyü tam olarak m × n kez, her hücre için bir kez çalıştır; böylece sonu algılaman gerekmez. Son okumadan sonra yürüyen bir duvara dönük olabilir ama bir daha adım atmaz. Her hücre bir kez okunur, dolayısıyla zaman karmaşıklığı O(m × n) olur. seen ızgarası O(m × n) ek bellek kullanır; sonraki yaklaşım bu gereksinimi ortadan kaldırır.

Algoritma

0. satırdan, 0. sütundan, sağa bakacak şekilde ve tüm hücreleri false olan bir seen ızgarasıyla başla.
m × n kez tekrarla: geçerli değeri ekle ve hücresini ziyaret edilmiş olarak işaretle.
Geçerli yönde bir sonraki hücreyi hesapla. Matrisin dışındaysa veya zaten ziyaret edilmişse sağa dön ve hücreyi yeniden hesapla.
O hücreye ilerle.
Değerleri eklediğin sırayla döndür.

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

Dört sınırla katmanları soy

Sezgi

Spiral, iç içe geçmiş halkalardan oluşur. Geçerli halkayı dört sınırla tanımlayın: top ile bottom arasındaki satırlar, left ile right arasındaki sütunlar. Bir turda üst satır left noktasından right noktasına, sağ sütun top+1 noktasından bottom noktasına doğru, alt satır right-1 noktasından left noktasına geri ve sol sütun bottom-1 noktasından top+1 noktasına doğru okunur. Her kenar, önceki kenarın bittiği noktanın bir hücre ötesinden başlar; böylece her köşe tam olarak bir kez okunur. Ardından dört sınırı da bir adım içeri taşıyın ve top ≤ bottom ve left ≤ right olduğu sürece tekrarlayın.

Buradaki tuzak, yalnızca bir satır veya bir sütun kalınlığında olan bir halkadır; bu durumda geri dönüş yolu daha önce okunmuş hücrelerin üzerinden geçer. İkinci örnekte, dış halkadan sonra sınırlar top = bottom = 1, left = 1 ve right = 2 olur: tek satır 9, -4. Üst satır her iki değeri de okur ve sağ sütunda top değerinin altında hiçbir şey yoktur. Ancak alt satır aynı satırdır ve bu satırda geri yürümek 9 değerini ikinci kez ekler. Bu nedenle, alt satırı ve sol sütunu yalnızca top < bottom ve left < right olduğunda yürüyün. Üçüncü örnek bunun simetrik durumudur: tek sütunda 4, 1, 7, sol sütunda yukarı doğru yürümek 1 değerini yeniden okur.

Her değer bir kez okunur; bu nedenle süre O(m × n) olur. Yanıt her değeri içerdiğinden bu mümkün olan en düşük süredir. Yanıtın dışında bellek kullanımı dört tam sayıdır.

Algoritma

top = 0, bottom = m-1, left = 0, right = n-1 olarak ayarla.
top ≤ bottom ve left ≤ right olduğu sürece, üst satırı left değerinden right değerine kadar ve sağ sütunu top+1 değerinden bottom değerine kadar oku.
top < bottom ve left < right ise, alt satırı right-1 değerinden left değerine kadar ve sol sütunu bottom-1 değerinden top+1 değerine kadar oku.
top ve left değerlerini bir artır, bottom ve right değerlerini bir azalt.
Değerleri okuduğun sırayla döndür.

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

Tuzaklar ve uç durumlar

Döngüler kısa olduğundan hatalar köşelerde ve son katmanda ortaya çıkar.

Son katmanı, tek satır ya da tek sütundan oluştuğunda iki kez okumak. top < bottom ve left < right kontrolleri olmadan ikinci örnek 9, -4, 9 ile biter, üçüncü örnek ise 4, 1, 7, 1 değerlerini okur.
Bir köşeyi iki kez okumak. Her kenar kendi ilk hücresinden son hücresine kadar ilerlerse her köşe iki kenar tarafından okunur. Her kenara, önceki kenarın bittiği hücreden bir hücre sonra başlayın.
top ≤ bottom yerine top < bottom koşuluyla döngü kurmak. Bu, tek sayılı bir karenin ortasına ulaşmadan durur: 3 × 3 bir matriste merkez değeri hiç okunmaz.
Kare olmayan bir matriste satırlarla sütunları karıştırmak. Her iki sınır için de matrix.length kullanmak, tüm kare testlerde işe yarar ama 3 × 4 boyutunda bir matriste başarısız olur.
İnce girdileri unutmak: tek satır, tek sütun, tek hücre. Bunların her biri, alt satıra veya sol sütuna hiç ulaşmayan tek bir katmandır.
R'de a > b olduğunda a:b geriye doğru sayar; bu nedenle 3:2 gibi boş bir aralık hiçbir şey yerine 3, 2 verir. Bu durumu koşulla denetleyin veya seq_len kullanın. Lua ve R'de satır ve sütunlar 1'den başlar.

Sıkça sorulan sorular4

Spiral Matrix'in zaman ve alan karmaşıklığı nedir?

Her iki yaklaşım da her değeri bir kez okur, dolayısıyla zaman karmaşıklığı O(m × n) olur ve yanıt her değeri içerdiğinden hiçbir çözüm daha iyisini yapamaz. Dört sınır kullanarak katmanları soymak, yanıt dışında O(1) ek bellek kullanır. Engelle karşılaşınca yön değiştiren yürüyüş, okuduğu hücreleri hatırlamak için O(m × n) boyutunda bir ızgara kullanır.

Spiral dolaşımda bir değeri iki kez okumaktan nasıl kaçınırsınız?

Tekrarlara iki nokta neden olur. Köşelerde, her kenarı bir önceki kenarın bittiği hücreden bir hücre sonra başlat; böylece her köşe yalnızca bir kenara ait olur. Son katmanda, alt satırı ve sol sütunu yalnızca katmanda birden fazla satır ve birden fazla sütun varsa oku; aksi hâlde geri dönüş yolu daha önce okuduğun hücrelerin üzerinden geçer.

Bir matrisi okumak yerine spiral sırayla nasıl doldurursunuz?

Aynı dört sınırı ve aynı dört kenarı kullan, ancak okumak yerine yaz. 1 ile başlayan bir sayaç tut ve her hücreden geçerken sayacı o hücreye yazıp her seferinde bir artır. n × n boyutundaki bir matris için sayaç n² değerine ulaşır ve yukarıdaki ilk örnek, 4 × 3 boyutundaki bir ızgara için elde edilen sonucu gösterir.

Engellenmişken sağa dönmek neden bir spiral oluşturur?

İlk turda gezgin matrisin dört kenarında döner. Sonraki her turda, daha önce okunan hücreler duvar görevi görür; böylece her tur, önceki turda yürüdüğü halkanın bir hücre öncesinde döner. Bu, her turun bir öncekinin içinde kalmasını sağlar; spiral de budur. Gezginin hangi katmanda olduğunu bilmesine gerek yoktur; yalnızca sıradaki hücrenin boş olup olmadığını bilmesi yeterlidir.

Python

def spiralOrder(matrix):
    # Kodu buraya yazın

Test durumları

Durum 1

Durum 2

Durum 3

Girdi

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

Beklenen

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