1. 子集#
给你一个整数数组 nums ,数组中的元素 互不相同 。返回该数组所有可能的子集(幂集)。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1:
输入:nums = [1,2,3]
输出:[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2:
输入:nums = [0]
输出:[[],[0]]
提示:
1 <= nums.length <= 10
-10 <= nums[i] <= 10
nums 中的所有元素 互不相同
/*
递归,回溯法
时间复杂度:O(n*(2^n))
空间复杂度:O(n)
*/
func subsets(nums []int) [][]int {
res := make([][]int, 0)
var recursion func(index int, num []int)
recursion = func(index int, num []int) {
if index == len(nums) {
temp := make([]int, len(num))
copy(temp, num)
res = append(res, temp)
return
}
num = append(num, nums[index])
recursion(index+1, num) //选择该值往下走
num = num[:len(num)-1]
recursion(index+1, num) //不选择该值往下走,回溯
}
recursion(0, []int{})
return res
}
func main() {
nums := []int{1, 2, 3}
fmt.Println(subsets(nums))
}
2. 组合#
给定两个整数 n 和 k,返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
示例 1:
输入:n = 4, k = 2
输出:
[[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4]]
示例 2:
输入:n = 1, k = 1
输出:[[1]]
提示:
1 <= n <= 20
1 <= k <= n
/*
递归,回溯
时间复杂度:O(C(n, k)*k),其中C(n, k)表示每次循环中包含的排列组合结果
空间复杂度:O(n+k)
*/
func combine(n int, k int) [][]int {
res, temp := make([][]int, 0), make([]int, 0)
var recursion func(cur int)
recursion = func(cur int) {
//剪枝:去除多余循环,只有 >= k的个数时才存在答案
if len(temp)+n-cur+1 < k {
return
}
if len(temp) == k { //匹配到了直接放入结果
nums := make([]int, k)
copy(nums, temp)
res = append(res, nums)
return
}
temp = append(temp, cur) //考虑该值
recursion(cur + 1)
temp = temp[:len(temp)-1] //不考虑该值,回溯
recursion(cur + 1)
}
recursion(1)
return res
}
func main() {
fmt.Println(combine(5, 3))
}
3. 全排列#
给定一个不含重复数字的数组 nums ,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
示例 1:
输入:nums = [1,2,3]
输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2:
输入:nums = [0,1]
输出:[[0,1],[1,0]]
示例 3:
输入:nums = [1]
输出:[[1]]
提示:
1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums 中的所有整数 互不相同
/*
时间复杂度:O(n×n!)
空间复杂度:O(n)
回溯算法 =(递归+纯暴力搜索)因为:有的能用回溯做出来就不错了
特点:抽象
解决问题:组合、切割、子集、排列、棋盘(N皇后)
解题方法:动手画图(切忌纯想象),一般回溯问题都可以变形为n叉树形结构
解题模板:
func {
if 终止条件 {
收集结果
return
}
for 元素集合 {
处理结点
递归
回溯
}
正常return
}
学习视频地址:https://www.bilibili.com/video/BV1cy4y167mM/
*/
func permute(nums []int) [][]int {
var ans [][]int
var backTrack func(nums []int, length int, path []int)
backTrack = func(nums []int, length int, path []int) {
if len(nums) == 0 {
//重新起一个地址存放,防止path上的值被覆盖
p := make([]int, len(path))
copy(p, path) //path -> p
ans = append(ans, p)
return
}
for i := 0; i < length; i++ {
cur := nums[i]
path = append(path, cur)
nums = append(nums[:i], nums[i+1:]...) //把位置i处的元素去除
backTrack(nums, len(nums), path)
//回溯之前的操作,也叫做撤销之前的操作
nums = append(nums[:i], append([]int{cur}, nums[i:]...)...)
path = path[:len(path)-1]
}
}
backTrack(nums, len(nums), []int{})
return ans
}
func main() {
nums := []int{1, 2, 3}
fmt.Println(permute(nums))
}
4. 全排列2#
给定一个可包含重复数字的序列 nums ,按任意顺序 返回所有不重复的全排列。
示例 1:
输入:nums = [1,1,2]
输出:
[[1,1,2],
[1,2,1],
[2,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 <= nums.length <= 8
-10 <= nums[i] <= 10
nums 中的整数可以相同
func permuteUnique(nums []int) [][]int {
var ans [][]int
var backTrack func(nums []int, length int, path []int)
backTrack = func(nums []int, length int, path []int) {
if len(nums) == 0 {
//重新起一个地址存放,防止path上的值被覆盖
p := make([]int, len(path))
copy(p, path) //path -> p
ans = append(ans, p)
return
}
visited := [21]int{}
for i := 0; i < length; i++ {
cur := nums[i]
if visited[nums[i]+10] == 1 { //如果已经存在过了,则剪枝
continue
}
path = append(path, cur)
visited[nums[i]+10] = 1 //每个元素使用后都标记一下
nums = append(nums[:i], nums[i+1:]...) //把位置i处的元素去除
backTrack(nums, len(nums), path)
//回溯之前的操作,也叫做撤销之前的操作
nums = append(nums[:i], append([]int{cur}, nums[i:]...)...)
path = path[:len(path)-1]
}
}
backTrack(nums, len(nums), []int{})
return ans
}
func main() {
nums := []int{1, 1, 2}
fmt.Println(permuteUnique(nums))
}
5. 翻转二叉树#
给一棵二叉树的根节点 root ,翻转这棵二叉树,并返回其根节点
例如:
输入:root = [4,2,7,1,3,6,9]
输出:[4,7,2,9,6,3,1]
输入:root = []
输出:[]
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
//迭代法
//时间复杂度:O(n)
//空间复杂度:O(n)
func invertTree1(root *TreeNode) *TreeNode {
if root == nil {
return nil
}
var queue []*TreeNode
queue = append(queue, root)
for len(queue) > 0 {
tempA := queue[0]
queue = queue[1:]
tempData := tempA.Left
tempA.Left = tempA.Right
tempA.Right = tempData
if tempA.Left != nil {
queue = append(queue, tempA.Left)
}
if tempA.Right != nil {
queue = append(queue, tempA.Right)
}
}
return root
}
//递归法
//时间复杂度:O(n)
//空间复杂度:O(log(n)),最坏情况下O(n)
func invertTree2(root *TreeNode) *TreeNode {
if root == nil {
return nil
}
left := invertTree2(root.Left)
right := invertTree2(root.Right)
root.Left = right
root.Right = left
return root
}
func main() {
root, l1, l2, r1, r2 := new(TreeNode), new(TreeNode), new(TreeNode), new(TreeNode), new(TreeNode)
root.Val, root.Left, root.Right = 4, l1, r1
l1.Val, l1.Left, l1.Right = 2, l2, r2
r1.Val, l2.Val, r2.Val = 7, 1, 3
invertTree2(root)
}
6. 验证二叉搜索树#
给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下:
节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例 1:
输入:root = [2,1,3]
输出:true
示例 2:
输入:root = [5,1,4,null,null,3,6]
输出:false
解释:根节点的值是 5 ,但是右子节点的值是 4 。
提示:
树中节点数目范围在[1, 104] 内
-231 <= Node.val <= 231 - 1
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
//递归法
//时间复杂度:O(n)
//空间复杂度:O(n)
func isValidBST(root *TreeNode) bool {
lower, upper := math.MinInt64, math.MaxInt64
var recursion func(node *TreeNode, lower, upper int) bool
recursion = func(node *TreeNode, lower, upper int) bool {
if node == nil {
return true
}
if node.Val <= lower || node.Val >= upper {
return false
}
return recursion(node.Left, lower, node.Val) && recursion(node.Right, node.Val, upper)
}
return recursion(root, lower, upper)
}
func main() {
root, l1, r1 := new(TreeNode), new(TreeNode), new(TreeNode)
root.Val, root.Left, root.Right = 2, l1, r1
l1.Val, r1.Val = 1, 3
fmt.Println(isValidBST(root))
}
7. 二叉树的最小深度#
给定一个二叉树,找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明:叶子节点是指没有子节点的节点。
示例 1:
输入:root = [3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7
输出:2
示例 2:
输入:root = [2,null,3,null,4,null,5,null,6]
输出:5
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
/*
深度优先
时间复杂度:O(n)
空间复杂度:O(height)
*/
func minDepth(root *TreeNode) int {
if root == nil {
return 0
}
return min(minDepth(root.Left), minDepth(root.Right)) + 1
}
/*
广度优先搜索
时间复杂度:O(n)
空间复杂度:最坏情况O(n)
*/
func minDepth1(root *TreeNode) int {
if root == nil {
return 0
}
queue, res := make([]*TreeNode, 0), 0
queue = append(queue, root)
for len(queue) > 0 {
res++
tempQueue := make([]*TreeNode, 0)
for _, v := range queue {
if v.Left == nil && v.Right == nil {
return res
}
if v.Left != nil {
tempQueue = append(tempQueue, v.Left)
}
if v.Right != nil {
tempQueue = append(tempQueue, v.Right)
}
}
queue = tempQueue
}
return res
}
func main() {
var root = new(TreeNode)
var root1 = new(TreeNode)
var root2 = new(TreeNode)
var root3 = new(TreeNode)
var root4 = new(TreeNode)
root.Val = 3
root.Left = root1
root.Right = root2
root1.Val = 9
root2.Val = 20
root2.Left = root3
root2.Right = root4
root3.Val = 15
root4.Val = 7
fmt.Println(minDepth(root))
fmt.Println(minDepth1(root))
}
8. 二叉树的最大深度#
给定一个二叉树,找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例:
给定二叉树 [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回它的最大深度 3
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
func max(a, b int) int {
if a < b {
return b
}
return a
}
//深度优先搜索
//时间复杂度:O(n)
//空间复杂度:O(height)
func maxDepth1(root *TreeNode) int {
if root == nil {
return 0
}
return max(maxDepth(root.Left), maxDepth(root.Right)) + 1
}
/*
广度优先搜索
时间复杂度:O(n)
空间复杂度:最坏情况O(n)
*/
func maxDepth(root *TreeNode) int {
if root == nil {
return 0
}
queue, res := make([]*TreeNode, 0), 0
queue = append(queue, root)
for len(queue) > 0 {
tempQueue := make([]*TreeNode, 0)
for _, v := range queue {
if v.Left != nil {
tempQueue = append(tempQueue, v.Left)
}
if v.Right != nil {
tempQueue = append(tempQueue, v.Right)
}
}
queue = tempQueue
res++
}
return res
}
func main() {
var root = new(TreeNode)
var root1 = new(TreeNode)
var root2 = new(TreeNode)
var root3 = new(TreeNode)
var root4 = new(TreeNode)
root.Val = 3
root.Left = root1
root.Right = root2
root1.Val = 9
root2.Val = 20
root2.Left = root3
root2.Right = root4
root3.Val = 15
root4.Val = 7
fmt.Println(maxDepth(root))
fmt.Println(maxDepth1(root))
}
9. Pow(x, n)#
实现 pow(x, n) ,即计算 x 的整数 n 次幂函数(即,xn )。
示例 1:
输入:x = 2.00000, n = 10
输出:1024.00000
示例 2:
输入:x = 2.10000, n = 3
输出:9.26100
示例 3:
输入:x = 2.00000, n = -2
输出:0.25000
解释:2-2 = 1/22 = 1/4 = 0.25
提示:
-100.0 < x < 100.0
-231 <= n <= 231-1
-104 <= xn <= 104
/*
快速幂(分治)+递归
时间复杂度:log(n)
空间复杂度:log(n)
*/
func myPow(x float64, n int) float64 {
var recursion func(float64, int) float64
recursion = func(x float64, n int) float64 {
if n == 0 {
return 1
}
if n%2 == 1 { //n为奇数
return x * recursion(x, n-1)
}
return recursion(x*x, n/2) //n为偶数
}
if n >= 0 { // n为正数
return recursion(x, n)
}
return 1 / recursion(x, -n) //n为负数
}
func main() {
x := 2.10000
n := 3
fmt.Println(myPow(x, n))
}
10. 括号生成#
数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。
示例 1:
输入:n = 3
输出:["((()))","(()())","(())()","()(())","()()()"]
示例 2:
输入:n = 1
输出:["()"]
/*
递归,分治
*/
func generateParenthesis(n int) []string {
var result []string
var backtrace func(left, right int, str string)
backtrace = func(leftRemain, rightRemain int, str string) {
if len(str) == 2*n { //递归出口
result = append(result, str)
return
}
if leftRemain > 0 { //剪枝条件1
backtrace(leftRemain-1, rightRemain, str+"(")
}
if leftRemain < rightRemain { //剪枝条件2
backtrace(leftRemain, rightRemain-1, str+")")
}
}
backtrace(n, n, "")
return result
}
func main() {
fmt.Println(generateParenthesis(3))
}
11. 二叉树的中序遍历#
给定一个二叉树的根节点 root ,返回它的 中序 遍历。
示例 1:
1
\
2
/
3
输入:root = [1,null,2,3]
输出:[1,3,2]
示例 2:
输入:root = []
输出:[]
示例 3:
输入:root = [1]
输出:[1]
示例 4:
1
\
2
输入:root = [1,null,2]
输出:[1,2]
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
//递归法
//时间复杂度:O(n),其中 n 为二叉树节点的个数。二叉树的遍历中每个节点会被访问一次且只会被访问一次。
//空间复杂度:O(n),空间复杂度取决于递归的栈深度,而栈深度在二叉树为一条链的情况下会达到 O(n) 的级别。
func inorderTraversal1(root *TreeNode) (res []int) {
var inorder func(node *TreeNode)
inorder = func(node *TreeNode) {
if node != nil {
inorder(node.Left)
res = append(res, node.Val)
inorder(node.Right)
}
return
}
inorder(root)
return
}
//迭代法
//时间复杂度:O(n),其中 n 为二叉树节点的个数。二叉树的遍历中每个节点会被访问一次且只会被访问一次。
//空间复杂度:O(n),空间复杂度取决于栈深度,而栈深度在二叉树为一条链的情况下会达到 O(n) 的级别。
func inorderTraversal2(root *TreeNode) (res []int) {
var stack []*TreeNode
for root != nil || len(stack) > 0 {
for root != nil {
stack = append(stack, root)
root = root.Left
}
root = stack[len(stack)-1]
stack = stack[:len(stack)-1]
res = append(res, root.Val)
root = root.Right
}
return
}
func main() {
var root = new(TreeNode)
var root1 = new(TreeNode)
var root2 = new(TreeNode)
root.Val = 1
root.Left = nil
root.Right = root1
root1.Val = 2
root1.Right = nil
root1.Left = root2
root2.Val = 3
root2.Left = nil
root2.Right = nil
a := inorderTraversal1(root)
fmt.Println(a)
b := inorderTraversal2(root)
fmt.Println(b)
}
12. N叉树的前序遍历#
给定一个 n 叉树的根节点 root ,返回 其节点值的 前序遍历 。
n 叉树 在输入中按层序遍历进行序列化表示,每组子节点由空值 null 分隔(请参见示例)。
示例 1:
输入:root = [1,null,3,2,4,null,5,6]
输出:[1,3,5,6,2,4]
type Node struct {
Val int
Children []*Node
}
/*
递归法
时间复杂度:O(m)
空间复杂度:O(m)
*/
func preorder(root *Node) []int {
var ans []int
var dfs func(node *Node)
dfs = func(node *Node) {
if node == nil {
return
}
ans = append(ans, node.Val)
for _, v := range node.Children {
dfs(v)
}
}
dfs(root)
return ans
}
func main() {
}
13. N叉树的层次遍历#
给定一个 N 叉树,返回其节点值的层序遍历。(即从左到右,逐层遍历)。
树的序列化输入是用层序遍历,每组子节点都由 null 值分隔(参见示例)。
示例 1:
输入:root = [1,null,3,2,4,null,5,6]
输出:[[1],[3,2,4],[5,6]]
type Node struct {
Val int
Children []*Node
}
/*
广度优先搜索
时间复杂度:O(n)
空间复杂度:O(n)
*/
func levelOrder(root *Node) [][]int {
if root == nil {
return nil
}
ans := make([][]int, 0)
levelQueue := make([]*Node, 0)
levelQueue = append(levelQueue, root)
for len(levelQueue) > 0 {
var tmpQueue []*Node
var tmpVal []int
for _, v := range levelQueue {
tmpVal = append(tmpVal, v.Val)
if len(v.Children) > 0 {
tmpQueue = append(tmpQueue, v.Children...)
}
}
levelQueue = tmpQueue
ans = append(ans, tmpVal)
}
return ans
}
func main() {
}
14. 前序与中序构造二叉树#
给定两个整数数组preorder 和 inorder,其中preorder 是二叉树的先序遍历,
inorder是同一棵树的中序遍历,请构造二叉树并返回其根节点。
preorder 和 inorder 均 无重复 元素.
示例 1:
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]
示例 2:
输入: preorder = [-1], inorder = [-1]
输出: [-1]
/*
只有前序遍历和后序遍历不能唯一确定一颗二叉树,
必须含有中序遍历
*/
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
/*
递归
时间复杂度:O(n)
空间复杂度:O(n)
*/
func buildTree(preorder []int, inorder []int) *TreeNode {
if len(preorder) == 0 {
return nil
}
root := &TreeNode{preorder[0], nil, nil}
i := 0
for ; i < len(inorder); i++ {
if inorder[i] == preorder[0] {
break
}
}
root.Left = buildTree(preorder[1:len(inorder[:i])+1], inorder[:i]) //先 左子树遍历
root.Right = buildTree(preorder[len(inorder[:i])+1:], inorder[i+1:]) //后 右子树遍历
return root
}
func main() {
preorder := []int{3, 9, 20, 15, 7}
inorder := []int{9, 3, 15, 20, 7}
fmt.Println(buildTree(preorder, inorder))
}
15. 中序与后续构造二叉树#
给定两个整数数组 inorder 和 postorder ,其中 inorder 是二叉树的中序遍历,
postorder 是同一棵树的后序遍历,请你构造并返回这颗 二叉树 。
示例 1:
输入:inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出:[3,9,20,null,null,15,7]
示例 2:
输入:inorder = [-1], postorder = [-1]
输出:[-1]
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
/*
递归
时间复杂度:O(n)
空间复杂度:O(n)
*/
func buildTree2(inorder []int, postorder []int) *TreeNode {
indexMap := make(map[int]int, 0)
for i, v := range inorder {
indexMap[v] = i
}
var buildTrees func(int, int) *TreeNode
buildTrees = func(inorderLeft int, inorderRight int) *TreeNode {
if inorderLeft > inorderRight {
return nil
}
//从后序遍历找到当前树的根结点,该结点可以把中序遍历划分成左右两颗子树
inorderNode := postorder[len(postorder)-1]
postorder = postorder[:len(postorder)-1]
root := &TreeNode{
Val: inorderNode,
}
inorderNodeIndex := indexMap[inorderNode]
root.Right = buildTrees(inorderNodeIndex+1, inorderRight) //先 遍历右子树
root.Left = buildTrees(inorderLeft, inorderNodeIndex-1) //后 遍历左子树
return root
}
return buildTrees(0, len(inorder)-1)
}
func main() {
}
16. 二叉树的最近公共祖先#
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点 p、q,
最近公共祖先表示为一个节点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”
示例 1:
输入:root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出:3
解释:节点 5 和节点 1 的最近公共祖先是节点 3 。
示例 2:
输入:root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出:5
解释:节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
示例 3:
输入:root = [1,2], p = 1, q = 2
输出:1
提示:
树中节点数目在范围 [2, 105] 内。
-109 <= Node.val <= 109
所有 Node.val 互不相同 。
p != q
p 和 q 均存在于给定的二叉树中。
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
/*
递归
时间复杂度:O(n)
空间复杂度:O(n)
*/
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
if root == nil {
return nil
}
if root.Val == p.Val || root.Val == q.Val { //如果成立,则往父节点往上传true,当做一种标记,
return root
}
left := lowestCommonAncestor(root.Left, p, q)
right := lowestCommonAncestor(root.Right, p, q)
if left != nil && right != nil { //当左右孩子树中都有p或q时则成立
return root
}
if left == nil {
return right
}
return left
}
func main() {
}
17. 课程表#
你这个学期必须选修 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 。这是不可能的。
提示:
1 <= numCourses <= 105
0 <= prerequisites.length <= 5000
prerequisites[i].length == 2
0 <= ai, bi < numCourses
prerequisites[i] 中的所有课程对 互不相同
/*
深度优先搜索
时间复杂度:O(m+n)
空间复杂度:O(m+n)
*/
func canFinish(numCourses int, prerequisites [][]int) bool {
edges, visited, valid := make([][]int, numCourses), make([]int, numCourses), true
var dfs func(int)
dfs = func(i int) {
visited[i] = 1
for _, v := range edges[i] {
if visited[v] == 0 {
dfs(v)
if !valid {
return
}
} else if visited[v] == 1 {
valid = false
return
}
}
visited[i] = 2
}
for _, v := range prerequisites {
edges[v[1]] = append(edges[v[1]], v[0]) //组成邻接表的存储结构
}
for i := 0; i < numCourses && valid; i++ { //当valid=false时,直接退出
if visited[i] == 0 {
dfs(i)
}
}
return valid
}
/*
广度优先搜索
时间复杂度:O(m+n)
空间复杂度:O(m+n)
*/
func canFinish2(numCourses int, prerequisites [][]int) bool {
edges, indeg, result, queue := make([][]int, numCourses),
make([]int, numCourses), make([]int, 0), make([]int, 0)
for _, v := range prerequisites {
edges[v[1]] = append(edges[v[1]], v[0]) //组成邻接表的存储结构
indeg[v[0]]++
}
for i := 0; i < numCourses; i++ {
if indeg[i] == 0 {
queue = append(queue, i)
}
}
for len(queue) > 0 {
u := queue[0]
queue = queue[1:]
result = append(result, u)
for _, v := range edges[u] {
indeg[v]--
if indeg[v] == 0 {
queue = append(queue, v)
}
}
}
return len(result) == numCourses
}
func main() {
}
18. 课程表2#
现在你总共有 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] 。
示例 2:
输入:numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
输出:[0,2,1,3]
解释:总共有 4 门课程。要学习课程 3,你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
因此,一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。
示例 3:
输入:numCourses = 1, prerequisites = []
输出:[0]
提示:
1 <= numCourses <= 2000
0 <= prerequisites.length <= numCourses * (numCourses - 1)
prerequisites[i].length == 2
0 <= ai, bi < numCourses
ai != bi
所有[ai, bi] 互不相同
/*
广度优先搜索
时间复杂度:O(m+n)
空间复杂度:O(m+n)
*/
func findOrder(numCourses int, prerequisites [][]int) []int {
edges, indeg, result, queue := make([][]int, numCourses),
make([]int, numCourses), make([]int, 0), make([]int, 0)
for _, v := range prerequisites {
edges[v[1]] = append(edges[v[1]], v[0]) //组成邻接表的存储结构
indeg[v[0]]++
}
for i := 0; i < numCourses; i++ {
if indeg[i] == 0 {
queue = append(queue, i)
}
}
for len(queue) > 0 {
u := queue[0]
queue = queue[1:]
result = append(result, u)
for _, v := range edges[u] {
indeg[v]--
if indeg[v] == 0 {
queue = append(queue, v)
}
}
}
if len(result) == numCourses {
return result
}
return []int{}
}
func main() {
fmt.Println(findOrder(3, [][]int{{1, 0}, {1, 2}, {0, 1}}))
}
...