Grid'i spiral sırayla doldur
Görev tanımı
Problem
Satır ve sütun (column) sayısı verildiğinde, o boyutta, 1'den rows × cols'a kadar sayılarla içe doğru saat yönünde bir spiral halinde doldurulmuş bir grid kur: üst satır boyunca sağa, sağ sütun boyunca aşağı, alt satır boyunca geri, sol sütun boyunca yukarı ve her hücre dolana kadar yeniden etrafında. Grid'i satırlardan oluşan bir liste olarak döndür.
Örnekler
Input: rows = 3, cols = 3
Output: [[1, 2, 3], [8, 9, 4], [7, 6, 5]]
Neden: spiral orta hücrede bitiyor
Input: rows = 3, cols = 4
Output: [[1, 2, 3, 4], [10, 11, 12, 5], [9, 8, 7, 6]]
Neden: geniş bir grid tek bir hücre yerine kısa bir orta satırda biter
Input: rows = 1, cols = 1
Output: [[1]]
Neden: edge case: spiral tek bir adım
İpuçları
0 / 3
Bir kaplumbağa gibi yürü: bir konum ve bir yön tut, sonraki sayıyı yaz ve ileri adım at.
Saat yönü sırasıyla dört yön sağ, aşağı, sol ve yukarı. Dönmek o listede bir sonrakine geçmek demek.
Sonraki adım grid'den çıkacaksa ya da zaten dolu bir hücreye düşecekse dön. Sayılar 1'den başladığı için sıfır boş bir hücreyi işaretler.
- Hedef zaman
- O(rows · cols)
- Hedef alan
- O(rows · cols)
Çözüm
Bir spirali doldurmak okuma versiyonunun tersten çalıştırılmasıdır ve yazmanın en basit yolu yürümektir: bir konum ve bir yön tut, sonraki sayıyı yaz ve sonraki adım grid'den çıkacak ya da dolu bir hücreye çarpacaksa saat yönünde dön. Dolu hücreler küçülen sınır görevi görür; böylece dört ayrı kenar döngüsü ve tek satır ya da tek sütun için özel durumlar yoktur. Her hücre tam bir kez yazılır ve her adım sabit iş yapar; zaman O(rows × cols), tek alan da grid'in kendisi.
def spiral_fill(rows, cols):
grid = [[0] * cols for _ in range(rows)] # 0 = not filled yet
moves = [(0, 1), (1, 0), (0, -1), (-1, 0)] # right, down, left, up
r = c = d = 0
for value in range(1, rows * cols + 1):
grid[r][c] = value
nr, nc = r + moves[d][0], c + moves[d][1]
if not (0 <= nr < rows and 0 <= nc < cols) or grid[nr][nc]:
d = (d + 1) % 4 # blocked: turn clockwise
nr, nc = r + moves[d][0], c + moves[d][1]
r, c = nr, nc
return grid
print(spiral_fill(3, 3)) # -> [[1, 2, 3], [8, 9, 4], [7, 6, 5]]
print(spiral_fill(3, 4)) # -> [[1, 2, 3, 4], [10, 11, 12, 5], [9, 8, 7, 6]]
print(spiral_fill(1, 1)) # -> [[1]]Kodda değil de fikirde mi takıldın? Spiral dolaşma bunu anlatıyor.