Kilitli her odayı aç
Görev tanımı
Problem
Bir kaçış odasında 0'dan n - 1'e kadar numaralanmış n oda var. 0 numaralı oda açık, diğer her oda kilitli başlıyor. i numaralı odanın içinde bir anahtar listesi, rooms[i], duruyor; j numaralı bir anahtar j numaralı odayı açıyor. Anahtarlar istenen sayıda ve istenen sırada kullanılabilir. Her odaya girebiliyorsan True döndür. En fazla 1.000 oda ve toplamda en fazla 3.000 anahtar var.
Örnekler
Input: rooms = [[1], [2], [3], []]
Output: True
Neden: 0 numaralı oda 1 numaralı anahtarı, 1 numaralı oda 2 numaralı anahtarı, 2 numaralı oda 3 numaralı anahtarı tutuyor
Input: rooms = [[1, 3], [3, 0, 1], [2], [0]]
Output: False
Neden: 2 numaralı odanın tek anahtarı bu odanın kendi içinde kilitli
Input: rooms = [[]]
Output: True
Neden: edge case: tek oda zaten açık
İpuçları
0 / 3
Her odayı bir düğüm, her anahtarı da bulunduğu odadan açtığı odaya giden yönlü bir kenar olarak düşün.
Soru o zaman her düğüme 0 düğümünden ulaşılıp ulaşılamayacağı.
0 numaralı odadan elle yönetilen bir stack ve bir ziyaret kümesiyle derinlik öncelikli bir arama çalıştır. Henüz ziyaret etmediğin her anahtarın odasını push et. Sonunda ziyaret kümesinin boyutunu n ile karşılaştır.
- Hedef zaman
- O(n + k)
- Hedef alan
- O(n)
Kısıtlar
- n ≤ 1000 rooms
- ≤ 3000 keys in total
- room 0 starts open
Çözüm
Odalar ve anahtarlar, i numaralı odadan, anahtarı bu odada duran her odaya bir kenarla yönlü bir graf oluşturur; bir odaya tam olarak 0 numaralı odadan ulaşılabildiğinde girilebilir. 0 numaralı odadan bir derinlik öncelikli arama (DFS) ulaşılabilen her odayı işaretler; elle yönetilen bir stack, uzun bir oda zincirinde derin özyinelemeyi (recursion) önler. Her oda en fazla bir kez push edilir ve her anahtara bir kez bakılır; n oda ve k anahtar için zaman O(n + k), alan O(n).
def can_open_all(rooms):
seen = {0}
stack = [0]
while stack:
room = stack.pop()
for key in rooms[room]:
if key not in seen: # a room we have not entered yet
seen.add(key)
stack.append(key)
return len(seen) == len(rooms)
print(can_open_all([[1], [2], [3], []])) # -> True
print(can_open_all([[1, 3], [3, 0, 1], [2], [0]])) # -> False
print(can_open_all([[]])) # -> TrueKodda değil de fikirde mi takıldın? Derinlik öncelikli arama bunu anlatıyor.