递归 模板
首先规定递归什么时候结束,一定要限制条件,不能无限循环
递归的执行逻辑,当前层的执行逻辑,即重复性思维,重复性处理,找相似性
递归调用,层数加1,进入下一层
最后清除,如果有涉及到外部逻辑的
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 func recursion (level int, param1, param2 interface{} ) { if level > MAX_LEVEL { process_result return } process(level, data...) recursion(level + 1 , p1, ...) }
注意点 1.递归要找到重复子问题,不要人肉递归
2.一定注意递归终止条件
3.递归属于后进先出(与栈,深度优先遍历类似)
4.明白是层级向下递减,还是递增,带不带return值
递增:边界条件达到最大值,层逻辑在递归调用前处理,看看是不是需要传给下一层
递减:边界条件达到最小值,带返回值,返回后,层逻辑在递归调用后处理,用上一层的返回值处理,看看是不是要用到上一层的结果
分治 1.分治是将递归过程中的问题分步骤解决,每一步骤单独递归,最终得到结果
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 func recursion (level int, param1, param2 interface{} ) { if level > MAX_LEVEL { process_result return } for { process(...) recursion(...) } }
回溯 思想 1.回溯采用试错的思想,分布解决,达到某种特定条件,或者是错误结果,则进行回溯,要有一个不断变化的变量,递归下一层改变,回溯上一层重置
2.递归过程中是一直向深层递归,处理完某种特定条件之后,返回当前层,回到上一层
3.对于当前层的处理进行回溯,回到上一层的状态,进行状态重置
4.在上一层做相应处理,通过分治,走下一种情况去解决,进入到另一种情况下一层,继续处理
5.重复4步骤,知道递归完毕
例如: 组合,全排列等题
1.通过递归往数组里添加数字,直到这个数组,满足结果,添加进最终结果,这个数组就是不断变化的变量
2.然后回溯,将状态回到上一层,再对上一层的分治的第二种情况,继续向下递归,然后回溯,重复步骤
3.区别在于分治时候的逻辑不一样,组合是依次遍历+1,所以不会加入重复的, 全排列是全遍历,要对于已加入的数字进行过滤
复杂度分析 由于回溯相当于遍历,所以时间复杂度会比较高,通过特定条件进行剪枝,跳过一些情况,可以降低复杂度
比如全排列2的排序操作,通过排序预处理,针对已经加入,或者重复的进行跳过,达到剪枝,减少递归
时间复杂度: O(N×N!) 空间复杂度: O(N×N!)
理解 1.为什么要进行回溯,不回溯的话也可以解决问题,则需要在每一层递归的时候,创建新的变量来处理问题,消耗比较大
2.回溯则是用一个变化的变量,进行修改状态,重置状态,不用创建变量
3.回溯问题思考: 1.如何产生分支,如何进行下次递归,递归树是怎样的 2.解在哪里,是在叶子节点,还是路径,还是非叶子节点,如何得到解 3.哪些情况不需要解,如何过滤掉这些解,如何剪枝,如何避免重复
4.要记得优化参数
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 func recursion (level int, param1, param2 interface{} ) { terminator (... ) { return } for { fix(...) process(...) recursion(...) back() } }
例题 括号生成 数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。
递归+回溯
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 func generateParenthesis(n int) []string { res := []string{} var handle func(int, int, string) handle = func (left, right int, r string ) { if len(r) == 2 *n { res = append(res, r) return } if left < n { r += "(" handle(left + 1 , right, r) r = r[:len(r) - 1 ] } if right < left { r += ")" handle(left, right + 1 , r) r = r[:len(r) - 1 ] } } handle(0 , 0 , "" ) return res }
组合 给定两个整数 n 和 k,返回 1 … n 中所有可能的 k 个数的组合。
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 func combine(n int, k int) [][]int { res := [][]int{} if n < k { return res } var handle func(start int, path []int) handle = func (start int, path []int ) { if len(path) == k { tmp := make([]int, len(path)) copy(tmp, path) res = append(res, tmp) return } for i := start; i <= n; i++ { path = append(path, i) handle(i+1 , path) path = path[:len(path) - 1 ] } } handle(1 , []int{}) return res }
全排列 给定一个 没有重复 数字的序列,返回其所有可能的全排列。
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 func permute(nums []int) [][]int { res := [][]int{} vis := make(map[int]bool, len(nums)) var handle func(curNums []int) handle = func (curNums []int ) { if len(curNums) == len (nums ) { tmp := make([]int, len(curNums)) copy(tmp, curNums) res = append(res, tmp) return } for _, v := range nums { if vis[v] { continue } vis[v] = true curNums = append(curNums, v) handle(curNums) vis[v] = false curNums = curNums[:len(curNums) - 1 ] } } handle([]int{}) return res }
全排列2 给定一个可包含重复数字的序列 nums ,按任意顺序 返回所有不重复的全排列。
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 func permuteUnique(nums []int) [][]int { res := [][]int{} vis := make(map[int]bool, len(nums)) sort.Ints(nums) var handle func(curNums []int) handle = func (curNums []int ) { if len(curNums) == len (nums ) { tmp := make([]int, len(curNums)) copy(tmp, curNums) res = append(res, tmp) return } for i, v := range nums { if vis[i] { continue } if i > 0 && v == nums[i - 1 ] && !vis[i - 1 ] { continue } vis[i] = true curNums = append(curNums, v) handle(curNums) vis[i] = false curNums = curNums[:len(curNums) - 1 ] } } handle([]int{}) return res }
N皇后 n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。
给你一个整数 n ,返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案,该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。
回溯递归:
1.与之前递归回溯类似,只不过是二维数组,多了一维,可以先初始化一个二维数组,然后在递归过程中不断赋值修改
2.类似组合start +1这种,start就是行, 递归中遍历列,递归深度行+1,达到类似两个指针的效果,就像组合,固定一个,遍历从固定的开始
3.剪枝规则,就是行,左对角线,右对角线都没有重复的
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 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 func solveNQueens(n int) [][]string { res := [][]string{} bd := make([][]string, n) for i := range bd { bd[i] = make([]string, n) for j := range bd[i] { bd[i][j] = "." } } visCol := make(map[int]bool, n) visLeftSth := make(map[int]bool, n) visRightSth := make(map[int]bool, n) var handle func([][]string, int) handle = func (bd [][]string, r int ) { if r == n { tmp := make([]string, n) for i := 0 ; i < n; i++ { tmp[i] = strings.Join(bd[i], "" ) } res = append(res, tmp) return } for c := 0 ; c < n; c++ { if visCol[c] || visLeftSth[c - r] || visRightSth[c + r] { continue } bd[r][c] = "Q" visCol[c] = true visLeftSth[c - r] = true visRightSth[c + r] = true handle(bd, r + 1 ) bd[r][c] = "." visCol[c] = false visLeftSth[c - r] = false visRightSth[c + r] = false } } handle(bd, 0 ) return res }
Pow 实现 pow(x, n) ,即计算 x 的 n 次幂函数(即,xn)。
for循环迭代会超时
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 func myPow(x float64, n int) float64 { res := 1.0 if n == 0 { return res } if n < 0 { x = 1 / x n = -n } var handle func(float64, int) float64 handle = func (x float64, n int) float64 { if n == 0 { return res } res = handle(x, n/2 ) if n % 2 == 0 { return res * res } return res * res * x } return handle(x, n) }
子集 给你一个整数数组 nums ,数组中的元素 互不相同 。返回该数组所有可能的子集(幂集)。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
回溯递归:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 func subsets(nums []int) [][]int { res := [][]int{} var handle func([]int, int) handle = func (cur []int, start int) { if len(cur) <= len (nums ) { tmp := make([]int, len(cur)) copy(tmp, cur) res = append(res, tmp) } for i := start; i < len(nums); i++ { cur = append(cur, nums[i]) handle(cur, i+1 ) cur = cur[:len(cur) - 1 ] } } handle([]int{}, 0 ) return res }
迭代:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 func subsets(nums []int) (ans [][]int) { n := len(nums) for mask := 0 ; mask < 1 <<n; mask++ { set := []int{} for i, v := range nums { if mask>>i&1 > 0 { set = append(set, v) } } ans = append(ans, append([]int(nil), set...)) } return }
子集2 给定一个可能包含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。
说明:解集不能包含重复的子集。
回溯递归:
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 func subsetsWithDup(nums []int) [][]int { res := [][]int{} sort.Ints(nums) vis := make(map[int]bool, len(nums)) var handle func([]int, int) handle = func (cur []int, start int ) { if len(cur) <= len (nums ) { tmp := make([]int, len(cur)) copy(tmp, cur) res = append(res, tmp) } for i := start; i < len(nums); i++ { if i > 0 && nums[i] == nums[i - 1 ] && !vis[i - 1 ] { continue } vis[i] = true cur = append(cur, nums[i]) handle(cur, i + 1 ) cur = cur[:len(cur) - 1 ] vis[i] = false } } handle([]int{}, 0 ) return res }