Asteroid Collision
Bir asteroit sırası, hepsi aynı hızda olacak şekilde bir çizgi boyunca ilerler. asteroids içindeki her değer bir asteroidi tanımlar: mutlak değeri boyutunu, işareti ise yönünü belirtir; pozitif sağa, negatif sola doğru olduğunu gösterir.
Sağa doğru hareket eden bir asteroit sola doğru hareket eden bir asteroitle karşılaştığında çarpışırlar. Küçük olan patlar; boyutları aynıysa ikisi de patlar. Aynı yönde hareket eden asteroitler asla karşılaşmaz. Her çarpışmadan sonra geriye kalan asteroitleri, başlangıçtaki sıralarını koruyarak döndür. Sonuç boş olabilir.
Fonksiyon
- asteroidsinteger-array
- asteroitler soldan sağa, yön için işaret, boyut için mutlak değer
- Döndürürinteger-array
- soldan sağa kalan asteroitler, belki hiçbiri
Kısıtlar
1 ≤ asteroids.length ≤ 104-1000 ≤ asteroids[i] ≤ 1000asteroids[i] ≠ 0
Örnekler
- Girdi
- asteroids = [4, 9, -6, 2, -3]
- Çıktı
- [4, 9]
- Açıklama
- 9, -6 ile karşılaşır ve kazanır. 2, -3 ile karşılaşır ve patlar; ardından -3, 9'a doğru uçar ve o da patlar. Başka hiçbir şey başka bir şeye doğru hareket etmez, bu yüzden 4 ve 9 kalır.
- Girdi
- asteroids = [6, -6]
- Çıktı
- []
- Açıklama
- 6 ve -6 aynı büyüklükte çarpışır, bu yüzden ikisi de patlar ve sonuç boştur.
- Girdi
- asteroids = [-2, -7, 3, 8]
- Çıktı
- [-2, -7, 3, 8]
- Açıklama
- -2 ve -7 sola, 3 ve 8 sağa uçar; böylece iki grup birbirinden uzaklaşır. Hiçbir şey çarpışmaz ve dört asteroidin hepsi hayatta kalır.
Ek soru
Yığın, hangi asteroitlerin hayatta kaldığını belirler. Patlayan her asteroit için onu yok eden asteroitin indeksini de nasıl bildirirdin?
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
Bir çarpışma için solda sağa hareket eden, sağda ise sola hareket eden bir asteroit gerekir. Sol yönde hareket eden bir asteroitin önünde sağa hareket eden hiçbir şey yoksa, sonsuza dek güvendedir. Sırayı soldan sağa ilerleyerek inceleyin: Yeni sola hareket eden bir asteroit, daha önceki asteroitlerden hangilerine hâlâ çarpabilir?
Yeni bir sola hareket eden, önce hayatta kalan en yakın sağa hareket edene, sonra bir sonrakine ve böyle devam ederek patlayana ya da sağa hareket edenler tükenene kadar çarpar. O ana kadar hayatta kalanlar bir yığın gibi davranır: sıradaki darbeyi yalnızca en son gelen alabilir.
- Hayatta kalanları bir yığında tut. Sağa hareket edenlerin her birini yığına ekle. Sola hareket eden biri için, yığının tepesindeki daha küçük bir sağa hareket edeni, tepeye ulaşana kadar yığından çıkar. Tepedeki sağa hareket eden aynı boyuttaysa, onu yığından çıkar ve yenisini de bırak. Tepedeki daha büyükse, yenisini bırak. Aksi takdirde onu yığına ekle.
Çözüm
Sola hareket eden bir asteroit, sağa hareket edenlerden oluşan uzun bir diziyi yok edebilir ve her çarpışma, sıradaki çarpışmayı gerçekleştirecek yeni bir çifti ortaya çıkarabilir. Yeni bir asteroit her zaman önce hayatta kalanların en sonuncusuyla karşılaşır; bu nedenle hayatta kalanlardan oluşan bir yığın, tek geçişte tüm çarpışmaları çözer.
Her seferinde bir çökme sorununu çöz
Doğru, ama en büyük testlerde bitmiyor
Sezgi
İki asteroit, sağa hareket eden bir asteroit sola hareket eden bir asteroitin hemen solunda bulunduğunda çarpışır. Böyle ilk çifti bul, çarpışmayı çöz ve soldan başlayarak yeniden tara. Hiç çift kalmadığında artık hiçbir şey çarpışmaz ve satır cevap olur.
Çarpışmaları çözme sırası önemli değildir: Yan yana ve birbirine dönük asteroitler, başka herhangi bir şeyle çarpışmadan önce birbirleriyle çarpışır.
Her çarpışma yeni bir tarama ve satırın ortasından bir öğenin çıkarılmasını gerektirir. Sağa hareket eden 9.999 küçük asteroidin ardından -1000 gelirse, her taramada bir sağa hareket eden asteroidi yok etmek için satır baştan sona dolaşılır: yaklaşık 5 × 10^7 adım.
Algoritma
- Asteroitleri kaldırabilmek için satırı kopyalayın.
row[i] > 0verow[i+1] < 0koşullarını sağlayan ilkiindeksini soldan başlayarak tarayın.- Yoksa satırı döndürün.
- Aksi takdirde, ikisinden küçük olanı ya da boyutları eşitse ikisini de kaldırın ve yeniden tarayın.
def asteroidCollision(asteroids):
row = list(asteroids)
while True:
# A crash happens where a right-mover is directly followed by a left-mover.
hit = -1
for i in range(len(row) - 1):
if row[i] > 0 and row[i + 1] < 0:
hit = i
break
if hit == -1:
return row
right, left = row[hit], -row[hit + 1]
if right > left:
del row[hit + 1]
elif right < left:
del row[hit]
else:
del row[hit:hit + 2]Hayatta kalanlar yığını
Sezgi
Şimdiye kadar hayatta kalanları bir yığında tut. Yığında hiçbir zaman sağa hareket eden bir cisimden sonra sola hareket eden bir cisim bulunmaz; çünkü böyle bir çift çoktan çarpışmış olur. Bu nedenle yığın, kaçıp kurtulan sola hareket eden cisimlerin ardından sağa hareket eden cisimlerden oluşur.
Yeni bir sağa hareket eden cisim, yığındaki her şeyden uzaklaşır; bu yüzden onu yığına eklersin. Yeni bir sola hareket eden cisim, üstteki sağa hareket eden cisimlere doğru ilerler ve önce en yeni olanla karşılaşır; dolayısıyla sıradaki çarpabileceği tek asteroit en üsttekidir. İlk örnekte -3, 2'yi yığından çıkarır, ardından 9'la çarpışıp yok olur ve özgün sırasındaki [4, 9] yığını cevap olur.
Her asteroit en fazla bir kez yığına eklenir ve en fazla bir kez yığından çıkarılır; bu nedenle tek bir sola hareket eden cisim uzun bir diziyi temizlese bile tarama O(n) sürer.
Algoritma
- Sağ kalanlardan oluşan boş bir yığınla başlayın.
- Her asteroit için, sağa hareket ediyorsa onu yığına ekleyin ve devam edin.
- Sola hareket ediyorsa, üstündeki sağa hareket eden asteroitler kendisinden küçük olduğu sürece onları yığından çıkarın.
- Üstte artık aynı boyutta sağa hareket eden bir asteroit varsa onu yığından çıkarın ve yeni asteroidi bırakın. Üstte daha büyük, sağa hareket eden bir asteroit varsa yeni asteroidi bırakın. Aksi takdirde onu yığına ekleyin.
- Yığını alttan üste doğru döndürün.
def asteroidCollision(asteroids):
survivors = [] # the row so far, after every crash it caused
for rock in asteroids:
alive = True
# Only a left-mover can hit something: a right-mover on top of the stack.
while alive and rock < 0 and survivors and survivors[-1] > 0:
top = survivors[-1]
if top < -rock:
survivors.pop() # the right-mover is smaller and explodes
elif top == -rock:
survivors.pop() # same size: both explode
alive = False
else:
alive = False # the right-mover is bigger: the new one explodes
if alive:
survivors.append(rock)
return survivors
Tuzaklar ve uç durumlar
- Sola hareket eden bir nesneyi sağa hareket eden bir nesnenin ardından geldiğinde çarpışma olarak değerlendirmek.
[-2, -7, 3, 8]örneğinde gruplar birbirinden uzaklaşır ve dördü de hayatta kalır. - Yığından çıkarma işlemleri için
whileyerineifkullanmak.[1, 2, 3, 4, 5, -15]örneğinde sola hareket eden nesne, sağa hareket eden beş nesnenin tümünü yok eder ve hayatta kalır. - Eşitlik durumunu atlamak.
[6, -6]örneğinde 6 yığından çıkarılmalı ve -6 atılmalı; böylece sonuç boş kalmalıdır. - Kaybeden bir sola hareket eden nesneyi yığına eklemek.
[9, -6]örneğinde -6 patlar ve yığına eklenmemelidir; hâlâ hayatta olup olmadığını belirten bir bayrak kullanın.
Sıkça sorulan sorular3
Asteroid Collision'ın zaman karmaşıklığı nedir?
Kalan asteroitlerden oluşan bir yığınla O(n) zaman ve O(n) alan; çünkü her asteroit en fazla bir kez yığına eklenir ve yığından çıkarılır. Her çarpışmadan sonra satırı yeniden taramak O(n²) maliyet getirir.
Asteroid Collision için yığın neden doğru veri yapısıdır?
Yeni bir asteroit yalnızca kendisine en yakın hayatta kalanlara ulaşabilir ve onlarla en yeniden en eskiye doğru karşılaşır. Yani son giren ilk çıkar. Sona gelindiğinde yığında ne varsa artık çarpışamaz; bu nedenle son satırda yer alır.
Asteroid Collision O(1) ek alan kullanılarak çözülebilir mi?
Evet, girdinin üzerine yazabiliyorsan. Yığının sonu olarak dizinin başını kullan: bir yazma indeksi top tut, asteroids[top-1] ile karşılaştır ve ilk top girdiyi döndür.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
def asteroidCollision(asteroids):
# Kodu buraya yazınTest #1
Test #2
Test #3
Argüman
asteroids = [4, 9, -6, 2, -3]
Beklenen Çıktı
[4, 9]