課程時間表IV

1462。課程表四

難度：中等

主題：深度優先搜索、廣度優先搜索、圖、拓撲排序

您必須修讀總共 numCourses 課程，標記為從 0 到 numCourses - 1。您將獲得一個數組先決條件，其中先決條件[i] = [a_i, b_i ] 表示您必須首先學習課程a _i，如果您想參加課程b_i.

• 例如，[0, 1]對錶示您必須先選修課程 0，然後才能選修課程 1。

先決條件也可以是間接。如果課程a是課程b的先決條件，課程b是課程c的先決條件，那麼課程a是課程c的先決條件。

您還會獲得一個數組查詢，其中querys[j] = [u_j, v_j]。對於第 j^th 查詢，您應該回答課程 u_j 是否是課程 v_j 的先決條件。

返回一個布爾數組答案，其中answer[j]是第j^第查詢的答案。

示例1：

• 輸入： 課程數 = 2，先決條件 = [[1,0]]，查詢 = [[0,1],[1,0]]
• 輸出： [假，真]
• 說明： [1, 0] 對錶示您必須先學習課程 1，然後才能學習課程 0。 課程 0 並不是課程 1 的先決條件，反之亦然。

示例2：

• 輸入： 課程數 = 2，先決條件 = []，查詢 = [[1,0],[0,1]]
• 輸出： [假，假]
• 說明：沒有先決條件，每門課程都是獨立的。

示例 3：

• 輸入： 課程數= 3，先決條件= [[1,2],[1,0],[2,0]]，查詢= [[1,0],[1,2] ]
• 輸出： [true,true]

約束：

• 2
• 0
• 先決條件[i].length == 2
• 0 i, b_i
• a_i != b_i
• 所有對 [a_i, b_i] 都是唯一的。
• 先決條件圖沒有循環。
• 1 4
• 0 i, v_i
• u_i != v_i

提示：

1. 想像一下，如果課程是圖表的節點。我們需要建立一個陣列 isReachable[i][j].
2. 從每個課程 i 開始一個 bfs，並為您訪問的每個課程 j 分配 isReachable[i][j] = True。
3. 回答來自 isReachable 陣列的查詢。

解：

我們可以使用圖形表示和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]
?>

解釋：

1. 圖片初始化：

   • $isReachable 2D 陣列初始化為 false，表示最初無法從另一個課程到達。

2. 直接先決條件：

   • 我們根據先決條件填入 $isReachable 陣列。對於每個先決條件 [a, b]，課程 a 必須在課程 b 之前學習。

3. Floyd-Warshall 演算法：

   • 此演算法計算圖的傳遞閉包。
   • 對於每個中間課程 k，我們檢查從課程 j 到 k 是否可以到達課程 i。如果是，我們標記 $isReachable[i][j] = true。

4. 查詢評估：

   • 每個查詢 [u, v] 只需檢查 $isReachable[u][v] 的值即可得到答案。

複雜：

• 時間複雜度：
  • Floyd-Warshall 演算法：O(numCourses³)
  • 查詢：O(queries.length)
  • 總計：O(numCourses³查詢.長度)
• 空間複雜度：
  • $isReachable 陣列所使用的空間為 O(numCourses²).

演練範例：

輸入：

$numCourses = 3;
$prerequisites = [[1, 2], [1, 0], [2, 0]];
$queries = [[1, 0], [1, 2]];

執行：

1. 初始化圖表後：

   $isReachable = [
       [false, false, false],
       [false, false, true],
       [false, false, false]
   ];

1. 佛洛伊德‧沃歇爾之後：

   $isReachable = [
       [false, false, false],
       [true, false, true],
       [true, false, false]
   ];

1. 回答問題：
   • 查詢 [1, 0]: true
   • 查詢 [1, 2]: true

輸出：

[true, true]

聯絡連結

如果您發現本系列有幫助，請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！

如果您想要更多類似的有用內容，請隨時關注我：

• 領英
• GitHub

以上是課程時間表IV的詳細內容。更多資訊請關注PHP中文網其他相關文章！