1462。課程表四
難度:中等
主題:深度優先搜索、廣度優先搜索、圖、拓撲排序
您必須修讀總共 numCourses 課程,標記為從 0 到 numCourses - 1。您將獲得一個數組先決條件,其中先決條件[i] = [ai, bi ] 表示您必須首先學習課程a i,如果您想參加課程bi.
先決條件也可以是間接。如果課程a是課程b的先決條件,課程b是課程c的先決條件,那麼課程a是課程c的先決條件。
您還會獲得一個數組查詢,其中querys[j] = [uj, vj]。對於第 jth 查詢,您應該回答課程 uj 是否是課程 vj 的先決條件。
返回一個布爾數組答案,其中answer[j]是第j第查詢的答案。
示例1:
示例2:
示例 3:
約束:
提示:
解:
我們可以使用圖形表示和Floyd-Warshall演算法來計算每個課程是否可以從另一個課程到達。這種方法將有效地處理先決條件關係,並允許我們直接回答查詢。
讓我們用 PHP 實作這個解:1462。課表四
<?php /** * @param Integer $numCourses * @param Integer[][] $prerequisites * @param Integer[][] $queries * @return Boolean[] */ function checkIfPrerequisite($numCourses, $prerequisites, $queries) { ... ... ... /** * go to ./solution.php */ } // Example usage: $numCourses = 2; $prerequisites = [[1,0]]; $queries = [[0,1],[1,0]]; $result = checkIfPrerequisite($numCourses, $prerequisites, $queries); print_r($result); // Output: [false,true] $numCourses = 2; $prerequisites = []; $queries = [[1,0],[0,1]] $result = checkIfPrerequisite($numCourses, $prerequisites, $queries); print_r($result); // Output: [false,false] $numCourses = 3; $prerequisites = [[1, 2], [1, 0], [2, 0]]; $queries = [[1, 0], [1, 2]]; $result = checkIfPrerequisite($numCourses, $prerequisites, $queries); print_r($result); // Output: [true, true] ?>
圖片初始化:
直接先決條件:
Floyd-Warshall 演算法:
查詢評估:
$numCourses = 3; $prerequisites = [[1, 2], [1, 0], [2, 0]]; $queries = [[1, 0], [1, 2]];
$isReachable = [ [false, false, false], [false, false, true], [false, false, false] ];
$isReachable = [ [false, false, false], [true, false, true], [true, false, false] ];
[true, true]
聯絡連結
如果您發現本系列有幫助,請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子? 。您的支持對我來說意義重大!
如果您想要更多類似的有用內容,請隨時關注我:
以上是課程時間表IV的詳細內容。更多資訊請關注PHP中文網其他相關文章!