Course Schedule
numCourses ders vardır ve bu dersler 0 ile numCourses-1 arasında numaralandırılmıştır. prerequisites içindeki her [a, b] çifti, a dersine başlamadan önce b dersini tamamlamanız gerektiği anlamına gelir. Her dersi tamamlamanızı sağlayan bir sıralama varsa true, yoksa false döndürün.
Fonksiyon
- numCoursesinteger
- ders sayısı
- prerequisitesinteger-2d-array
- Her biri b dersinin a dersinden önce geldiği anlamına gelen [a, b] çiftleri
- Döndürürboolean
- Her ders tamamlanabiliyorsa true, aksi takdirde false
Kısıtlar
1 ≤ numCourses ≤ 1051 ≤ prerequisites.length ≤ 5000- Her
[a, b]çifti için0 ≤ a, b < numCourseskoşulu geçerlidir. - Hiçbir ikili iki kez görünmez.
- Bir çift aynı dersi iki kez adlandırabilir:
[a, a]. Bu dersin önce kendisinin alınmış olması gerekir; bu yüzden hiçbir zaman alınamaz.
Örnekler
- Girdi
- numCourses = 4prerequisites = [[1, 0], [2, 1], [3, 1]]
- Çıktı
- true
- Açıklama
- Ders 0'ın ön koşulu yok, bu yüzden onu önce alırsın. Böylece ders 1'in, ardından 2 ve 3'ün ön koşulları tamamlanır; dolayısıyla 0, 1, 2, 3 sıralaması işe yarar.
- Girdi
- numCourses = 3prerequisites = [[0, 2], [2, 1], [1, 0]]
- Çıktı
- false
- Açıklama
- Ders 0, 2'yi bekler; 2, 1'i bekler ve 1, 0'ı bekler. Üçü bir döngü içinde birbirini bekler, bu yüzden hiçbiri önce başlayamaz.
Ek soru
Herhangi sayıda ders tek bir döneme sığabilir; yeter ki her dersin ön koşulları önceki dönemlerde tamamlanmış olsun. Tüm dersleri tamamlamak için gereken en az dönem sayısı kaçtır?
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
Her dersi bir nokta, her
[a, b]çiftini deb'dena'ya giden bir ok olarak çiz. Bu çizimde hangi şekil, dersleri bitirmeyi imkânsız hâle getirir?Ok döngüsü. Bir döngüdeki her ders, aynı döngüdeki başka bir dersi bekler; bu yüzden hiçbirisi ilk sırada olamaz. Soru, grafın bir döngü içerip içermediğidir.
Her dersin hâlâ kaç ön koşul beklediğini say. Sayısı 0 olan dersleri bir kuyruğa ekle ve her birini aldığında, onu bekleyen her dersin sayısını azalt.
numCoursesdersin tümü kuyruğa ulaşmazsa bir döngü vardır.
Çözüm
Her [a, b] çifti için b → a oku çizin. V = numCourses düğüm ve E = prerequisites.length ok içeren bu grafikte döngü yoksa her ders tam olarak bitirilebilir. Kahn algoritması bunu bir öğrencinin plan yaptığı gibi kontrol eder: ön koşulları tamamlanmış bir dersi almaya devam edin ve her dersin alınıp alınmadığını görün.
Her turda tüm ücretsiz kursları al
Doğru, ama en büyük testlerde bitmiyor
Sezgi
Her turda, ön koşullarının tümü alınmış olan alınmamış her dersi al. Bir turda hiçbir ders alınmadığında dur ve her ders alınmışsa true yanıtını ver. Bir turda hiçbir ders alınmaması, yalnızca geriye kalan her ders başka bir geriye kalan dersi beklediğinde gerçekleşir; bu da bir döngüdür.
Her turda tüm çiftler ve her ders yeniden kontrol edilir, ancak yalnızca tek bir ders alınabilir. 100.000 ders arasındaki 5.001 derslik bir zincir 5.000'den fazla tur gerektirir: yaklaşık 5 × 10^8 kontrol.
Algoritma
- Her dersi alınmamış olarak işaretle.
- Bir ders, alınmamış bir ön koşulu varsa engellenmiş olarak işaretle.
- Alınmamış ve engellenmemiş her dersi al.
- Turda hiçbir ders alınmadıysa dur; aksi takdirde 2. adıma dön.
- Her ders alınmışsa true döndür.
def canFinish(numCourses, prerequisites):
taken = [False] * numCourses
count = 0
while True:
# A course is blocked while one of its prerequisites is not taken.
blocked = [False] * numCourses
for course, before in prerequisites:
if not taken[before]:
blocked[course] = True
# Take every course that is free this round.
progress = False
for c in range(numCourses):
if not taken[c] and not blocked[c]:
taken[c] = True
count += 1
progress = True
if not progress:
break
return count == numCoursesÜç durumlu derinlik öncelikli arama
Sezgi
Derinlik öncelikli arama, izlediği yolu takip ederek bir döngü bulur. Her derse üç durumdan birini ver: ziyaret edilmedi, yolda, tamamlandı. Bir dersten, onu bekleyen derslere giden okları takip et. Bir derse girdiğinde onu yolda olarak işaretle, tüm okları incelendiğinde ise tamamlandı olarak işaretle.
Yoldaki bir derse giden ok bir döngüyü kapatır: false döndür. Tamamlanmış bir derse giden ok güvenlidir; çünkü o dersten erişilebilen her şey kontrol edilmiştir ve döngü içermez. Dolayısıyla bir derse ikinci kez ulaşılması tek başına döngü olduğu anlamına gelmez. Her derse bir kez girilir ve her ok bir kez izlenir: O(V + E).
Algoritma
- Her ders için, onu bekleyen derslerin listesini oluştur.
- Ziyaret edilmemiş her ders için, onu yol üzerinde işaretle ve yığına ekle.
- Yığının en üstündeki derse bak. Takip edilecek oku kalmadıysa, onu tamamlandı olarak işaretle ve yığından çıkar; aksi takdirde sıradaki oku takip et.
- Ok yol üzerindeki bir derse gidiyorsa, false döndür. Ziyaret edilmemiş bir derse gidiyorsa, o dersi yol üzerinde işaretle ve yığına ekle.
- Tüm dersler tamamlandığında, true döndür.
def canFinish(numCourses, prerequisites):
unlocks = [[] for _ in range(numCourses)]
for course, before in prerequisites:
unlocks[before].append(course)
# 0 = not visited, 1 = on the current path, 2 = done, no cycle below it
state = [0] * numCourses
# next_edge[c] counts the edges out of c the search has already followed.
next_edge = [0] * numCourses
for start in range(numCourses):
if state[start] != 0:
continue
# A stack of our own instead of recursion: a chain of 5,000
# courses would go 5,000 calls deep.
state[start] = 1
stack = [start]
while stack:
course = stack[-1]
if next_edge[course] == len(unlocks[course]):
state[course] = 2
stack.pop()
continue
nxt = unlocks[course][next_edge[course]]
next_edge[course] += 1
if state[nxt] == 1:
return False # an edge back to the current path closes a cycle
if state[nxt] == 0:
state[nxt] = 1
stack.append(nxt)
return TrueKahn algoritması
Sezgi
Bir ders tek bir anda ücretsiz hâle gelir: son ön koşulu alındığında. Bu yüzden her dersin giriş derecesini, yani hâlâ kaç ön koşulu beklediğini tut ve sayısı 0 olan her dersle bir kuyruk başlat. Bir dersi almak, onu bekleyen her dersin sayısını azaltır ve sayısı 0'a ulaşan ders kuyruğa eklenir. İlk örnekte sayılar başlangıçta 0, 1, 1, 1'dir: 0'ı almak 1'i, 1'i almak da 2 ve 3'ü serbest bırakır. Her ders kuyruğa bir kez girer ve her çift sayıyı bir kez azaltır: O(V + E).
Kuyruk boşaldığında a dersi hâlâ alınmamışsa, sayısı 0'dan büyüktür; dolayısıyla a'nın bir ön koşulu da alınmamıştır ve bu böyle devam eder. Bu yürüyüşte aynı derse yeniden ulaşmak zorunludur: bir döngü. Buna karşılık, bir döngüdeki her ders o döngüdeki başka bir dersi bekler; bu nedenle hiçbir ders önce alınamaz. Derslerin kuyruktan çıkma sırası geçerli bir programdır.
Algoritma
- Her [a, b] çifti için a'yı b'yi bekleyen dersler listesine ekleyin ve a'nın giriş derecesine 1 ekleyin.
- Giriş derecesi 0 olan her dersi bir kuyruğa ekleyin.
- Kuyruktan bir ders alın ve sayın. Onu bekleyen her dersin giriş derecesini azaltın ve 0'a ulaşan her dersi kuyruğa ekleyin.
- Kuyruk boşaldığında, sayının
numCoursesdeğerine eşit olup olmadığını döndürün.
from collections import deque
def canFinish(numCourses, prerequisites):
# unlocks[b] lists the courses that wait for b.
# indegree[a] counts the prerequisites of a that are not taken yet.
unlocks = [[] for _ in range(numCourses)]
indegree = [0] * numCourses
for course, before in prerequisites:
unlocks[before].append(course)
indegree[course] += 1
# Every course with no prerequisites can be taken right away.
queue = deque(c for c in range(numCourses) if indegree[c] == 0)
taken = 0
while queue:
course = queue.popleft()
taken += 1
for nxt in unlocks[course]:
indegree[nxt] -= 1
if indegree[nxt] == 0:
queue.append(nxt)
# A course on a cycle never gets down to 0, so it is never taken.
return taken == numCourses
Tuzaklar ve uç durumlar
- Yönü karıştırmak.
[a, b], b'nin önce geldiği anlamına gelir: ok b'den a'ya gider ve a'nın giriş derecesi artar. - Hiçbir çiftte yer almayan dersleri unutmak.
numCourses = 5ve tek çift[4, 3]olduğunda, 0, 1 ve 2 numaralı dersler de başlangıçta kuyruğa eklenmelidir. - Derinlik öncelikli aramada üç durum yerine iki durum kullanmak. 0 → 1, 0 → 2, 1 → 3, 2 → 3 elmas biçiminde, yalnızca "seen" durumunu takip ederseniz 3 numaralı derse iki kez ulaşılır ve bu bir döngü gibi görünür.
- 5.000 derslik bir zincirde özyineleme yapmak: 5.000 çağrı derinliği, Python'ın varsayılan 1.000 sınırını aşar.
numCoursesdersin tamamının alındığını kontrol etmeden kuyruk boşaldığında true döndürmek. İkinci örnek true döndürürdü.
Sıkça sorulan sorular3
Course Schedule probleminin zaman karmaşıklığı nedir?
O(V + E); burada V ders sayısı, E ise çift sayısıdır. Kahn algoritması ya da derinlik öncelikli arama kullanılır. Her çift bir kez okunur ve her ders bir kez işlenir. Listeler ve sayımlar O(V + E) alan kullanır.
Ders Programı için BFS mi yoksa DFS mi kullanmalısınız?
İkisi de O(V + E) sürede çalışır. Genişlik öncelikli sürüm olan Kahn algoritmasında endişelenmeniz gereken bir özyineleme derinliği yoktur ve derslerin geçerli bir sıralamasını verir. Döngüyü de bildirmeniz gerektiğinde üç durumlu derinlik öncelikli arama doğal seçimdir; çünkü yığınındaki dersler döngüyü oluşturur.
Topolojik sıralama nedir?
Yönlü bir grafiğin düğümlerinin, her okun ileriye doğru gösterdiği bir sıralaması; burada, her ön koşulun onu gerektiren dersten önce geldiği bir sıralama. Yalnızca grafikte döngü olmadığında vardır ve Kahn algoritmasının dersleri aldığı sıra böyle bir sıralamadır. Course Schedule, böyle bir sıralamanın var olup olmadığını sorar.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
def canFinish(numCourses, prerequisites):
# Kodu buraya yazınTest #1
Test #2
Argümanlar
numCourses = 4 prerequisites = [[1, 0], [2, 1], [3, 1]]
Beklenen Çıktı
true