1. 子集类型(直接添加结果子集，从i或i+1开始遍历，不需要visited判断重复搜索)：原数组所有可能的组合。因此要从i+1继续搜。不需要使用visited防止重复搜索(因为不是从0开始遍历)
输入: nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
或
输入: [1,2,2]
输出:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
- 有重复元素，先排序去重
class Solution {
public List<List<Integer>> result = new ArrayList<>();
public List<Integer> list = new ArrayList<>();
public List<List<Integer>> subsetsWithDup(int[] nums) {
/*
子集，有重复，要去重，先排序
8.23
*/
if(nums.length == 0){
return result;
}
//有重复元素，解集不允许重复，先排序
Arrays.sort(nums);
dfs(nums,0);
return result;
}
public void dfs(int[] nums,int index){
//result直接添加list
result.add(new ArrayList<>(list));
for(int i=index;i<nums.length;i++){
//去重
if(i > index && nums[i] == nums[i-1]){
continue;
}
list.add(nums[i]);
dfs(nums,i+1);
list.remove(list.size()-1);
}
}
}
- 无重复元素，直接进行dfs
class Solution {
public ArrayList<List<Integer>> result = new ArrayList<>();
public ArrayList<Integer> list = new ArrayList<>();
public List<List<Integer>> subsets(int[] nums) {
/*
子集，无重复，index从0开始
8.23
*/
//dfs所有组合模板
if(nums.length < 1){
return result;
}
//索引从0开始
dfs(nums,0);
return result;
}
public void dfs(int[] nums,int index){
result.add(new ArrayList<>(list));
for(int i=index;i<nums.length;i++){
//list直接添加当前nums[i]
list.add(nums[i]);
//继续添加下一个元素
dfs(nums,i+1);
//剪枝
list.remove(list.size()-1);
}
}
}
2. 全排列(从0开始遍历，需要visited判断重复复搜索，结果子集长度与原数组长度一致)：找出所有和原数组长度相同的组合。每次递归都从0开始搜索nums数组，需要visited数组判断重复搜索
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
或
输入: [1,1,2]
输出:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
- 全排列：无重复元素，直接进行dfs
class Solution {
public ArrayList<List<Integer>> result = new ArrayList<>();
public ArrayList<Integer> list = new ArrayList<>();
public List<List<Integer>> permute(int[] nums) {
/*
全排列，无重复。
8.23
*/
//因为全排列，每次都重新遍历数组，需要visited防止重复搜索
if(nums.length == 0){
return result;
}
boolean[] visited = new boolean[nums.length];
dfs(nums,visited);
return result;
}
public void dfs(int[] nums,boolean[] visited){
//递归出口：当list长度等于nums长度时
if(list.size() == nums.length){
result.add(new ArrayList<>(list));
return;
}
//全排列，长度和原数组一直，从0开始重新遍历，用visited来防止重复搜索
for(int i=0;i<nums.length;i++){
if(visited[i]){
continue;
}
visited[i] = true;
list.add(nums[i]);
dfs(nums,visited);
visited[i] = false;
list.remove(list.size()-1);
}
}
}
- 全排列：有重复元素，先排序，在遍历过程中进行去重
class Solution {
public List<List<Integer>> result = new ArrayList<>();
public List<Integer> list = new ArrayList<>();
public List<List<Integer>> permuteUnique(int[] nums) {
/*
全排列：有重复元素，先去重
8.23
*/
if(nums.length == 0){
return result;
}
Arrays.sort(nums);
boolean[] visited = new boolean[nums.length];
dfs(nums,visited);
return result;
}
public void dfs(int[] nums,boolean[] visited){
//递归出口：当list长度和nums长度一致时
if(nums.length == list.size()){
result.add(new ArrayList<>(list));
return;
}
for(int i=0;i<nums.length;i++){
if(visited[i]){
continue;
}
if(i > 0 && nums[i] == nums[i-1] && visited[i-1]){
continue;
}
visited[i] = true;
list.add(nums[i]);
dfs(nums,visited);
visited[i] = false;
list.remove(list.size()-1);
}
}
}
- 字符串全排列：输入一个字符串，打印出该字符串中字符的所有排列。
输入：s = "abc"
输出：["abc","acb","bac","bca","cab","cba"]
class Solution {
List<String> result = new ArrayList<>();
public String[] permutation(String s) {
/*
字符串全排序：可能有重复字符串，先转换为字符数组，然后排序，进行去重。全排列，要用visited判断重复搜索
8.23
*/
char[] str = s.toCharArray();
Arrays.sort(str);
boolean[] visited = new boolean[str.length];
//初始化temp为""，传入visited
dfs(str,"",visited);
//将List转为String数组
return result.toArray(new String[result.size()]);
}
public void dfs(char[] str,String temp,boolean[] visited){
//递归出口：当str.length() == temp.length()
if(str.length == temp.length()){
result.add(temp);
return;
}
//全排列，从0开始
for(int i=0;i<str.length;i++){
if(visited[i]){
continue;
}
//去重
if(i > 0 && str[i] == str[i-1] && visited[i-1]){
continue;
}
visited[i] = true;
dfs(str,temp+str[i],visited);
visited[i] = false;
}
}
}
- 电话号码的字母组合：给定一个
输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
class Solution {
ArrayList<String> result = new ArrayList<>();
//使用HashMap存储电话数字和字符串
HashMap<Character,String> map = new HashMap<>();
String digits = "";
public List<String> letterCombinations(String digits) {
/*
电话号码的字母组合，先用HashMap预存。递归时通过index提取当前字符串。全排列类型。遍历从0开始
8.23
*/
if(digits.length() == 0){
return result;
}
//初始化map
map.put('2', "abc");
map.put('3', "def");
map.put('4', "ghi");
map.put('5', "jkl");
map.put('6', "mno");
map.put('7', "pqrs");
map.put('8', "tuv");
map.put('9', "wxyz");
//初始化digits，用于作为key提取value
this.digits = digits;
//index为0，初始化temp为""
dfs(0,"");
return result;
}
public void dfs(int index,String temp){
//递归出口，如果temp的长度等于digits的长度
if(temp.length() == digits.length()){
result.add(temp);
return;
}
//提取当前digits的index对应value
String str = map.get(digits.charAt(index));
//遍历str，全排列，从0开始遍历
for(int i=0;i<str.length();i++){
//index+1，temp添加当前字符
dfs(index+1,temp+str.charAt(i));
}
}
}
3. 组合总和(要递减，先排序，递减到0就添加，从i或i+1开始遍历)：给定一个目标值，求数组元素所能组成的和为target的组合。每次递归遍历不用从0开始，target递减当前元素
输入：candidates = [2,3,6,7], target = 7,
所求解集为：
[
[7],
[2,2,3]
]
或
输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
- 组合总和：无重复、元素可以使用无限次
class Solution {
public ArrayList<List<Integer>> result = new ArrayList<>();
public ArrayList<Integer> list = new ArrayList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
/*
组合总和，
1. 无重复，不需要去重。
2. target要递减，先排序。
3. 因为元素可以多次使用，因此遍历从i开始，所以不需要使用visited判断重复搜索。遍历过程先判断递减之后是否越界
8.23
*/
if(candidates.length == 0){
return result;
}
Arrays.sort(candidates);
dfs(candidates,0,target);
return result;
}
public void dfs(int[] candidates,int index,int target){
//递归出口
if(target == 0){
result.add(new ArrayList<>(list));
return;
}
for(int i=index;i<candidates.length;i++){
//防止溢出
if(target - candidates[i] < 0){
break;
}
list.add(candidates[i]);
dfs(candidates,i,target-candidates[i]);
list.remove(list.size()-1);
}
}
}
- 组合总和：有重复，元素只能使用一次
class Solution {
public List<List<Integer>> result = new ArrayList<>();
public List<Integer> list = new ArrayList<>();
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
/*
组合总和：有重复元素，元素不允许使用多次
8.23
*/
if(candidates.length == 0){
return result;
}
//target要递减并且有重复要去重
Arrays.sort(candidates);
dfs(candidates,target,0);
return result;
}
public void dfs(int[] candidates,int target,int index){
//递归出口
if(target == 0){
result.add(new ArrayList<>(list));
return;
}
for(int i=index;i<candidates.length;i++){
//防溢出
if(target - candidates[i] < 0){
break;
}
//去重
if(i > index && candidates[i] == candidates[i-1]){
continue;
}
list.add(candidates[i]);
dfs(candidates,target-candidates[i],i+1);
list.remove(list.size()-1);
}
}
}
- 组合总和：找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
class Solution {
public ArrayList<List<Integer>> result = new ArrayList<>();
public ArrayList<Integer> list = new ArrayList<>();
public List<List<Integer>> combinationSum3(int k, int n) {
/*
组合总和：和1、2同理，甚至更简单。遍历从1到9
8.23
*/
//n和k用于终止递归，当n递减i到0且k == list.size()时
dfs(1,n,k);
return result;
}
public void dfs(int start,int end,int k){
//递归出口：当end递减到0且list.size() == k时
if(end == 0 && list.size() == k){
result.add(new ArrayList<>(list));
return;
}
//1到9
for(int i=start;i<=9;i++){
list.add(i);
dfs(i+1,end-i,k);
list.remove(list.size()-1);
}
}
}
- 组合：给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
class Solution {
public List<List<Integer>> result = new ArrayList<>();
public List<Integer> list = new ArrayList<>();
public List<List<Integer>> combine(int n, int k) {
/*
组合：1到n数组中长度为k的组合
8.23
*/
dfs(1,n,k);
return result;
}
public void dfs(int start,int end,int k){
//递归出口：当list.size() == k
if(list.size() == k){
result.add(new ArrayList<>(list));
return;
}
for(int i=start;i<=end;i++){
list.add(i);
dfs(i+1,end,k);
list.remove(list.size()-1);
}
}
}
- 目标和：在给定数组中找出可以通过加减使和为S的组合个数。逆向思维：找出可以通过加减使S为0的组合
class Solution {
int result = 0;
public int findTargetSumWays(int[] nums, int S) {
/*
目标和：非负数整数数组，要求能过通过加减得到S，求有多少种方法(逆向思维，求有多少种组合能够通过加和减使S为0)
8.23
*/
//index从0开始
dfs(nums,S,0);
return result;
}
public void dfs(int[] nums,int S,int index){
//递归出口，当S == 0且index == nums.length
if(S == 0 && index == nums.length){
result++;
return;
}
//如果不符合S == 0的要求
if(index == nums.length){
return;
}
//S + nums[index]
dfs(nums,S+nums[index],index+1);
//S - nums[index]
dfs(nums,S-nums[index],index+1);
}
}
- 24点游戏(B站笔试)：类似目标和，只不过多了乘和除。除的时候要判断除数(nums[index])不能为0
Class Solution{
static boolean result = true;
private static boolean Game24(int[] nums) {
if(nums.length == 0){
return false;
}
dfs(nums,24,0);
return result;
}
private static void dfs(int[] nums, int sum, int index) {
//递归出口：如果sum == 0且index == nums.length
if(sum == 0 && index == nums.length){
result = true;
return;
}
//如果不符合要求
if(index == nums.length){
result = false;
return;
}
//加减乘除使24为0
dfs(nums,sum+nums[index],index+1);
dfs(nums,sum-nums[index],index+1);
dfs(nums,sum*nums[index],index+1);
if(nums[index] != 0){
dfs(nums,sum/nums[index],index+1);
}
}
}
- 丢弃最少物品(网易笔试)：分与不分
- 题目：给出n个物品，每个物品都有自己的价值，每个物品只有一件，这些物品需要分给两个人，要求分配完之后，两个人的物品价值相同。分配完成之后，会丢弃剩下的物品，求最少要丢弃多少物品。
输入
输入第一行为总的测试数据个数，第二行为物品个数n，第三行为n个物品的价值。
1
5
30 60 5 15 30
输出
20 丢弃5和15，把60分配给第一个人，2个30分配给第二个人。
- 使用dfs，分给A，分给B，都不分
import java.util.Scanner;
public class Solution{
public static int result = Integer.MAX_VALUE;
public static int sum = 0;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
//用例数
int group = sc.nextInt();
while(group-- > 0){
int len = sc.nextInt();
int[] nums = new int[len];
for(int i=0;i<nums.length;i++){
nums[i] = sc.nextInt();
//先计算sum，用于判断分得的两次结果是否相等
sum += nums[i];
}
//index为0，第一个人拥有的为0，第二个人拥有的为0
dfs(nums,0,0,0);
System.out.println(result);
}
}
private static void dfs(int[] nums, int index, int result1, int result2) {
//递归出口
if(index == nums.length){
//判断result1 == result2
if(result1 == result2){
//取小的值，(result1和result2一样)
result = Math.min(result,sum - 2*result1);
}
return;
}
//1. 谁也不给
dfs(nums,index+1,result1,result2);
//2. 给A
dfs(nums,index+1,result1+nums[index],result2);
//3. 给B
dfs(nums,index+1,result1,result2+nums[index]);
}
}
- 括号生成：数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
class Solution {
ArrayList<String> result = new ArrayList<>();
public List<String> generateParenthesis(int n) {
/*
括号生成
7.22
*/
//dfs，[n,n]中心扩散
dfs(n,n,"");
return result;
}
public void dfs(int left,int right,String temp){
//递归出口
if(left == 0 && right == 0){
result.add(temp);
return;
}
//如果left > 0，拼接左半
if(left > 0){
dfs(left-1,right,temp+"(");
}
//如果right > left，拼接右半
if(right > left){
dfs(left,right-1,temp+")");
}
}
}
4. 树路径
- 路径总和(路径数目)：判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
/*
判断是否存在到某个值的路径总和
8.23
*/
//要求从根节点开始，所以sum先递减root.val
if(root == null){
return false;
}
sum -= root.val;
//如果sum为0且左右子树都为空，说明存在一条路径
if(sum == 0 && root.left == null && root.right == null){
return true;
}
//递归左右子树，存在一条即可
return hasPathSum(root.left,sum) || hasPathSum(root.right,sum);
}
}
- 路径总和(路径集合)：找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
class Solution {
ArrayList<List<Integer>> result = new ArrayList<>();
ArrayList<Integer> list = new ArrayList<>();
public List<List<Integer>> pathSum(TreeNode root, int sum) {
/*
路经总和，找路径组合
8.23
*/
dfs(root,sum);
return result;
}
public void dfs(TreeNode node,int sum){
//递归出口
if(node == null){
return;
}
//list先添加当前节点值
list.add(node.val);
//sum递减当前节点值
sum -= node.val;
//如果sum递减到0并且左右子树为空，result添加list。否则继续递归左右子树
if(sum == 0 && node.left == null && node.right == null){
result.add(new ArrayList<>(list));
}else{
dfs(node.left,sum);
dfs(node.right,sum);
}
//回溯
list.remove(list.size()-1);
}
}
- 二叉树的左/右视图：给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
class Solution {
ArrayList<Integer> result = new ArrayList<>();
int depth = 0;
public List<Integer> rightSideView(TreeNode root) {
/*
二叉树的右视图，先递归右子树，搜完右子树就return。需要一个深度depth变量控制添加每一层的值
8.23
*/
if(root == null){
return result;
}
//当前深度为0
dfs(root,0);
return result;
}
public void dfs(TreeNode root,int curDepth){
//递归出口，搜完右子树就return
if(root == null){
return;
}
//如果当前深度一致
if(curDepth == depth){
result.add(root.val);
depth++;
}
//先搜索右子树
dfs(root.right,curDepth+1);
dfs(root.left,curDepth+1);
}
}
- 二叉树最大路径和：从随机节点出发到随即节点所能组成的最大路径和是多少
输入: [-10,9,20,null,null,15,7]
-10
/ \
9 20
/ \
15 7
输出: 42
class Solution {
int result = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
/*
二叉树中的最大路径和：从任意节点出发到任意节点的路径所组成的最大路径的和为多少
8.23
*/
dfs(root);
return result;
}
public int dfs(TreeNode root){
//递归出口
if(root == null){
return 0;
}
//左子树最大值，和0比较
int left = Math.max(0,dfs(root.left));
//右子树最大值，和0比较
int right = Math.max(0,dfs(root.right));
//提取本次递归结果，和result比较
result = Math.max(result,left + right + root.val);
//返回本次结果：root + max(左,右)
return root.val + Math.max(left,right);
}
}
5. 二维dfs：典型岛屿3问、单词搜索
- 单词搜索：可以直接修改原矩阵或者使用visited[][]绑定
class Solution {
public boolean exist(char[][] board, String word) {
/*
单词搜索：二维dfs，要判断重复搜索，可以直接修改原矩阵为不属于矩阵数据类型的值，比如'/'。也可以使用visited数组判断。
8.23
*/
char[] str = word.toCharArray();
//遍历矩阵
for(int i=0;i<board.length;i++){
for(int j=0;j<board[0].length;j++){
//返回dfs搜索的结果
return dfs(i,j,board,str,0);
}
}
return true;
}
public boolean dfs(int row,int col,char[][] board,char[] str,int index){
//false出口
if(row < 0 || row >= board.length || col < 0 || col >= board[0].length || board[row][col] != str[index]){
return false;
}
//true出口，如果index能够到达str.length-1
if(index == str.length-1){
return true;
}
//修改当前字符为'/'，防止重复搜索
board[row][col] = '/';
//上下左右搜索
boolean result = dfs(row+1,col,board,str,index+1) || dfs(row-1,col,board,str,index+1) || dfs(row,col+1,board,str,index+1) || dfs(row,col-1,board,str,index+1);
return result;
}
}
- 岛屿周长：当数字为1时进行dfs。统计递归结果。因为矩阵只有0和1，可以直接修改原矩阵来防止重复搜索
class Solution {
public int islandPerimeter(int[][] grid) {
/*
岛屿周长：当数字为1时，进行dfs。统计递归结果，如果已经搜索过，返回0，否则返回1
8.23
*/
if(grid.length == 0 || grid[0].length == 0){
return 0;
}
for(int i=0;i<grid.length;i++){
for(int j=0;j<grid[0].length;j++){
if(grid[i][j] == 1){
return dfs(i,j,grid);
}
}
}
return 0;
}
public int dfs(int row,int col,int[][] grid){
//1出口：当上下左右为0时，边长+1
if(row < 0 || row >= grid.length || col < 0 || col >= grid[0].length || grid[row][col] == 0){
return 1;
}
//0出口
if(grid[row][col] == 2){
return 0;
}
//绑定当前位置
grid[row][col] = 2;
//返回递归上下左右的结果
return dfs(row+1,col,grid) + dfs(row-1,col,grid) + dfs(row,col+1,grid) + dfs(row,col-1,grid);
}
}
- 岛屿数量：当字符为1时进行dfs，完成一次就+1。可以直接修改原矩阵
class Solution {
public int numIslands(char[][] grid) {
/*
岛屿数量：当字符为1时进行dfs，完成一次，数量 + 1。
8.23
*/
if(grid.length == 0 || grid[0].length == 0){
return 0;
}
int result = 0;
for(int i=0;i<grid.length;i++){
for(int j=0;j<grid[0].length;j++){
if(grid[i][j] == '1'){
dfs(i,j,grid);
result++;
}
}
}
return result;
}
public void dfs(int row,int col,char[][] grid){
//递归出口，
if(row < 0 || row >= grid.length || col < 0 || col >= grid[0].length || grid[row][col] == '0'){
return;
}
//绑定当前位置，修改为0
grid[row][col] = '0';
//搜索上下左右
dfs(row+1,col,grid);
dfs(row-1,col,grid);
dfs(row,col+1,grid);
dfs(row,col-1,grid);
}
}
- 岛屿最大面积：Math.max()比较每次的结果
class Solution {
public int maxAreaOfIsland(int[][] grid) {
/*
岛屿最大面积：max比较每次递归结果
8.23
*/
if(grid.length == 0 || grid[0].length == 0){
return 0;
}
int result = 0;
for(int i=0;i<grid.length;i++){
for(int j=0;j<grid[0].length;j++){
if(grid[i][j] == 1){
result = Math.max(result,dfs(i,j,grid));
}
}
}
return result;
}
public int dfs(int row,int col,int[][] grid){
//递归0出口：grid[row][col] = 0
if(row < 0 || row >= grid.length || col < 0 || col >= grid[0].length || grid[row][col] == 0){
return 0;
}
//绑定当前位置
grid[row][col] = 0;
//没有就为1
int size = 1;
return size + dfs(row+1,col,grid) + dfs(row-1,col,grid) + dfs(row,col+1,grid) + dfs(row,col-1,grid);
}
}
6. 图经典问题(还没搞懂...)：朋友圈、课程表
- 朋友圈
class Solution {
public int findCircleNum(int[][] M) {
/*
朋友圈：图的邻接块.DFS 整体思路：假设以第一个学生为例，首先应找到与该学生是朋友的所有人，找到一个朋友时且没有并访问，则找到该朋友的朋友，这样就能找到与第一个学生有间接关系的朋友。 依次思路遍历所有未被访问的学生，同时朋友圈数+1。
8.23
*/
//从1个点开始搜索没有被标记的点，要用visited进行标记搜索过的点
boolean[] visited = new boolean[M.length];
int result = 0;
//行
for(int i=0;i<M.length;i++){
//搜索未被标记的点
if(visited[i] == false){
dfs(i,M,visited);
result++;
}
}
return result;
}
public void dfs(int row,int[][] M,boolean[] visited){
for(int i=0;i<M[0].length;i++){
//搜索未被标记的点
if(visited[i] == false && M[row][i] == 1){
visited[i] = true;
dfs(i,M,visited);
}
}
}
}
- 课程表1：你这个学期必须选修 numCourse 门课程，记为 0 到 numCourse-1 。在选修某些课程之前需要一些先修课程。
输入: 2, [[1,0]]
输出: true
解释: 总共有 2 门课程。学习课程 1 之前，你需要完成课程 0。所以这是可能的。
输入: 2, [[1,0],[0,1]]
输出: false
解释: 总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0；并且学习课程 0 之前，你还应先完成课程 1。这是不可能的。
有向无环图：即课程间规定了前置条件，但不能构成任何环路，否则课程前置条件将不成立。
//BFS拓扑排序(重点)
1. 创建入度表，遍历矩阵，存入indegress[i[0]]++
2. 创建队列，遍历入度表，如果入度表为0，queue.add(i)
3. 当队列不为空时，弹出队首，学过的课程可以删除了：courses--。遍历矩阵，如果pre != p[i]，continue。否则indegress[p[0]]--，如果indegress[p[0]] == 0，queue.add(i)
4. return courses == 0。查看能否学完
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
/*
BFS入度表
1. 创建入度表，遍历矩阵，存入indegress[i[0]]++
2. 创建队列，遍历入度表，如果入度表为0，queue.add(i)
3. 当队列不为空时，弹出队首，courses--。遍历矩阵，如果pre != p[i]，continue。否则indegress[p[0]]--，如果indegress[p[0]] == 0，queue.add(i)
*/
Queue<Integer> queue = new LinkedList<>();
int[] indegress = new int[numCourses];
//遍历矩阵，初始化indegress[i[0]]
for(int[] i : prerequisites){
indegress[i[0]]++;
}
//遍历courses，初始化queue，当indegress[i] == 0时，添加该i
for(int i=0;i<numCourses;i++){
if(indegress[i] == 0){
queue.add(i);
}
}
//当queue不为空，弹出队首，用于在图中搜索与入度表中删除
while(!queue.isEmpty()){
int pre = queue.poll();
numCourses--;
for(int[] p : prerequisites){
if(p[1] != pre){
continue;
}
if(--indegress[p[0]] == 0){
queue.add(p[0]);
}
}
}
return numCourses == 0;
}
}
- 课程表2：返回路径
class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
/*
BFS入度表，与207稍微不同，学过的课程存入一个数组中
1. 创建入度表，初始化indegress[p[0]]++
2. 创建队列，初始化队列，当indegress[i]==0时，queue.add(i)
3. 创建result数组，index索引
4/ 当队列不为空时，弹出队首pre，将本次课程存入result。遍历矩阵，如果--courses[i]==0，p[0]入队。如果p[1] != pre，continue
8.24
*/
//1. 创建入度表
int[] indegress = new int[numCourses];
//2. 遍历矩阵，初始化入度表
for(int[] p : prerequisites){
indegress[p[0]]++;
}
//3. 创建队列
Queue<Integer> queue = new LinkedList<>();
//4. 遍历courses，初始化队列
for(int i=0;i<numCourses;i++){
if(indegress[i] == 0){
queue.add(i);
}
}
int[] result = new int[numCourses];
int index = 0;
//5. 当队列不为空时
while(!queue.isEmpty()){
int pre = queue.poll();
result[index++] = pre;
//6. 遍历矩阵
for(int[] p : prerequisites){
if(p[1] != pre){
continue;
}
if(--indegress[p[0]] == 0){
queue.add(p[0]);
}
}
}
//如果能学完，返回result，否则返回空
if(index == numCourses){
return result;
}else{
return new int[0];
}
}
}
