Number of Islands
Eşit uzunlukta dizelerden oluşan bir liste olarak bir harita alırsın; burada '1' bir kara karesini, '0' ise bir su karesini belirtir. İki kara karesi aynı adaya, bir kenarı paylaştıklarında aittir: yukarı, aşağı, sol veya sağ. Yalnızca köşeleri birleşen kareler bağlantılı değildir. Ada sayısını döndür.
Fonksiyon
- gridstring-array
- harita, her satırda bir dizge
- Döndürürinteger
- ada sayısı
Kısıtlar
1 ≤ grid.length ≤ 1501 ≤ grid[i].length ≤ 150- Her satır aynı uzunluktadır.
- Her karakter
'0'veya'1'olur.
Örnekler
- Girdi
- grid = ["11000", "11000", "00100", "00011"]
- Çıktı
- 3
- Açıklama
- Sol üstteki dört kare bir ada oluşturur. Üçüncü sıradaki orta kare, onlara yalnızca bir köşesinden dokunduğu için ikinci bir adadır. Sağ alttaki çift ise üçüncü adadır.
- Girdi
- grid = ["01110", "01000", "00011", "11001"]
- Çıktı
- 3
- Açıklama
- Üst sıradaki üç kare ve sol ucunun altındaki kare bir ada oluşturur. Üçüncü sıradaki sağdaki ikili, aşağı doğru en sağ alttaki kareye bağlanarak ikinci bir ada oluşturur. Sol alttaki ikili ise üçüncü adadır.
Ek soru
Artık kara, su haritasında her seferinde bir kare olarak beliriyor. Tüm haritayı yeniden taramadan, her yeni kareden sonra ada sayısını bildirebilir misin?
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
Haritayı kare kare tara. Daha önce hiçbir adanın sahiplenmediği bir kara karesine ulaştığında, kaç yeni ada bulmuş olursun?
Yeni bir ada bulduğunuzda, ona bağlı tüm kara karelerini ziyaret edip her birini görüldü olarak işaretleyin; böylece tarama aynı adayı tekrar saymaz.
Ziyaret edilecek kareleri bir kuyrukla (önce genişlik) ya da açıkça tanımlanmış bir yığınla (önce derinlik) keşfedin. Tek ve devasa bir adadan oluşan bir haritada özyinelemeli arama çağrı yığınını tüketebilir; kendi kuyruğunuz ya da yığınınız üzerindeki bir döngü ise tüketemez.
Çözüm
Her kara karesini yanındaki kara karelerine bağlı bir düğüm olarak ele al: bir ada, birbirine bağlı tek bir parçadır. Haritayı tara ve daha önce görmediğin bir karaya her ulaştığında yeni bir ada sayıp onu taşırarak doldur; taramanın onu bir daha saymaması için tüm karelerini işaretle.
Belirgin bir yığınla taşkın doldurma (DFS)
Sezgi
İşaretlenmemiş bir kara karesi, daha önce saydığınız bir adaya ait olamaz; çünkü bir adayı saymak onun tamamını işaretler. Bu nedenle yeni bir ada başlatır. Kendiniz yönettiğiniz bir yığın geri kalanını işaretler: çıkardığınız her kare, işaretlenmemiş kara komşularını yığına ekler ve yığın boşaldığında adanın tamamı işaretlenmiş olur.
Kendi yığınınızı kullanmanız önemlidir; çünkü özyinelemeli bir doldurma, tamamen kara olan 150 × 150 boyutundaki bir haritada 22,500 çağrı derinliğine ulaşabilir. Her kare yığına en fazla bir kez eklenir ve dört komşusu kontrol edilir; bu nedenle süre O(rows × cols) olur. Harita tamamen kara olduğunda işaretler ve yığın O(rows × cols) alan kaplar.
Algoritma
- Her kare için bir ziyaret edildi işareti oluştur ve sayacı 0 olarak ayarla.
- Su olan kareleri ve daha önce ziyaret edilmiş kareleri atlayarak tüm kareleri tara.
- Ziyaret edilmemiş kara üzerinde, sayaca 1 ekle, kareyi işaretle ve bir yığına ekle.
- Yığın boş değilken bir kareyi yığından çıkar ve harita sınırları içindeki, ziyaret edilmemiş kara olan her komşuyu işaretleyip yığına ekle.
- Tarama sona erdiğinde sayacı döndür.
def numIslands(grid):
rows, cols = len(grid), len(grid[0])
seen = [[False] * cols for _ in range(rows)]
count = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] != '1' or seen[r][c]:
continue
# Land that no island has claimed yet: a new island.
count += 1
seen[r][c] = True
stack = [(r, c)]
while stack:
i, j = stack.pop()
for ni, nj in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
if 0 <= ni < rows and 0 <= nj < cols and grid[ni][nj] == '1' and not seen[ni][nj]:
# Mark on push, so no square enters the stack twice.
seen[ni][nj] = True
stack.append((ni, nj))
return countKuyruk kullanarak taşma doldurma (BFS)
Sezgi
Sayı aynı şekilde çalışır; yalnızca ziyaret sırası değişir. Bir kuyruk kareleri önden alır ve işaretlenmemiş kara komşularını arkaya ekler; böylece adayı halkalar hâlinde ziyaret eder: önce ilk kareyi, ardından bir adım uzaktaki tüm kareleri, sonra iki adım uzaktakileri. Her kare yine yalnızca bir kez ziyaret edilir; zaman ve alan karmaşıklığı O(rows × cols) olur.
Halka sırası, her karenin başlangıçtan uzaklığını verir; böylece aynı döngü, kare başına fazladan bir sayıyla ızgaradaki en kısa yol sorularını yanıtlar.
Algoritma
- Her kare için bir ziyaret edildi işareti oluştur ve sayıyı 0 olarak ayarla.
- Her kareyi tara; suyu ve daha önce ziyaret edilmiş kareleri atla.
- Ziyaret edilmemiş karada sayıya 1 ekle, kareyi işaretle ve boş bir kuyruğa ekle.
- Kuyrukta kare olduğu sürece öndekini al ve haritanın içindeki, ziyaret edilmemiş kara olan her komşuyu işaretleyerek kuyruğun sonuna ekle.
- Tarama bittiğinde sayıyı döndür.
def numIslands(grid):
rows, cols = len(grid), len(grid[0])
seen = [[False] * cols for _ in range(rows)]
count = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] != '1' or seen[r][c]:
continue
count += 1
seen[r][c] = True
stack = [(r, c)]
while stack:
i, j = stack.pop()
for ni, nj in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
if 0 <= ni < rows and 0 <= nj < cols and grid[ni][nj] == '1' and not seen[ni][nj]:
seen[ni][nj] = True
stack.append((ni, nj))
return count
Tuzaklar ve uç durumlar
- Bir kareyi yığına veya kuyruğa eklerken değil, yığından veya kuyruktan çıkarırken işaretlemek. Böylece aynı kare kuyruğa birkaç kez eklenir.
- Bir kareyi
'1'karakteri yerine 1 sayısıyla karşılaştırmak. Her satır bir dizedir, dolayısıyla her kare bir karakterdir. 0 ≤ row < rowsve0 ≤ col < colskoşullarını denetlemeden önce bir komşuyu okumak. Böylece kenardaki bir kara karesi haritanın dışından okur.- Doldurma işlemini özyinelemeli yazmak. Python varsayılan olarak 1.000 çağrıdan sonra durur ve diğer dillerde büyük bir adadaki çağrılar yığın taşmasına neden olabilir.
- Bir Python listesinin başından
pop(0)ile eleman çıkarmak; bu işlem listeyle orantılı zaman alır.collections.dequevepopleft()kullanın.
Sıkça sorulan sorular4
Number of Islands'ın zaman karmaşıklığı nedir?
O(rows × cols). Tarama her kareye bir kez bakar ve her kara kare yığına veya kuyruğa bir kez eklenir, ardından dört komşusu kontrol edilir. seen işaretleri ve yığın veya kuyruk, tamamen kara olan bir haritada O(rows × cols) alan kullanır.
Adaların Sayısı için BFS mi yoksa DFS mi kullanmalısınız?
İkisi de aynı zaman ve bellek karmaşıklığında doğrudur; çünkü sayım için yalnızca bir adanın her hücresinin işaretlenmesi gerekir. Kuyruk kullanan BFS hiçbir zaman özyinelemeli çağrı yapmaz; açık bir yığın kullandığında DFS de aynı derecede güvenlidir.
Union-find ile Adalar Sayısı problemini çözebilir misin?
Evet. Her kara karesini kendi kümesine koy ve sayımı kara karelerinin sayısından başlat. Komşu olan her kara karesi çiftini birleştir ve birleştirme iki farklı kümeyi bağladığında sayımı bir azalt. Yol sıkıştırmayla süre O(rows × cols) değerine yakındır.
Farklı bir seen dizisi olmadan adaları sayabilir misin?
Evet, haritayı değiştirebiliyorsan: her kara karesine ulaşır ulaşmaz onu suya dönüştür. Birçok dilde dizeler yerinde değiştirilemez; bu yüzden önce satırları bir karakter ızgarasına kopyalarsın ve bunun maliyeti, ziyaret edildi işaretleriyle aynı miktarda alan kaplar.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
def numIslands(grid):
# Kodu buraya yazınTest #1
Test #2
Argüman
grid = ["11000", "11000", "00100", "00011"]
Beklenen Çıktı
3