国外网站设计理念,wordpress多功能图片主题,wordpress主题调度,wordpress的主机要求大家好我是苏麟 , 今天聊聊回溯是怎么个事 . 回溯是最重要的算法思想之一#xff0c;主要解决一些暴力枚举也搞不定的问题#xff0c;例如组合、分割、子集、排列#xff0c;棋盘等。从性能角度来看回溯算法的效率并不高#xff0c;但对于这些暴力都搞不定的算法能出结果就…大家好我是苏麟 , 今天聊聊回溯是怎么个事 . 回溯是最重要的算法思想之一主要解决一些暴力枚举也搞不定的问题例如组合、分割、子集、排列棋盘等。从性能角度来看回溯算法的效率并不高但对于这些暴力都搞不定的算法能出结果就很好了效率低点没关系 我们利用LeetCode 77 组合题来了解回溯 . 77.组合 大纲 从N叉树开始为什么有的问题暴力搜索也不行回溯 枚举 递归 撤销 回溯可以视为递归的拓展很多思想和解法都与递归密切相关在很多材料中都将回溯都与递归同时解释。因此学习回溯时我们对比递归来分析其特征会理解更深刻。
递归策略: 先与意中人制造偶遇然后了解人家的情况然后约人家吃饭有好感之后尝试拉人家的手没有拒绝就表白。回溯策略: 先统计周围所有的单身女孩然后一个一个表白被拒绝就说“我喝醉了”然后就当啥也没发生继续找下一个
回溯最大的好处是有非常明确的模板所有的回溯都是一个大框架因此透彻理解回溯的框架是解决一切回溯问题的基础
回溯不是万能的而且能解决的问题也是非常明确的例如组合、分割、子集、排列棋盘等等不过这些问题具体处理时又有很多不同
回溯模板 :
void huisu(参数){if(){return;}for(){处理......huisu();......}
}从N叉树开始
在解释回溯之前我们先看一下N叉树遍历的问题我们知道在二又树中按照前序遍历的过程如下所示 : public class TreeNode {int val;TreeNode left;TreeNode right;}public void nodeVal(TreeNode node){if(node null){return;}System.out.println(node.val);nodeVal(node.left,list);nodeVal(node.right,list);}
}假如我现在是一个三叉、四叉甚至N叉树该怎么办呢? 很显然这时候就不能用 left 和 right 来表示分支了使用一个List比较好也就是这样子 :
N 叉树的定义 :
class TreeNode{int val;ListTreeNode nodes;
}遍历的代码 :
public void nodeVal(TreeNode node){if(node null){return;}System.out.println(node.val);for(int i 1;i nodes.length;i){nodeVal(第i个节点);}}
}到这里你有没有发现和上面说的回溯的模板非常像了? 是的!非常像!既然很像那说明两者一定存在某种关系。其他暂时不管现在你只要先明白回溯的大框架就是遍历N又树就行了。
为什么有的问题暴力搜索也不行
我们说回湖主要解决暴力枚举也解决不了的问题什么问题这么神奇暴力都搞不定? LeetCode77: 给定两个整数 n 和 k返回1…n 中所有可能的 k 个数的组合。 例如输入n4k2则输出 : [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]] 首先明确这个题是什么意思如果n4k2那就是从4个数中选择2个问你最后能选出多少组数据。这个是高中数学中的一个内容过程大致这样: 如果n4那就是所有的数字为{1,2,3,4)
1.先取一个1则有[1,2][1,3][1,4]三种可能2.然后取一个因为1已经取过了不再取则有[2,3][2,4]两种可能3.再取一个3因为1和2都取过了不再取则有[3,4]一种可能4.再取4因为123都已经取过了所以直接返回null5.所以最终结果就是[1,2][1,3][1,4][2,3][2,4][3,4]
这就是我们思考该问题的基本过程写成代码也很容易双层循环轻松搞定
int n 4; for (int i 1; i n; i) { for (int j i 1; j n; j) { System.out.println(i j); }
}假如n和k都变大比如n是200k是3呢? 也可以三层循环基本搞定
int n 200;
for (int i 1; i n; i) { for (int j i 1; j n; j) { for (int u j 1; u n; n) { System.out.println(i j u); } }
}如何这里的K是5呢? 甚至是50呢? 你需要套多少层循环? 甚至告你K就是一个末知的正整数k你怎么写循环呢?这时候已经无能为例了? 所以暴力搜索就不行了。
这就是组合类型问题除此之外子集、排列、切割、棋盘等方面都有类似的问题因此我们要找更好的方式。
回溯 枚举 递归 撤销
我们继续研究LeetCode77题我们图示一下上面自己枚举所有答案的过程。
n4时我们可以选择的n有 1,2,3,4这四种情况所以我们从第一层到第二层的分支有四个分别表示可以取1234。而且这里 从左向右取数取过的数不在重复取。第一次取1集合变为234因为k为2我们只需要再取一个数就可以了分别取234得到集合[1,2] [1,3][1,4]以此类推横向: 每次从集合中选取元素可选择的范围会逐步收缩到了取4时就直接为空了
继续观察树结构可以发现图中每次访问到一次叶子节点(图中红框标记处)我们就找到了一个结果。虽然最后一个是空但是不影响结果。这相当于只需要把从根节点开始每次选择的内容(分支)达到叶子节点时将其收集起来就是想要的结果。
如果感觉不明显我们再画一个n5k3的例子: 从图中我们发现元素个数n相当于树的宽度(横向)而每个结果的元素个数k相当于树的深度(纵向)。所以我们说回溯算法就是一纵一横而已。再分析我们还发现几个规律:
我们每次选择都是从类似{1,2,3,4)1,2,3,4,5这样的序列中一个个选的这就是局部枚举而且越往后枚举范围越小。枚举时我们就是简单的暴力测试而已一个个验证能否满足要求从上图可以看到这就是N叉树遍历的过程因此两者代码也必然很像。我们再看上图中红色大框起来的部分这个部分的执行过程与n4k2的处理过程完全一致很明显这是个可以递归的子结构。
这样我们就将回溯与N叉树的完美结合在一起了
到此还有一个大问题没有解决回溯一般会有个手动撤销的操作为什么要这样呢? 继续观察纵横图:
我们可以看到我们收集每个结果不是针对叶子结点的而是针对树枝的比如最上层我们首先选了1下层如果选2结果就是(1,2)如果下层选了3结果就是(1,3)依次类推。现在的问题是当我们得到第一个结果{1,2)之后怎么得到第二个结果(1,3}呢?
继续观察纵横图可以看到我可以在得到(1,2)之后将2撤掉再继续取3这样就得到了(1,3}同理可以得到{1,4}之后当前层就没有了我们可以将1撤销继续从最上层取2继续进行。
这里对应的代码操作就是先将第一个结果放在临时列表 deque 里得到第一个结果(1,2)之后就将path里的内容放进结果列表 list 中之后将 deque 里的2撤销掉继续寻找下一个结果{1.3},然后继续将 deque 放入list然后再撤销继续找。
这几条就是回溯的基本规律明白之后一切都变得豁然开朗。
到此我们就可以写出完整的回溯代码了 :
class Solution {public ListListInteger combine(int n, int k) {ListListInteger list new ArrayList();if(n 0 || n k){return list;}DequeInteger deque new ArrayDeque();dfs(n,k,1,list,deque);return list;}//dfs 深度优先搜索的意思public void dfs (int n,int k,int start,ListListInteger list,DequeInteger deque){if(deque.size() k){list.add(new ArrayList(deque));return;}for(int i start;i n;i){deque.addLast(i);dfs(n,k,i 1,list,deque);deque.removeLast();}}
}上面代码还有个问题要解释一下: start 和 i 是怎么变化的为什么传给下一层时要加 1.我们可以看到在递归里有个循环
for (int i startIndex; i n; i) { dfs(n,k,i1,path,res);
}这里的循环有什么作用呢? 看一下图就知道了这里其实就是枚举第一次n4可以选择1234四种情况所以就有四个分支for循环就会执行四次: 而对于第二层第一个选择了1之后剩下的元素只有234了所以这时候for循环就执行3次后面的则只有2次和1次。
这期就到这里 , 下期见!
