seo如何分析一个网站,建站网址什么意思,项目经理证书怎么考,做小程序商城以下内容更详细解释来自于:代码随想录 (programmercarl.com)
1.回溯算法理论基础 回溯法也叫回溯搜索法,是搜索法的一种,我们之前在二叉树中也经常使用到回溯来解决问题,其实有递归就有回溯,有的时候回溯隐藏在递归之下,我们不容易发觉,今天我们来详细介绍一下什么是回溯,它能…以下内容更详细解释来自于:代码随想录 (programmercarl.com)
1.回溯算法理论基础 回溯法也叫回溯搜索法,是搜索法的一种,我们之前在二叉树中也经常使用到回溯来解决问题,其实有递归就有回溯,有的时候回溯隐藏在递归之下,我们不容易发觉,今天我们来详细介绍一下什么是回溯,它能解决哪些问题. 回溯法效率 回溯法的效率是不高的,回溯的本质是穷举,因为有些问题能用回溯法解决出来就不错了,别无他法,只能使用这个暴力方法 回溯法一般可以解决如下几种问题 组合问题N个数里面按一定规则找出k个数的集合切割问题一个字符串按一定规则有几种切割方式子集问题一个N个数的集合里有多少符合条件的子集排列问题N个数按一定规则全排列有几种排列方式棋盘问题N皇后解数独等等 提供一个八皇后小游戏hhh:【死亡8皇后】小游戏_游戏规则玩法,高分攻略-2345小游戏 理解回溯法的方式 不要光靠脑子想,要将这种回溯具象化,想象成树形结构,任何回溯法解决的问题都可以转化为树形结构来解决问题. 因为回溯法解决的都是在集合中递归查找子集,集合的大小就构成了树的宽度,递归的深度,都构成的树的深度. 递归就要有终止条件,所以必然是一棵高度有限的树(N叉树). 回溯法代码模板(伪代码) 首先是函数参数和返回值 一般无需返回值,参数很多,一般边写边定,函数名一般定为backtracking void backtracking(参数) 终止条件 我们说可以将回溯算法想像成一个树形结构,那么我们就一定有终止条件,一般到达终止条件(叶子结点),也就是我们收获答案的时候,相关为伪代码如下 if (终止条件) {存放结果;return;
} 回溯搜索的遍历过程 上文中我们说回溯的树的宽度取决于元素个数,回溯深度取决于递归深度,如图所示 回溯算法遍历的伪代码如下 for (选择本层集合中元素树中节点孩子的数量就是集合的大小) {处理节点;backtracking(路径选择列表); // 递归回溯撤销处理结果
} 注意这里的撤销,假设我们要求1234中size为2的组合,有 12 13....这里假设我们第一个节点是12,这里我们要得到13就得将2pop出去,也就是我们回溯撤销的过程. 回溯模板(全) void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择本层集合中元素树中节点孩子的数量就是集合的大小) {处理节点;backtracking(路径选择列表); // 递归回溯撤销处理结果}
} 2.经典例题 :LeetCode T77 组合问题 题目链接:77. 组合 - 力扣LeetCode
题目思路: 我们说递归有三部曲,这里我们回溯也有三部曲,这里我们首先定义一个path变量,来存放我们每条路径上的结果,因为这里我们可以将回溯过程想象成n叉树,所以叶子结点的结果也可以想象成路径的结果,然后定义一个result数组来存放所有路径的集合,这里我们定义为全局变量,下面函数实现中直接操作即可. ListInteger path new ArrayList();
ListListInteger result new ArrayList(); 我们以1234中排列2个数字,即n 4,k 2为例,画出如下图 回溯三部曲 1.确定函数参数和返回值 这里n和k肯定是需要的,还有我们需要一个参数就是从哪里开始,于是我们定义一个变量startIndex来记录每次递归开始的逻辑,比如第一次从1开始,第二次从2开始 public void backtracking(int n, int k,int startIndex) 2.确定终止条件 这里的终止条也是收割结果的时候,我们发现树的叶子节点就是我们所要的结果,我们写出如下代码 //终止条件if(path.size() k){result.add(new ArrayList(path));return;} 3.确定一次递归(回溯)过程 这里我们按照上文所说就是我们for循环该登场了,这个时候我们的循环就得从startIndex开始到n结束,里面需要做的事情就是path.add元素,再进行backtracking,最后得pop元素进行一次回溯的过程,这里我们可以想象假设上面这个1234的例子,这里我收集了12这个例子,我想收获13这个结果是不是得将2弹出再将3进行添加呀,下面是代码演示 //for循环for(int i startIndex;in;i){path.add(i);backtracking(n,k,i1);path.remove(path.size()-1);} 题目代码:
class Solution {ListInteger path new ArrayList();ListListInteger result new ArrayList();public ListListInteger combine(int n, int k) {backtracking(n,k,1);return result;}public void backtracking(int n, int k,int startIndex){//终止条件if(path.size() k){result.add(new ArrayList(path));return;}//for循环for(int i startIndex;in;i){path.add(i);backtracking(n,k,i1);path.remove(path.size()-1);}}
} 代码优化 还是以上面1234举例,这里我们可以进行一次剪枝,假设我们n 4,k 4我们就会发现startIndex取2后面的值就毫无意义了,这里我们就可以对这种情况剪枝,如果后面的元素不足以我构成我们的一次正确的结果,就不要去遍历它了 优化过程如下: 已经选择的元素个数path.size(); 还需要的元素个数为: k - path.size(); 在集合n中至多要从该起始位置 : n - (k - path.size()) 1开始遍历 为什么有个1呢因为包括起始位置我们要是一个左闭的集合。 举个例子n 4k 3 目前已经选取的元素为0path.size为0n - (k - 0) 1 即 4 - ( 3 - 0) 1 2,这里都是合理的 只需修改一下for循环的区间即可 for (int i startIndex; i n - (k - path.size()) 1; i)
