Demo önizleme: Bu çözümler otomatik test paketini geçiyor ama insan tarafından incelenmedi. Trade-off ve yazıları taslak olarak değerlendirin.

Mediumtopological-sort

Course Schedule II

Problem (yeniden ifade)

numCourses ve prerequisites [a,b] (b, a’dan önce). Herhangi geçerli bir sıra döndür; döngü varsa boş.

Sezgi

Course Schedule ile aynı: Kahn indegree BFS; sırayı üret; count n’den küçükse döngü.

Yaklaşımlar

Kahn BFS topo

Doğrulanmadı

Zaman O(V+E)Alan O(V+E)

Fikir. graf+indegree kur; sıfırları kuyruğa al; pop et ve komşuları azalt.

Yürüyüş. 2, [[1,0]] → [0,1]; döngü → [].

Trade-off. DFS renk topo da çalışır; Kahn şablon varsayılanı.

Çözüm

export function findOrder(numCourses: number, prerequisites: number[][]): number[] {
  const g: number[][] = Array.from({ length: numCourses }, () => []);
  const indeg = new Array(numCourses).fill(0);
  for (const [a, b] of prerequisites) {
    g[b!]!.push(a!);
    indeg[a!]++;
  }
  const q: number[] = [];
  for (let i = 0; i < numCourses; i++) if (indeg[i] === 0) q.push(i);
  const order: number[] = [];
  while (q.length) {
    const u = q.shift()!;
    order.push(u);
    for (const v of g[u]!) {
      if (--indeg[v]! === 0) q.push(v);
    }
  }
  return order.length === numCourses ? order : [];
}

export function findOrder(numCourses: number, prerequisites: number[][]): number[] {
  const g: number[][] = Array.from({ length: numCourses }, () => []);
  const indeg = new Array(numCourses).fill(0);
  for (const [a, b] of prerequisites) {
    g[b!]!.push(a!);
    indeg[a!]++;
  }
  const q: number[] = [];
  for (let i = 0; i < numCourses; i++) if (indeg[i] === 0) q.push(i);
  const order: number[] = [];
  while (q.length) {
    const u = q.shift()!;
    order.push(u);
    for (const v of g[u]!) {
      if (--indeg[v]! === 0) q.push(v);
    }
  }
  return order.length === numCourses ? order : [];
}

Şablon bağlantısı

Önkoşullar için topolojik sıralama.

Yansıma

Kahn sırası geçerli bir ders sırası. Döngüde çıkan düğüm n’den azsa cevap boş.
İndegree 0 birden fazlaysa kuyruk sırası çıktıyı değiştirir. Hepsi geçerli.
Önkoşul yok: dersler herhangi sırada. Tek ders: o ders.