首頁 > 後端開發 > php教程 > 課程時間表IV

課程時間表IV

Patricia Arquette
發布: 2025-01-28 00:03:40
原創
690 人瀏覽過

1462。課程表四

難度:中等

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

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

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

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

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

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

示例1:

課程時間表IV

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

示例2:

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

示例 3:

課程時間表IV

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

約束:

  • 2
  • 0
  • 先決條件[i].length == 2
  • 0 i, bi
  • ai != bi
  • 所有對 [ai, bi] 都是唯一的。
  • 先決條件圖沒有循環。
  • 1 4
  • 0 i, vi
  • ui != vi

提示:

  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(numCourses3)
    • 查詢:O(queries.length)
    • 總計:O(numCourses3查詢.長度)
  • 空間複雜度:
    • $isReachable 陣列所使用的空間為 O(numCourses2).

演練範例:

輸入:

$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中文網其他相關文章!

本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
作者最新文章
熱門教學
更多>
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板