做vue用哪个网站,网站收录不好排名高,龙岩是哪个省哪个市,外汇网站建设回溯有清晰的解题模板#xff0c; void backtracking(参数){if (终止条件){存放结果;return;}for (选择本层中的集合元素#xff08;画成树#xff0c;就是树节点孩子的大小) {处理节点;backtracking();回溯#xff0c;撤销处理结果;}}
1. 从N叉树说起
在回溯之前#x…回溯有清晰的解题模板 void backtracking(参数){if (终止条件){存放结果;return;}for (选择本层中的集合元素画成树就是树节点孩子的大小) {处理节点;backtracking();回溯撤销处理结果;}}
1. 从N叉树说起
在回溯之前先看一下N叉树的遍历问题我们知道在二叉树中按照前序遍历的过程如下所示 void treeDFS(TreeNode root){if (root null){return;}System.out.println(root.val);treeDFS(root.left);treeDFS(root.right);}class TreeNode{int val;TreeNode left;TreeNode right;}
假如是N叉树该如何遍历将原来的子节点left和right换成list。 public class TreeNode {int val;ListTreeNode nodes;}//N叉树遍历的基本过程public static void treeDFS(TreeNode root){//递归必须要有终止条件if (root null){return;}//处理节点System.out.println(root.val);//通过循环分别遍历N个子树for (int i 0; i nodes.length; i) {treeDFS(第i个子节点);}}
2. 为什么有的问题暴力搜索也不行
LeetCode77给定两个整数n和k返回1..n中所有可能的k个数的组合。例如输入n4k 2则输出[ [1,2], [1,3], [1,4], [2,3], [2,4], [3,4]。 可以用双重循环暴力搜索 int n 4;for (int i 0; i n; i) {for (int j i 1; j n; j) {System.out.println( i j);}}
如果n和k都变大例如k50那么50层循环嵌套时间复杂度就会非常高。
3. 回溯 递归 局部枚举 放下前任
继续研究LeetCode77题目按照树的思想
n4时我们可以选择的n有{1234}这四种情况所以 我们从第一层到第二层的分支有四个分别表示可以取 1,2,3,4.从左向右取数取过的不会重复取第一次取1集合变为234因为k为2我们只需要再取一个就可以了分别取234. 再看k3n5,的树图中红框标记处代表一个结果最后会有空的情况。 从图中发现元素个数时树的宽度每个结果的元素个数相当于树的深度纵向所以我们说回溯算法时一纵一横。
每次选择都是从类似{1234}{12345}这样一个序列一个个选这就是局部枚举而且越往后枚举范围越小。枚举时我们就是简单的暴力测试而已一个个验证能否满足要求从上图可以看到这就是N叉树遍历的过程因此两者代码很相似。我们再看上图中红色大框起来的部分这个部分执行过程与n4k 2的处理完全一样很明显是个可以递归的子序列。放下前任这步还是根据代码解释。
回溯代码 public ListListInteger combine(int n, int k){ArrayListListInteger res new ArrayList();if (k 0 || n k){return res;}//用户返回结果ArrayDequeInteger path new ArrayDeque();dfs(n, k, 1, path, res);return res;}private void dfs(int n, int k, int startIndex, DequeInteger path, ListListInteger res) {//递归终止条件是path的长度等于kif (path.size() k){res.add(new ArrayList(path));return;}//针对一个结点遍历可能搜索的起点其实就是枚举for (int i 0; i n; i) {//向路径变量添加一个数就是上图中的一个树枝的值path.addLast(i);//搜索起点要加1是为了缩小范围下一轮递归做准备因为不允许出现重复元素dfs(n,k,i 1,path,res);path.removeLast();}}
递归中的循环解释 for (int i 0; i n; i) {dfs(n,k,i 1,path,res);}
代表图中的四个分支 4. 图解为什么有个撤销操作
主要还是对for循环的理解 图中解释我把最外层的for循环成为外for内层成为内for
