DSA Interview Prep · Pelajaran

Jadual Kursus I dan II

Modelkan prasyarat kursus sebagai graf berarah dan gunakan isihan topologi untuk menentukan sama ada semua kursus boleh diselesaikan serta susunannya.

Pelajaran 3 daripada 413 langkah

Jadual Kursus I dan II ialah pelajaran DSA Interview Prep percuma di CoddyKit. Ini ialah pelajaran 3 daripada 4. Sebanyak 3 pelajaran dalam laluan pembelajaran ini boleh dibaca sepenuhnya secara percuma — selepas itu, CoddyKit PRO membuka akses kepada semua pelajaran, serta latihan praktikal dengan penyunting kod terbina dalam dan tutor kecerdasan buatan yang tersedia 24/7. Pelajaran ini merupakan sebahagian daripada laluan pembelajaran DSA Interview Prep, dan kemajuan anda disegerakkan merentas web serta aplikasi CoddyKit. Kursus DSA Interview Prep merangkumi sejumlah 4 pelajaran.

Gambaran Keseluruhan Masalah

Jadual Kursus I (LeetCode 207): diberikan n kursus dan senarai pasangan prerequisites [a, b] yang bermaksud 'b mesti diambil sebelum a', tentukan sama ada anda boleh menamatkan semua kursus. Jadual Kursus II (LeetCode 210): kembalikan susunan sebenar untuk mengambil kursus, atau tatasusunan kosong jika mustahil. Kedua-duanya boleh dirumuskan sebagai pengisihan topologi pada graf berarah yang prasyaratnya diwakili oleh sisi.

Pemodelan Graf

Bina graf berarah: bagi setiap pasangan prasyarat [a, b], tambahkan sisi b → a ('b mesti muncul sebelum a' bermaksud b menuju kepada a). Kira darjah masuk bagi setiap kursus. Kursus dengan darjah masuk 0 tidak mempunyai prasyarat dan boleh diambil serta-merta. Masalah ini boleh diselesaikan jika dan hanya jika tiada kitaran dalam graf ini (tiada kebergantungan melingkar).

from collections import defaultdict

def build_graph(n, prerequisites):
    graph = defaultdict(list)
    in_degree = [0] * n
    for a, b in prerequisites:  # b must come before a
        graph[b].append(a)
        in_degree[a] += 1
    return graph, in_degree

graph, ind = build_graph(4, [[1,0],[2,0],[3,1],[3,2]])
print('In-degrees:', ind)   # [0, 1, 1, 2]
print('Graph edges:', dict(graph))

Jadual Kursus I: Penyelesaian Kahn

Gunakan algoritma Kahn. Jika bilangan kursus yang diproses sama dengan n, semua kursus boleh diselesaikan. Jika tidak, kebergantungan melingkar menghalang penyelesaian.

from collections import deque, defaultdict

def canFinish(numCourses, prerequisites):
    graph = defaultdict(list)
    in_degree = [0] * numCourses
    for a, b in prerequisites:
        graph[b].append(a)
        in_degree[a] += 1
    
    queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
    count = 0
    
    while queue:
        course = queue.popleft()
        count += 1
        for nxt in graph[course]:
            in_degree[nxt] -= 1
            if in_degree[nxt] == 0:
                queue.append(nxt)
    
    return count == numCourses

print(canFinish(2, [[1,0]]))        # True
print(canFinish(2, [[1,0],[0,1]])) # False

Jadual Kursus II: Kembalikan Susunan

Sama seperti Jadual Kursus I, tetapi kumpulkan susunan kursus semasa kita memprosesnya. Kembalikan susunan tersebut jika semua kursus disertakan; jika tidak, kembalikan senarai kosong.

from collections import deque, defaultdict

def findOrder(numCourses, prerequisites):
    graph = defaultdict(list)
    in_degree = [0] * numCourses
    for a, b in prerequisites:
        graph[b].append(a)
        in_degree[a] += 1
    
    queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
    order = []
    
    while queue:
        course = queue.popleft()
        order.append(course)
        for nxt in graph[course]:
            in_degree[nxt] -= 1
            if in_degree[nxt] == 0:
                queue.append(nxt)
    
    return order if len(order) == numCourses else []

print(findOrder(4, [[1,0],[2,0],[3,1],[3,2]]))

Jadual Kursus dengan DFS

Alternatif yang menggunakan pengesanan kitaran DFS. Kursus mempunyai tiga keadaan: belum dilawati (0), sedang diproses (1), selesai (2). Jika kita mencapai kursus yang sedang diproses semasa DFS, kitaran wujud. Pendekatan ini setara dari segi fungsi dengan algoritma Kahn tetapi menggunakan DFS rekursif.

from collections import defaultdict

def canFinish_dfs(numCourses, prerequisites):
    graph = defaultdict(list)
    for a, b in prerequisites:
        graph[b].append(a)
    
    # 0=unvisited, 1=in-progress, 2=done
    state = [0] * numCourses
    
    def has_cycle(course):
        if state[course] == 1: return True  # back edge
        if state[course] == 2: return False # already cleared
        state[course] = 1
        for nxt in graph[course]:
            if has_cycle(nxt):
                return True
        state[course] = 2
        return False
    
    return not any(has_cycle(i) for i in range(numCourses))

print(canFinish_dfs(2, [[1,0]]))        # True
print(canFinish_dfs(2, [[1,0],[0,1]])) # False

Mengapa Arah Sisi Penting

Kesilapan biasa ialah menterbalikkan arah sisi: jika prasyarat ialah [a, b] yang bermaksud 'b sebelum a', tambahkan sisi b → a, bukannya a → b. Arah sisi mesti mencerminkan aliran kebergantungan: anak panah menunjuk daripada perkara yang mesti dilakukan dahulu kepada perkara yang bergantung padanya. Dengan arah yang salah, pengesanan kitaran dan susunan akan menjadi terbalik, lalu menghasilkan keputusan yang salah bagi masalah dengan berbilang kebergantungan.

Jadual Kursus III: Variasi Tamak

Jadual Kursus III (LeetCode 630) ialah masalah yang berbeza: kursus mempunyai tempoh dan tarikh akhir, dan anda mahu memaksimumkan bilangan kursus yang diambil. Masalah ini diselesaikan secara tamak dengan timbunan maksimum: sentiasa ambil kursus dengan tarikh akhir paling lewat dahulu; jika penambahan kursus melebihi tarikh akhirnya, gantikannya dengan kursus paling lama yang telah diambil setakat itu (jika kursus tersebut lebih lama). Ini ialah masalah tamak, bukannya masalah pengisihan topologi — menunjukkan kepentingan membaca pernyataan masalah dengan teliti.

Mengendalikan Nod Terasing

Kursus tanpa prasyarat dan tanpa kursus yang bergantung padanya ialah nod terasing — nod tersebut mempunyai darjah masuk 0 dan tiada sisi keluar. Algoritma Kahn mengendalikannya dengan betul: nod tersebut terus dimasukkan ke dalam baris gilir dan diproses. Pastikan anda memulakan darjah masuk untuk SEMUA nod dari 0 hingga n-1, termasuk nod yang tidak muncul dalam senarai prasyarat; jika tidak, nod tersebut akan terlepas.

# Example: 4 courses, but only courses 0 and 1 have a prerequisite relationship
# Courses 2 and 3 are isolated - they should appear in the output
from collections import deque, defaultdict

def findOrder_isolated(numCourses, prerequisites):
    graph = defaultdict(list)
    in_degree = [0] * numCourses  # initialise ALL nodes
    for a, b in prerequisites:
        graph[b].append(a)
        in_degree[a] += 1
    queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
    order = []
    while queue:
        c = queue.popleft(); order.append(c)
        for nxt in graph[c]:
            in_degree[nxt] -= 1
            if in_degree[nxt] == 0: queue.append(nxt)
    return order if len(order) == numCourses else []

print(findOrder_isolated(4, [[1,0]]))  # [0,1,2,3] or [2,3,0,1] etc.

Masa Penyelesaian Kursus Secara Selari

Kursus Selari II: cari bilangan semester minimum untuk mengambil semua kursus apabila paling banyak k kursus dibenarkan bagi setiap semester dan prasyarat mesti dipatuhi. Ini memerlukan pemprosesan algoritma Kahn mengikut aras, bersama DP topeng bit untuk kekangan pemilihan k — masalah yang jauh lebih sukar kerana menggabungkan pengisihan topologi dengan DP topeng bit.

Strategi Komunikasi Temu Duga

Apabila menghadapi masalah jenis Jadual Kursus dalam temu duga: (1) Kenal pasti masalah itu dengan segera sebagai masalah pengisihan topologi / pengesanan kitaran. (2) Modelkan graf dengan menjelaskan arah sisi. (3) Pilih algoritma Kahn (BFS) untuk kesederhanaan atau DFS kerana lebih biasa. (4) Tangani kes kitaran secara jelas. (5) Nyatakan kerumitan masa O(V+E). Pendekatan berstruktur ini menunjukkan kemahiran menyelesaikan masalah secara sistematik.

Ujian Menyeluruh

Menguji kedua-dua penyelesaian dengan pelbagai data masukan untuk mengesahkan ketepatan. Pendekatan Kahn mengendalikan berbilang susunan yang sah dengan baik — sebarang susunan topologi yang sah boleh diterima sebagai jawapan bagi Jadual Kursus II.

from collections import deque, defaultdict

def findOrder(numCourses, prerequisites):
    graph = defaultdict(list)
    in_degree = [0] * numCourses
    for a, b in prerequisites:
        graph[b].append(a)
        in_degree[a] += 1
    queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
    order = []
    while queue:
        c = queue.popleft(); order.append(c)
        for nxt in graph[c]:
            in_degree[nxt] -= 1
            if in_degree[nxt] == 0: queue.append(nxt)
    return order if len(order) == numCourses else []

print(findOrder(1, []))                    # [0]
print(findOrder(2, [[0,1]]))              # [1, 0]
print(findOrder(3, [[1,0],[2,1]]))        # [0, 1, 2]
print(findOrder(3, [[1,0],[0,1]]))        # [] cycle

Semakan Pantas

Uji pemahaman anda tentang konsep Struktur Data & Algoritma — Persediaan Temu Duga Pengekodan daripada pelajaran ini.

Jawab dalam pelajaran interaktif

Ulang Kaji Pelajaran

Dalam pelajaran ini, anda telah mempelajari bahawa: Jadual Kursus I dan II kedua-duanya menggunakan pengisihan topologi dengan sisi b → a bagi prasyarat [a, b], Jadual Kursus I hanya menyemak bahawa panjang susunan sama dengan n, manakala Jadual Kursus II mengembalikan susunan itu sendiri, dan pengesanan kitaran berasaskan DFS dengan tiga keadaan ialah alternatif yang sah kepada pendekatan BFS Kahn. Seterusnya, kita akan meneroka algoritma Kosaraju untuk Komponen Terhubung Kuat.

Percuma untuk bermula

Pelajari Python dengan tutor kecerdasan buatan — percuma

Tulis dan jalankan kod sebenar dalam pelayar anda, dapatkan bantuan segera daripada tutor kecerdasan buatan yang tersedia 24/7, dan sambung semula dari tempat anda berhenti di web atau dalam aplikasi.

Kursus: 30
Pelajaran: 120

Mula belajar secara percuma Lihat kursus penuh

Soalan Lazim

Adakah pelajaran “Jadual Kursus I dan II” percuma?

Ya — sebanyak 3 pelajaran dalam laluan pembelajaran DSA Interview Prep, termasuk “Jadual Kursus I dan II”, boleh dibaca sepenuhnya secara percuma di web ini. Selepas itu, CoddyKit PRO membuka akses kepada semua pelajaran, serta latihan interaktif dengan penyunting kod terbina dalam dan tutor kecerdasan buatan yang tersedia 24/7. Kursus DSA Interview Prep merangkumi sejumlah 4 pelajaran.

Apakah yang akan saya pelajari dalam “Jadual Kursus I dan II”?

Modelkan prasyarat kursus sebagai graf berarah dan gunakan isihan topologi untuk menentukan sama ada semua kursus boleh diselesaikan serta susunannya. Anda berlatih DSA Interview Prep menggunakan kod praktikal yang dijalankan terus dalam pelayar, manakala tutor kecerdasan buatan 24/7 menjawab soalan anda semasa anda mengikuti pelajaran.

Adakah saya memerlukan pengalaman untuk memulakan DSA Interview Prep?

Tiada pengalaman terdahulu diperlukan. Pembelajaran DSA Interview Prep di CoddyKit disusun untuk pelajar daripada peringkat pemula hingga lanjutan, jadi anda boleh bermula di sini atau dari awal dan belajar mengikut kadar anda sendiri. Ini ialah pelajaran 3 daripada 4.

Berapa lamakah pelajaran “Jadual Kursus I dan II” diambil?

Kebanyakan pelajaran CoddyKit mengambil masa kira-kira 5–10 minit. Setiap pelajaran ringkas dan interaktif, jadi anda boleh membuat kemajuan secara berterusan dan menyambung tepat dari tempat anda berhenti di web atau aplikasi.

Bolehkah saya menulis dan menjalankan kod dalam pelajaran DSA Interview Prep ini?

Ya. Setiap pelajaran DSA Interview Prep menyertakan penyunting kod terbina dalam, jadi anda boleh menulis dan menjalankan kod sebenar terus dalam pelayar serta menerima maklum balas kecerdasan buatan serta-merta — tanpa memerlukan persediaan setempat.

Semua pelajaran dalam kursus ini

← Kembali ke DSA Interview Prep