网站建设结构安排论文,职高网站建设例题,深圳市住房和建设局工程交易服务主页,织梦学校网站模板文章目录 前言组合总和问题分割回文串子集问题排序问题字母大小写全排列单词搜索总结 前言 提示#xff1a;我不愿再给你写信了。因为我终于感到#xff0c;我们的全部通信知识一个大大的幻影#xff0c;我们每个人知识再给自己写信。 --安德烈纪德 回溯主要解决一些暴力枚举… 文章目录 前言组合总和问题分割回文串子集问题排序问题字母大小写全排列单词搜索总结 前言 提示我不愿再给你写信了。因为我终于感到我们的全部通信知识一个大大的幻影我们每个人知识再给自己写信。 --安德烈·纪德 回溯主要解决一些暴力枚举也搞不定的问题例如组合、分割、子集、排列、棋盘等。这关我们就看看如何接入。 组合总和问题
参考题目地址39. 组合总和 - 力扣LeetCode 如过不考虑重复的这个题目和113的那个题目相差无疑如果可以重复哪呢是否可以无限制取下去呢也不会因为题目也给了说明。每个元素最小为1因此最多一个target个1.我们画图该怎么做呢对于序列{2367}.target 7.很明显我们选择1个2还剩下target 7 - 2 5.然后再选取一个2还剩下target target - 2 3之后再选一个2变成了target target - 2 1此时最小的为2,不能再选了就要退出。看看有没有3。ok有那么第一个结果就是{223}.
之后我们继续回退到只选1个2的时候这是2不能选了从{367}中选择如下图所示没有符合规定的。
依次类推然后尝试从3和6、7中开始选择。
最终的结果就是{223}和{25}.为了方便我们可以先对元素做个排序然后按照上面的过程执行形成一个树形图 这个图横向是针对每个元素做暴力枚举纵向是递归向下找也是纵横问题实现起来代码也不复杂:
public ListListInteger combinationSum(int[] c, int target) {ListListInteger res new ArrayList();ListInteger path new ArrayList();dfs(c,0,target,path,res);return res;
}public void dfs(int[] c,int u,int target,ListInteger path,ListListInteger res){if(target 0){return;}if(target 0){res.add(new ArrayList(path));return;}for(int i u; i c.length; i){if(c[i] target){path.add(c[i]);dfs(c,i,target - c[i],path,res);path.remove(path.size() - 1);} }
}分割回文串
参考题目地址131. 分割回文串 - 力扣LeetCode 字符串如何判断回文本身就是一道算法题本题在其之上还要解决一个问题如何分割如果暴力切割很麻烦解决起来也很困难如果从回溯的角度去思考就很清晰 我们说回溯本身仍然回进行枚举的这里也是一样的。切割线途中的|切割到字符串的结尾位置说明找到了一个切割方法。这里就是先试一试第一次切割’a’,第二次切割’aa‘,第三次切割’aab’。这对应的就是回溯里面的for循环也就是横向遍历
我们还要说回溯需要进行递归操作第一次切合’a’,剩下的就是‘ab’.递归就是在将其且下一个回文下来也就是第二个‘a’剩下的‘b’再交给递归进行一步切割。这就是纵向方面要干的事依次类推。
至于回溯操作与前面的一样的道理不再赘述。通过代码就可以发现切割问题的回溯搜索的过程和嘴和问题的回溯搜索的过程是差不多的。
class Solution {ListListString res new ArrayList();DequeString path new LinkedList();public ListListString partition(String s) {backTracking(s,0);return res;}private void backTracking(String s, int startIndex) {// 如果起始位置大于s的大小说明找到了一组分割方案if (startIndex s.length()) {res.add(new ArrayList(path));return;}for (int i startIndex; i s.length(); i) {// 如果是回文子串则记录if (isPalindrome(s, startIndex, i)) {String str s.substring(startIndex, i 1);path.addLast(str);} else {continue;} // 起始位置后移保证不重复backTracking(s, i 1);path.removeLast();}}public boolean isPalindrome(String str,int start,int end){for(int i start, j end; i j; i,j--){if(str.charAt(i) ! str.charAt(j)){return false;}}return true;}
}子集问题
子集问题也是回溯的经典使用场景。回溯可以画成一种状态树子集组合分割都可以抽象出来。
但是子集也有它特有的类型需要找出所有情况。
参考题目78. 子集 - 力扣LeetCode 画图详解 从图中也可以看出遍历这颗树的时候就可以记录下所有的节点也就是得到子集结果。
那么什么时候停下来呢起始可以不加终止条件因为startIdex nums.size(),for循环就结束了。
记住求子集问题不需要任何的剪枝操作因为子集就是要遍历整颗树。这样实现起来也比较容易。
class Solution {ListListInteger res new ArrayList();ListInteger path new ArrayList();public ListListInteger subsets(int[] nums) {// 空集也是if(nums.length 0 ){res.add(new ArrayList());return res;}backTracking(nums,0);return res;} public void backTracking(int[] nums,int startIndex){// 记住加进来再判断res.add(new ArrayList(path));if(startIndex nums.length){return;}for(int i startIndex; i nums.length; i){// 今典小连招path.add(nums[i]);backTracking(nums,i 1);path.remove(path.size() - 1);}}
}tips上面的代码可以通过全局定义res和path这样简介。这里也可以转成参数传递的形式
排序问题
参考题目介绍46. 全排列 - 力扣LeetCode 排列问题也是经典的问题每次刷是不是都难。这个问题和前面的组合等问题的一个区别就是后面的还用再选可重复例如1开始使用了但是到了2和3的时候仍然要使用一次。本质上是因为【12】和【21】从集合的角度看一个问题单是从排列的角度是两个问题。
元素1在【12】中已经使用多了但是在【21】中还要再使用一次所以就不能使用startIndex了此时可以使用一个used数组来标记已经选择的元素完整的过程如图所示 开图就知道了怎么确定终止条件呢就是到达叶子节点那么是么时候到达叶子节点呢
当时收集元素的数组path的大小达到和nums数组一样不就行了说明就找到了一个全排列也就是到达叶子节点了。
class Solution {ListListInteger res new ArrayList();ListInteger path new ArrayList();// 是否选boolean[] used ; public ListListInteger permute(int[] nums) {if(nums.length 0){return res;}used new boolean[nums.length];permuteHepler(nums);return res;}public void permuteHepler(int[] nums){if(path.size() nums.length){res.add(new ArrayList(path));return ;}for(int i 0; i nums.length; i){// 解决01 10 问题if(used[i]){continue;}used[i] true;path.add(nums[i]);permuteHepler(nums);// 经典回溯path.remove(path.size() - 1);used[i] false;}}
}字母大小写全排列
参考题目地址784. 字母大小写全排列 - 力扣LeetCode 如果本题去掉数组只告诉你两个字母ab然你每个字母变化大小写那么就是abAbaBAB四种情况。就和上面的处理一样了。这里有数字的干扰我们就需要作过滤数字只处理字母。还有就是添加大小写的转换问题了。
由于每个字符的大小形式刚好相差32因此再大小写里面可以换成用c^32来进行转换和恢复。这样代码就简洁多了
class Solution {ListString res new ArrayList();public ListString letterCasePermutation(String s) {dfs(s.toCharArray(),0);return res;}public void dfs(char[] arr, int pos){// 过滤数字while(pos arr.length Character.isDigit(arr[pos])){pos;}// 终止条件if(pos arr.length){res.add(new String(arr));return;}// 转换arr[pos]^32;dfs(arr,pos 1);// 撤销arr[pos]^32;dfs(arr,pos 1);}
}单词搜索
参考题目介绍79. 单词搜索 - 力扣LeetCode 思路从上到下左到右遍历网格每个坐标递归调用check(i,j,k)函数i,j表示网格坐标k表示word的第k个字符如果能搜索到第k个字符返回true否则返回false。
check函数的终止条件也很明确
如果ij的位置和字符上的字符位置k不相符也就是说这个方面的路径有问题直接返回false如果搜索到了字符串的结尾则找到了网格中的一条路径这条路径上的字符正好可以组成字符串s返回true。
两种情况都不满足就把当前网格加入visited数组visited表示该位置已经访问过了然后顺着当前网格的坐标的四个方向继续尝试如果没有找到k开始的子串则返回回溯状态visited[i ] [j] false,继续向后面访问。
分析一波复杂度时间复杂度为O(ML*3^L),M,N 为网格的长度和宽度L 为字符串word的长度第一次电泳check函数的时候回向4个方向进行测试其余坐标的节点都是3个方向检车走过的分支不会反方向回去左移check函数的复杂度为3^L,而网格上面有MN个坐标且存在剪枝最坏的情况下是O(MN * 3 ^L).空间复杂符是OMN) visited数组的空间是OMN) check递归栈的最大深度在最坏的情况下是O(MN)
class Solution {public boolean exist(char[][] board, String word) {char[] words word.toCharArray();for(int i 0; i board.length; i){for(int j 0; j board[i].length;j){if(dfs(board,words,i,j,0)){return true;}}}return false;}public boolean dfs(char [][] board,char[] words,int i,int j, int k){// 边界条件if(i board.length || i 0 || j board[0].length || j 0 || board[i][j] ! words[k]){return false;}// 终止条件if(k words.length - 1){return true;}// 防止重复board[i][j] \0;boolean res dfs(board,words,i1,j,k1) || dfs(board,words,i - 1,j,k1) || dfs(board,words,i,j - 1,k1) || dfs(board,words,i,j 1,k1);// 恢复board[i][j] words[k];return res;}
}总结
提示组合总和问题分割问题子集问题排列问题搜索问题 如果有帮助到你请给题解点个赞和收藏让更多的人看到 ~ (▔□▔)/
如有不理解的地方欢迎你在评论区给我留言我都会逐一回复 ~
也欢迎你 关注我 喜欢交朋友喜欢一起探讨问题。
