Leetcode模块训练4

给你一个整数数组 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))
}

给定两个整数 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))
}

给定一个不含重复数字的数组 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))
}

给定一个可包含重复数字的序列 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))
}

给一棵二叉树的根节点 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)
}

给你一个二叉树的根节点 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))
}

给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。

示例 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))
}

给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。

示例：
给定二叉树 [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))
}

实现 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))
}

数字 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))
}

给定一个二叉树的根节点 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)

}

给定一个 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() {

}

给定一个 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() {

}

给定两个整数数组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))
}

给定两个整数数组 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() {

}

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 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() {

}

你这个学期必须选修 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() {

}

现在你总共有 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}}))
}