課程表系列(BFS)

廣度優先搜索

文章目錄

廣度優先搜索
- 207. 課程表
- 210. 課程表 II
- - 思路
- 630. 課程表 III
- 1462. 課程表 IV
- 547. 省份數量

207. 課程表

你這個學期必須選修 numCourses 門課程，記為 0 到 numCourses - 1 。

在選修某些課程之前需要一些先修課程。先修課程按數組 prerequisites 給出，其中 prerequisites[i] = [ai, bi] ，表示如果要學習課程 ai 則必須先學習課程 bi 。

例如，先修課程對 [0, 1] 表示：想要學習課程 0 ，你需要先完成課程 1 。

請你判斷是否可能完成所有課程的學習？如果可以，返回 true ；否則，返回 false 。

示例 1：

輸入：numCourses = 2, prerequisites = [[1,0]]
輸出：true
解釋：總共有 2 門課程。學習課程 1 之前，你需要完成課程 0 。這是可能的。

示例 2：

輸入：numCourses = 2, prerequisites = [[1,0],[0,1]]
輸出：false
解釋：總共有 2 門課程。學習課程 1 之前，你需要先完成課程 0 ；并且學習課程 0 之前，你還應先完成課程 1 。這是不可能的。

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;class Solution {public boolean canFinish(int numCourses, int[][] prerequisites) {List<List<Integer>> list=new ArrayList<List<Integer>>();//鄰接表存圖for(int i=0;i<numCourses;i++)list.add(new ArrayList<>());int[] indeg=new int[numCourses];//入度數組,下標對應結點for(int i=0;i<prerequisites.length;i++){list.get(prerequisites[i][0]).add(prerequisites[i][1]);//創建鄰接表indeg[prerequisites[i][1]]++;//入度+1}Queue<Integer> queue=new LinkedList<>();//遍歷時,用于存每個結點的隊列,這里的結點形式是在鄰接表中對應的下標//尋找入度為0的結點，當作起點加入隊列中for(int i=0;i<numCourses;i++){if(indeg[i]==0)queue.add(i);}//bfs部分while(!queue.isEmpty()){//將出度為0的結點全部出隊for(int i=queue.size();i>0;i--){//獲取結點的下標,并出隊Integer node=queue.poll();//遍歷該結點到達了哪些結點,并將那些結點入度-1;for(Integer j:list.get(node)){indeg[j]--;//可以學習該課程了，入隊if(indeg[j]==0){queue.add(j);}}}}//最后判斷入度數組是否全為0for(int i=0;i<numCourses;i++){if(indeg[i]!=0)return false;}return true;}
}

210. 課程表 II

現在你總共有 numCourses 門課需要選，記為 0 到 numCourses - 1。給你一個數組 prerequisites ，其中 prerequisites[i] = [ai, bi] ，表示在選修課程 ai 前必須先選修 bi 。

例如，想要學習課程 0 ，你需要先完成課程 1 ，我們用一個匹配來表示：[0,1] 。

返回你為了學完所有課程所安排的學習順序。可能會有多個正確的順序，你只要返回 任意一種 就可以了。如果不可能完成所有課程，返回 一個空數組 。

示例 1：

輸入：numCourses = 2, prerequisites = [[1,0]]
輸出：[0,1]
解釋：總共有 2 門課程。要學習課程 1，你需要先完成課程 0。因此，正確的課程順序為 [0,1] 。

思路

本題與課程表1很相似，唯一區別：只是改了學習箭頭反過來了，然后在層序遍歷的同時將遍歷的結點存起來

class Solution {public int[] findOrder(int numCourses, int[][] prerequisites) {List<List<Integer>> list=new ArrayList<List<Integer>>();//鄰接表存圖int[] res=new int[numCourses];//學習課程順序for(int i=0;i<numCourses;i++)list.add(new ArrayList<>());int[] indeg=new int[numCourses];//入度數組,下標對應結點for(int i=0;i<prerequisites.length;i++){list.get(prerequisites[i][1]).add(prerequisites[i][0]);//創建鄰接表indeg[prerequisites[i][0]]++;//入度+1}Queue<Integer> queue=new LinkedList<>();//遍歷時,用于存每個結點的隊列,這里的結點形式是在鄰接表中對應的下標//尋找入度為0的結點，當作起點加入隊列中for(int i=0;i<numCourses;i++){if(indeg[i]==0)queue.add(i);}//bfs部分int index=0;while(!queue.isEmpty()){//將出度為0的結點全部出隊for(int i=queue.size();i>0;i--){//獲取結點的下標,并出隊Integer node=queue.poll();res[index++]=node;//遍歷該結點到達了哪些結點,并將那些結點入度-1;for(Integer j:list.get(node)){indeg[j]--;//可以學習該課程了，入隊if(indeg[j]==0){queue.add(j);}}}}for(int i=0;i<numCourses;i++){if(indeg[i]!=0)return new int[]{};}return res;}
}

630. 課程表 III

這里有 n 門不同的在線課程，按從 1 到 n 編號。給你一個數組 courses ，其中 courses[i] = [durationi, lastDayi] 表示第 i 門課將會持續上 durationi 天課，并且必須在不晚于 lastDayi 的時候完成。

你的學期從第 1 天開始。且不能同時修讀兩門及兩門以上的課程。

返回你最多可以修讀的課程數目。

示例 1：

輸入：courses = [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]]
輸出：3
解釋：
這里一共有 4 門課程，但是你最多可以修 3 門：
首先，修第 1 門課，耗費 100 天，在第 100 天完成，在第 101 天開始下門課。
第二，修第 3 門課，耗費 1000 天，在第 1100 天完成，在第 1101 天開始下門課程。
第三，修第 2 門課，耗時 200 天，在第 1300 天完成。
第 4 門課現在不能修，因為將會在第 3300 天完成它，這已經超出了關閉日期。

import java.util.Arrays;
import java.util.PriorityQueue;//leetcode submit region begin(Prohibit modification and deletion)
class Solution {public int scheduleCourse(int[][] courses) {Arrays.sort(courses,(a,b)->a[1]-b[1]);PriorityQueue<Integer> queue=new PriorityQueue<>((a,b)->b-a);//耗時時間從大到小進行排序int s=0;for(int[] a:courses){int b=a[0],e=a[1];queue.add(b);s+=b;while(s>e){s-=queue.poll();}}return queue.size();}
}

1462. 課程表 IV

你總共需要上 numCourses 門課，課程編號依次為 0 到 numCourses-1 。你會得到一個數組 prerequisite ，其中 prerequisites[i] = [ai, bi] 表示如果你想選 bi 課程，你必須先選 ai 課程。

有的課會有直接的先修課程，比如如果想上課程 1 ，你必須先上課程 0 ，那么會以 [0,1] 數對的形式給出先修課程數對。

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

你也得到一個數組 queries ，其中 queries[j] = [uj, vj]。對于第 j 個查詢，您應該回答課程 uj 是否是課程 vj 的先決條件。

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

示例 1：

輸入：numCourses = 2, prerequisites = [[1,0]], queries = [[0,1],[1,0]]
輸出：[false,true]
解釋：課程 0 不是課程 1 的先修課程，但課程 1 是課程 0 的先修課程。

示例 2：

輸入：numCourses = 2, prerequisites = [], queries = [[1,0],[0,1]]
輸出：[false,false]
解釋：沒有先修課程對，所以每門課程之間是獨立的。

import java.util.*;class Solution {public List<Boolean> checkIfPrerequisite(int numCourses, int[][] prerequisites, int[][] queries) {int[] indeg=new int[numCourses];List<Boolean> res=new ArrayList<>();Boolean[][] grid=new Boolean[numCourses][numCourses];List<List<Integer>> list = new ArrayList<List<Integer>>();//鄰接表存圖for (int i = 0; i < numCourses; i++) {list.add(new ArrayList<>());grid[i]=new Boolean[numCourses];Arrays.fill(grid[i],false);}for (int i = 0; i < prerequisites.length; i++) {list.get(prerequisites[i][0]).add(prerequisites[i][1]);indeg[prerequisites[i][1]]++;}Queue<Integer> queue = new LinkedList<>();//先將入度為0入隊for (int i = 0; i < numCourses; i++) {if (indeg[i] == 0)queue.add(i);}while (!queue.isEmpty()) {for (int i = queue.size(); i > 0; i--) {Integer node = queue.poll();for (Integer j : list.get(node)) {grid[node][j]=true;for(int k=0;k<numCourses;k++){grid[k][j]=grid[k][j] || grid[k][node];}indeg[j]--;if (indeg[j] == 0) queue.add(j);}}}for(int[] a:queries){res.add(grid[a[0]][a[1]]);}return res;}}

547. 省份數量

有 n 個城市，其中一些彼此相連，另一些沒有相連。如果城市 a 與城市 b 直接相連，且城市 b 與城市 c 直接相連，那么城市 a 與城市 c 間接相連。

省份是一組直接或間接相連的城市，組內不含其他沒有相連的城市。

給你一個 n x n 的矩陣 isConnected ，其中 isConnected[i][j] = 1 表示第 i 個城市和第 j 個城市直接相連，而 isConnected[i][j] = 0 表示二者不直接相連。

返回矩陣中省份的數量。

示例 1：

輸入：isConnected = [[1,1,0],[1,1,0],[0,0,1]]
輸出：2

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;//leetcode submit region begin(Prohibit modification and deletion)
class Solution {public int findCircleNum(int[][] isConnected) {int n=isConnected.length;List<List<Integer>> grid=new ArrayList<>();//鄰接表//存圖for(int i=0;i<n;i++) {grid.add(new ArrayList<>());for (int j = 0; j < n; j++) {if (isConnected[i][j] == 1)grid.get(i).add(j);}}boolean[] visit=new boolean[n];int res=0;for(int i=0;i<n;i++){Queue<Integer> queue=new LinkedList<>();if(visit[i]==false){res++;visit[i]=true;queue.add(i);//bsf部分while(!queue.isEmpty()){Integer node=queue.poll();//遍歷該結點連接的結點for(Integer j:grid.get(node)){if(!visit[j])queue.add(j);visit[j]=true;}}}}return res;}
}