你的回溯像一坨答辩

最近发现自己的回溯算法，图论相关完全是一坨狗屎，遂记录一下

46. 全排列

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

1
2
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    List<List<Integer>> res = new LinkedList<>();
    List<Integer> path = new LinkedList<>();
    
    public List<List<Integer>> permute(int[] nums) {
        boolean[] used = new boolean[nums.length];
        dfs(nums, 0, used);
        return res;
    }

    private void dfs(int[] nums, int i, boolean[] used) {
        int n = nums.length;
        if (i == n) {
            res.add(new LinkedList<>(path));
            return;
        }
        for (int j = 0; j < n; ++ j) {
            if (!used[j]) {
                used[j] = true;
                path.add(nums[j]);
                dfs(nums, i + 1, used);
                path.removeLast();
                used[j] = false;
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    List<List<Integer>> res = new LinkedList<>();
    List<Integer> path = new LinkedList<>();
    
    public List<List<Integer>> permute(int[] nums) {
        dfs(nums, 0);
        return res;
    }

    private void dfs(int[] nums, int i) {
        int n = nums.length;
        if (i == n) {
            res.add(new LinkedList<>(path));
            return;
        }
        for (int j = 0; j < n; ++ j) {
            if (!path.contains(nums[j])) {
                path.add(nums[j]);
                dfs(nums, i + 1);
                path.removeLast();
            }
        }
    }
}

78. 子集

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

1
2
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    List<List<Integer>> res = new LinkedList<>();
    List<Integer> path = new LinkedList<>();
    
    public List<List<Integer>> subsets(int[] nums) {
        dfs(nums, 0);
        return res;
    }

    private void dfs(int[] nums, int i) {
        int n = nums.length;
        if (i == n) {
            res.add(new LinkedList<>(path));
            return;
        }
        dfs(nums, i + 1);//选或者不选
        path.add(nums[i]);
        dfs(nums, i + 1);
        path.removeLast();
        
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    List<List<Integer>> res = new LinkedList<>();
    List<Integer> path = new LinkedList<>();
    
    public List<List<Integer>> subsets(int[] nums) {
        dfs(nums, 0);
        return res;
    }

    private void dfs(int[] nums, int i) {
        int n = nums.length;
        res.add(new LinkedList<>(path));
        if (i == n) {
            return;
        }
        for (int j = i; j < n; ++ j) {//枚举选哪个
            path.add(nums[j]);
            dfs(nums, j + 1);
            path.removeLast();
        }
    }
}

17. 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1：

1
2
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    List<String> res = new ArrayList<>();
    String [] index = new String[] {"0", "0", "abc", "def", "ghi",
        "jkl", "mno", "pqrs", "tuv", "wxyz"};
    StringBuilder sb = new StringBuilder();
    public List<String> letterCombinations(String digits) {
        int n = digits.length();
        if (n == 0) return res;
        dfs(digits, 0);
        return res;
    }

    private void dfs(String digits, int i) {
        int n = digits.length();
        if (i == n) {
            res.add(sb.toString());
            return;
        }
        String s = index[digits.charAt(i) - '0'];
        for (char c : s.toCharArray()) {
            sb.append(c);
            dfs(digits, i + 1);
            sb.deleteCharAt(i);
        }
    }
}

131. 分割回文串(PDD手撕)

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

示例 1：

1
2
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    List<List<String>> res = new LinkedList<>(); 
    LinkedList<String> path = new LinkedList<>(); 
    public List<List<String>> partition(String s) {
        dfs(s, 0);
        return res;
    }
    private void dfs(String s, int i) {
        int n = s.length();
        if (i == n) {
            res.add(new LinkedList<>(path));
            return;
        }

        for (int j = i; j < n; ++ j) {//枚举选哪个，答案的视角，每个位置必须填入一个字符
            String t = s.substring(i, j + 1);
            if (isH(t)) {
                path.add(t);
                dfs(s, j + 1);
                path.removeLast();
            }
        }
    }

    private boolean isH(String s) {
        int l = 0, r = s.length() - 1;
        while (l < r) {
            if (s.charAt(l) != s.charAt(r)) {
                return false;
            }
            l ++; r --;
        }
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    List<List<String>> res = new LinkedList<>(); 
    LinkedList<String> path = new LinkedList<>(); 
    public List<List<String>> partition(String s) {
        dfs(s, 0, 0);
        return res;
    }
    private void dfs(String s, int i, int start) {
        int n = s.length();
        if (i == n) {
            res.add(new LinkedList<>(path));
            return;
        }
        if (i < n - 1) {//选或者不选第i和i+1个字符中间的逗号
            dfs(s, i + 1, start);
        }
        String t = s.substring(start, i + 1);
        if (isH(t)) {
            path.add(t);
            dfs(s, i + 1, i + 1);
            path.removeLast();
        }
    }

    private boolean isH(String s) {
        int l = 0, r = s.length() - 1;
        while (l < r) {
            if (s.charAt(l) != s.charAt(r)) {
                return false;
            }
            l ++; r --;
        }
        return true;
    }
}

93. 复原 IP 地址

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

  • 例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。

给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

示例 1：

1
2
输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
    List<String> res = new ArrayList<>();
    List<String> path = new ArrayList<>();
    public List<String> restoreIpAddresses(String s) {
        dfs(0, s, 0);
        return res;
    }

    private void dfs(int i, String s, int cnt) {//cnt用来记录生成的段数，只能是刚好四段整数才合法
        int n = s.length();
        if (i > n) return;
        if (i == n && cnt == 4) {//合法IP地址，加入答案
            StringBuilder t = new StringBuilder();
            for (String p : path) {
                t.append(p);
                t.append(".");
            }
            t.deleteCharAt(t.length() - 1);
            res.add(t.toString());
        }
        for (int j = 1; j <= 3; ++ j) {//为什么j从1到3？因为每一段整数的长度最长为3，最短为1
            if (i + j <= n) {
                String sub = s.substring(i, i + j);//以i为起点取长度为j的子串，然后判断这个子串合法与否，合法才加入path
                if (validate(sub)) {
                    path.add(sub);
                    dfs(i + j, s, cnt + 1);//递归到以i+j为起点，构造子串，同时生成的段数加一
                    path.remove(path.size() - 1);
                }
            }
        }
    }

    private boolean validate(String s) {
        if (s.length() > 1 && s.startsWith("0")) return false;
        if (Integer.parseInt(s) > 255) return false;
        return true;
    }
}

113. 路径总和 II

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

叶子节点 是指没有子节点的节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    List<List<Integer>> res = new LinkedList<>();
    List<Integer> path = new LinkedList<>();
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        dfs(root, targetSum);
        return res;
    }

    private void dfs(TreeNode root, int tar) {
        if (root == null) return;
        path.add(root.val);
        tar -= root.val;
        if (root.left == null && root.right == null && tar == 0) {
            res.add(new LinkedList<>(path));
        }
        dfs(root.left, tar);
        dfs(root.right, tar);
        path.removeLast();    
    }
}

784. 字母大小写全排列

给定一个字符串 s ，通过将字符串 s 中的每个字母转变大小写，我们可以获得一个新的字符串。

返回 所有可能得到的字符串集合 。以 任意顺序 返回输出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    List<String> ans = new ArrayList<>();
    StringBuilder sb = new StringBuilder();
    public List<String> letterCasePermutation(String s) {
        dfs(s, 0);
        return ans;
    }

    private void dfs(String s, int i) {
        if (i == s.length()) {
            ans.add(sb.toString());
            return;
        }
        char c = s.charAt(i);
        sb.append(c);
        dfs(s, i + 1);//先递归一次不管是数字还是字母
        sb.deleteCharAt(sb.length() - 1);
        if (Character.isLetter(c)) {//再转换一次字母大小写
            c ^= 32;//这个妙
            sb.append(c);
            dfs(s, i + 1);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}

51. N 皇后

原题去原链接看吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
    List<List<String>> ans;
    boolean[] used;//记录第j列是否有皇后
    boolean[] g1;//记录/方向上是否有皇后，这个方向满足性质r+c全部相等
    boolean[] g2;//记录\方向上，这个方向满足性质r-c全部相等，但是有负数，所以注意
    int[] col;//最重要的数组，存储第i行的皇后在第几列
    public List<List<String>> solveNQueens(int n) {
        ans = new LinkedList<>();
        used = new boolean[n];
        g1 = new boolean[2 * n - 1];
        g2 = new boolean[2 * n - 1];
        col = new int[n];
        dfs(0, n);
        return ans;
    }
    private void dfs(int r, int n) {
        if (r == n) {//枚举完了所有行，构造答案
            List<String> path = new LinkedList<>();
            for (int i : col) {
                char[] c = new char[n];
                Arrays.fill(c, '.');
                c[i] = 'Q';
                path.add(new String(c));
            }
            ans.add(path);
            return;
        }
        for (int j = 0; j < n; ++ j) { //枚举列
            int t = r - j + n - 1;
            if (!used[j] && !g1[r + j] && !g2[t]) {
                col[r] = j;
                used[j] = g1[r + j] = g2[t] = true;
                dfs(r + 1, n);
                used[j] = g1[r + j] = g2[t] = false;
            }
        }
    }
}

77. 组合

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

示例 1：

1
2
3
4
5
6
7
8
9
10
输入：n = 4, k = 2
输出：
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

正着遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    List<List<Integer>> res = new LinkedList<>();
    LinkedList<Integer> path = new LinkedList<Integer>();
    int n;
    public List<List<Integer>> combine(int n, int k) {
        this.n = n;
        dfs(1, k);
        return res;
    }

    public void dfs(int i, int k) {
        int d = k - path.size();//还要选d个数
        if (d == 0) {
            res.add(new LinkedList<>(path));
            return;
        }
        // if (n - i + 1 < d) return;   //剪枝
        for (int j = i; j <= n; j ++) {
            path.add(j);
            dfs(j + 1, k);
            path.removeLast();
        }
    }
}

倒着

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    List<List<Integer>> res = new LinkedList<>();
    LinkedList<Integer> path = new LinkedList<Integer>();
    public List<List<Integer>> combine(int n, int k) {
        dfs(n, k);
        return res;
    }

    public void dfs(int i, int k) {
        int d = k - path.size();
        if (d == 0) {
            res.add(new LinkedList<>(path));
            return;
        }
        for (int j = i; j >= d; j --) {
            path.add(j);
            dfs(j - 1, k);
            path.removeLast();
        }
    }
}

选或者不选

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    List<List<Integer>> res = new LinkedList<>();
    LinkedList<Integer> path = new LinkedList<Integer>();
    public List<List<Integer>> combine(int n, int k) {
        dfs(n, k);
        return res;
    }

    public void dfs(int i, int k) {
        int d = k - path.size();
        if (d == 0) {
            res.add(new LinkedList<>(path));
            return;
        }
        if (i > d) { //如果 i > d 可以不选 i
            dfs(i - 1, k);
        }
        path.add(i);
        dfs(i - 1, k);
        path.removeLast();
    }
}

39. 组合总和

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    List<List<Integer>> ans = new LinkedList<>();
    List<Integer> path = new LinkedList<>();
    int target;
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        this.target = target;
        dfs(0, candidates, 0);
        return ans;
    }

    private void dfs(int i, int[] candidates, int sum) {
        int n = candidates.length;
        if (sum == target) {
            ans.add(new LinkedList<>(path));
            return;
        }
        for (int j = i; j < n; ++ j) {//枚举选哪个
            if (sum + candidates[j] <= target) {
                sum += candidates[j];
                path.add(candidates[j]);
                dfs(j, candidates, sum);
                sum -= candidates[j];
                path.removeLast();
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    List<List<Integer>> ans = new LinkedList<>();
    List<Integer> path = new LinkedList<>();
    int target;
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        this.target = target;
        dfs(0, candidates, 0);
        return ans;
    }

    private void dfs(int i, int[] candidates, int sum) {
        int n = candidates.length;
        if (i == n) return;
        if (sum == target) {
            ans.add(new LinkedList<>(path));
            return;
        }
        dfs(i + 1, candidates, sum);//选或者不选
        if (sum + candidates[i] <= target) {
            sum += candidates[i];
            path.add(candidates[i]);
            dfs(i, candidates, sum);
            sum -= candidates[i];
            path.removeLast();
        }
    }
}

40. 组合总和 II

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的每个数字在每个组合中只能使用 一次 。

注意：解集不能包含重复的组合。

示例 1:

1
2
3
4
5
6
7
8
输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    List<List<Integer>> res = new LinkedList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        //1 1 2 5 6 7 10
        dfs(candidates, target, 0);
        return res;
    }

    private void dfs(int[] candidates, int t, int i) {
        if (t == 0) {
            res.add(new LinkedList<>(path));
            return;
        }
        for (int j = i; j < candidates.length; ++ j) {
            if (j > i && candidates[j] == candidates[j - 1]) continue;
            if (t >= candidates[j]) {
                path.add(candidates[j]);
                dfs(candidates, t - candidates[j], j + 1);
                path.removeLast();
            }
        }
    }
}

216. 组合总和 III

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

  • 只使用数字1到9
  • 每个数字 最多使用一次

返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

枚举选哪个

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    List<List<Integer>> res = new LinkedList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> combinationSum3(int k, int n) {
        dfs(9, k, n);
        return res;
    }

    public void dfs(int i, int k, int t) {
        int d = k - path.size();
        if (t < 0 || t > (2 * i - d + 1) * d / 2) {
            return;
        }
        if (d == 0) {
            res.add(new LinkedList<>(path));
            return;
        }   
        for (int j = i; j >= d; j --) {
            path.add(j);
            dfs(j - 1, k, t - j);
            path.removeLast();
        }
    }
}

选或不选

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    List<List<Integer>> res = new LinkedList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> combinationSum3(int k, int n) {
        dfs(9, k, n);
        return res;
    }

    public void dfs(int i, int k, int t) {
        int d = k - path.size();
        if (t < 0 || t > (2 * i - d + 1) * d / 2) {
            return;
        }
        if (d == 0) {
            res.add(new LinkedList<>(path));
            return;
        }   
        if (i > d) {
            dfs(i - 1, k, t);
        }
            path.add(i);
            dfs(i - 1, k, t - i);
            path.removeLast();
        
    }
}

22. 括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：

1
2
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

枚举第i个位置选哪个

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    List<String> ans = new LinkedList<>();
    StringBuilder sb = new StringBuilder();
    int n;
    public List<String> generateParenthesis(int n) {
        this.n = n;
        dfs(0, 0);
        return ans;
    }   
    private void dfs(int i, int left) {
        if (i == n * 2) {
            ans.add(sb.toString());
            return;
        }
        if (left < n) {
            sb.append('(');
            dfs(i + 1, left + 1);
            sb.deleteCharAt(sb.length() - 1);
        }
        if (i - left < left) {
            sb.append(')');
            dfs(i + 1, left);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}

判断图中是否有环

给你一个课程总数n，同时给你一个二维数组[[a,b], [c,d]]表示想上课程a就必须先上课程b，想上课程c就必须先上课程d，问你能不能上完所有的课

比如[[0,1], [2,0], [1,2]]，表示想上课程1就必须先上课程0，想上课程0就必须先上课程2，想上课程2就必须先上课程0，这就出现了循环依赖，也就是图中有环，死锁，返回false

DFS，为图建立邻接表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
public class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            graph.add(new ArrayList<>());
        }

        // 构建邻接表
        for (int[] pre : prerequisites) {
            graph.get(pre[0]).add(pre[1]);
        }

        // 状态数组，0：未访问，1：访问中，2：已访问
        int[] status = new int[numCourses];

        // 对每个节点进行 DFS
        for (int i = 0; i < numCourses; i++) {
            if (hasCycle(graph, status, i)) {
                return false; // 如果有环，返回 false
            }
        }

        return true; // 如果无环，返回 true
    }

    // DFS 检测是否有环
    private boolean hasCycle(List<List<Integer>> graph, int[] status, int course) {
        if (status[course] == 1) {
            return true; // 发现环
        }
        if (status[course] == 2) {
            return false; // 已经访问过，无环
        }

        // 标记为访问中
        status[course] = 1;

        // 访问相邻节点
        for (int nextCourse : graph.get(course)) {
            if (hasCycle(graph, status, nextCourse)) {
                return true; // 发现环
            }
        }

        // 标记为已访问
        status[course] = 2;
        return false;
    }
}

拓扑排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
public class Solution {

    public static void main(String[] args) {
        int[][] prerequisites = new int[][]{{0, 1}, {1, 2}, {2, 0}};
        System.out.println(canFinish(3, prerequisites));
    }
    public static boolean canFinish(int numCourses, int[][] prerequisites) {
        // 构建邻接表
        List<List<Integer>> adjList = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            adjList.add(new ArrayList<>());
        }

        // 构建入度表
        int[] inDegree = new int[numCourses];

        // 填充邻接表和入度表
        for (int[] prereq : prerequisites) {
            int course = prereq[0];
            int prereqCourse = prereq[1];
            adjList.get(prereqCourse).add(course);  // 先修课程指向当前课程
            inDegree[course]++;  // 当前课程的入度 +1
        }

        // 初始化队列，加入所有入度为 0 的课程
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);  // 入度为 0 的课程可以直接修
            }
        }

        // 记录已处理课程的数量
        int processedCourses = 0;

        // 处理队列中的课程
        while (!queue.isEmpty()) {
            int currCourse = queue.poll();  // 当前可以修的课程
            processedCourses++;  // 已处理的课程数 +1

            // 遍历当前课程的后继节点（依赖于当前课程的课程）
            for (int nextCourse : adjList.get(currCourse)) {
                inDegree[nextCourse]--;  // 将后继课程的入度 -1
                if (inDegree[nextCourse] == 0) {
                    queue.offer(nextCourse);  // 如果入度变为 0，加入队列
                }
            }
        }

        // 如果处理的课程数量等于总课程数，说明无循环，返回 true
        return processedCourses == numCourses;
    }
}
算法
#回溯
你的回溯像一坨答辩
https://payfish.github.io/2024/10/10/你的回溯像一坨答辩/
作者
fu1sh
发布于
2024年10月10日
许可协议