网站建设与维护 东博,企业内部网站建设方案,色系网站的,html品牌网页设计论文大家好#xff0c;我是怒码少年小码。
回溯是最重要的算法思想之一#xff0c;主要解决一些暴力枚举也搞不定的问题#xff08;组合、子集、分割、排列、棋盘等等#xff09;。性能并不高#xff0c;但是哪些暴力枚举都无法ko的问题能解出来就可以了#x1f923;。
这一…大家好我是怒码少年小码。
回溯是最重要的算法思想之一主要解决一些暴力枚举也搞不定的问题组合、子集、分割、排列、棋盘等等。性能并不高但是哪些暴力枚举都无法ko的问题能解出来就可以了。
这一篇让我们来看看回溯是个什么玩意儿。
回溯思想
定义
是一个种基于深度优先搜索的思想在搜索过程中通过剪枝操作来减少搜索空间从而找到问题的解。 回溯可以理解为递归的拓展而代码结构又特别像深度遍历N叉树因此只要知道递归理解回溯并不难。 模板
回溯比其他思想好理解的一点就是它是有模板的下面是伪代码
void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择本层集合中元素画成树就是树节点孩子的大小){处理节点;backtracking();回溯撤销处理结果;}
}本文我们只干一件事——分析回溯的模板。
从树的遍历开始
透析一种基于深度优先搜素的思想首先我们需要回顾一下树的遍历。二叉树中前序遍历的代码如下
class TreeNode{int val;TreeNode left;TreeNode right;
}
void treeDFS(TreeNode root) {if (root null)return;System.out.println(root.val);treeDFS(root.left);treeDFS(root.right);
}如果是n叉树就会变成
class TreeNode{int val;ListTreeNode nodes;
}
public static void treeDFS(TreeNode root) {//递归必须要有终止条件if (root null){return;}//处理节点System.out.println(root.val);//通过循环分别遍历N个子树for (int i 1; i nodes.length; i) {treeDFS(第i个子节点);}
}因为是n叉树所以没办法再用left和right表示分支了这里用了一个List。观察上面的代码是不是和回溯的模板特别像
暴力枚举解决不了的原因
看一下这道题LeetCode 77给定两个整数 n 和 k返回范围 [1, n] 中所有可能的 k 个数的组合。你可以按 任何顺序 返回答案。 示例 输入n 4, k 2输出 [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ] 从4个数中选择2个:
先取1则有[1,2][1,3][1,4]。然后取2因为1已经取过了不再取则有[2,3][2,4]。再取一个3因为1和2都取过了不再取则有[3,4]。再取4因为123都已经取过了直接返回null。所以最终是[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变得很大呢取2个用2个循环取k个要套多少层循环显然暴力枚举就不行了这就是组合问题。
回溯递归局部枚举放下前任
继续以LeetCode 77为例子图示枚举n4k2的情况
从第一层到第二层的分支有四个分别表示可以取1234。从左向右取数取过的数不在重复取。第一次取1集合变为234 因为k为2我们只需要再取一个数就可以了分别取234得到集合[1,2] [1,3] [1,4]。
以此类推 n5k3的情况 分析规律
图中每次访问到一次叶子节点(红框标记处)就找到一个结果。虽然最后一个是空但是不影响结果。这相当于只需要把从根节点开始每次选择的内容分支达到叶子节点时将其收集起来就是想要的结果。
元素个数n相当于树的宽度横向k相当于树的深度纵向。所以我们说回溯算法就是一纵一横而已。再分析我们还发现几个规律
我们每次选择都是从类似{1,2,3,4}{1,2,3,4,5}这样的序列中一个个选的这就是局部枚举而且越往后枚举范围越小。枚举时我们就是简单的暴力测试而已一个个验证能否满足要求从上图可以看到这就是N叉树遍历的过程因此两者代码也必然很像。我们再看上图中红色大框起来的部分这个部分的执行过程与n4k2的处理过程完全一致很明显这是个可以递归的子结构。
为什么要手动撤销放下前任 收集每个结果不是针对叶子结点的而是针对树枝的比如最上层我们首先选了1下层如果选2结果就是{1,2}如果下层选了3结果就是{1,3}依次类推。 观察图片我可以在得到{1,2}之后将2撤掉再继续取3这样就得到了{1,3}同理可以得到{1,4}之后当前层就没有了我们可以将1撤销继续从最上层取2继续进行。 手动撤销对应的代码操作
先将第一个结果放在临时列表path里得到第一个结果{1,2}之后就将path里的内容放进结果列表resultList中之后将path里的2撤销掉 继续寻找下一个结果{1.3},然后继续将path放入resultLit然后再撤销继续找。
完整代码
public ListListInteger combine(int n, int k) {ListListInteger resultList new ArrayList();if (k 0 || n k) {return resultList;}//用户返回结果DequeInteger path new ArrayDeque();dfs(n, k, 1, path, res);return res;
}public void dfs(int n, int k, int startIndex, DequeInteger path, ListListInteger resultList) {//递归终止条件是path 的长度等于 kif (path.size() k) {resultList.add(new ArrayList(path));return;}//针对一个结点遍历可能的搜索起点其实就是枚举for (int i startIndex; i n; i) {//向路径变量里添加一个数就是上图中的一个树枝的值path.addLast(i);//搜索起点要加1是为了缩小范围下一轮递归做准备因为不允许出现重复的元素dfs(n, k, i 1, path, resultList);//递归之后需要做相同操作的逆向操作,具体后面继续解释path.removeLast();}
}热身小题
输出二叉树的所有路径
LeetCode 257给你一个二叉树的根节点 root 按任意顺序返回所有从根节点到叶子节点的路径。 分析可以得出有几个叶子结点就有几条路径。深度优先搜索就是从根节点开始一直找到叶子结点我们这里可以先判断当前节点是不是叶子结点再决定是不是向下走如果是叶子结点我们就增加一条路径。
从回溯的角度来看得到第一条路径125之后怎么找到第二条路径13这里很明显就是先将5撤掉发现还是不行再撤掉2然后接着递归就可以了。
class Solution {ListString ans new ArrayList();public ListString binaryTreePaths(TreeNode root) {dfs(root,new ArrayList());return ans;}private void dfs(TreeNode root,ListInteger temp){if(root null){return ;}temp.add(root.val);//如果是叶子结点记录结果if(root.left null root.right null){ans.add(getPathString(temp));}dfs(root.left,temp);dfs(root.right,temp);temp.remove(temp.size()-1);}//拼接结果private String getPathString(ListInteger temp){StringBuilder sb new StringBuilder();sb.append(temp.get(0));for(int i 1;i temp.size();i){sb.append(-).append(temp.get(i));}return sb.toString();}
}这是力扣上的简单题怎么说呢不知道大家做这道题怎么样反正我是真的一点也没破防。 路径总和的问题
LeetCode 113给你二叉树的根节点 root 和一个整数目标和 targetSum 找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。 分析我们发现根节点是5因此只要从左侧或者右侧找到targetSum是17的即可。
看左子树根值为4那只要从node(4)的左右子树中找targetSum是13node(11)时我们需要再找和为2的子链路显然此时node(7)已经超了要将node(7)给移除掉继续访问node(2)。左子树遍历完毕看根结点的右子树要找targetSum为17的链路方式与上面的一致。完整代码就是
ListListInteger res new ArrayList();
public ListListInteger pathSum(TreeNode root, int targetSum) {LinkedListInteger path new LinkedList();dfs(root,targetSum,path);return res;
}
public void dfs(TreeNode root,int targetSum,LinkedListInteger path){if(root null){return ;}targetSum - root.val;path.add(root.val);if(targetSum 0 root.left null root.right null){res.add(new LinkedList(path));}dfs(root.left,targetSum,path);dfs(root.right,targetSum,path);path.removeLast();
}总的来说
首先我们传入一个二叉树的根节点和一个目标和。我们创建一个二维列表 res 用于保存结果。接着我们创建一个 LinkedList 类型的 path 用于保存当前路径。使用深度优先搜索DFS的方式遍历二叉树具体实现在 dfs 函数中。在 dfs 函数中首先我们判断当前节点是否为空。如果为空则直接返回。然后我们将目标和减去当前节点值并将当前节点的值添加到路径中。进一步我们判断是否满足目标和为 0 且当前节点为叶子节点即没有左右子树。如果满足条件我们将当前路径添加到结果列表 res 中。接下来我们分别递归地遍历当前节点的左子树和右子树注意此时目标和和路径都已经更新。最后我们移除路径中的最后一个值以便继续向上寻找其他路径。最终返回保存有所有符合条件路径的结果列表 res。
END
啊~~知识的力量脑子好疼。下一篇我将专门介绍回溯思想的经典算法题目和应用场景这篇就当是个入门知道什么是回溯就行了。
