ps插件国外网站,推广下载app,都市人才网莱芜,织梦医院网站开发关卡名 回溯热门问题 我会了✔️ 内容 1.组合总和问题 ✔️ 2.分割回文串问题 ✔️ 3.子集问题 ✔️ 4.排列问题 ✔️ 5.字母全排列问题 ✔️ 6.单词搜索 ✔️
1. 组合总和问题
LeetCode39题目要求#xff1a;给你一个无重复元素的整数数组candidates和一个目标整数 ta… 关卡名 回溯热门问题 我会了✔️ 内容 1.组合总和问题 ✔️ 2.分割回文串问题 ✔️ 3.子集问题 ✔️ 4.排列问题 ✔️ 5.字母全排列问题 ✔️ 6.单词搜索 ✔️
1. 组合总和问题
LeetCode39题目要求给你一个无重复元素的整数数组candidates和一个目标整数 target 找出 candidates 中可以使数字和为目标数 target 的 所有不同组合 并以列表形式返回。你可以按任意顺序返回这些组合。 candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同则两种组合是不同的。 数组中的元素满足1 candidates[i] 200。例子 输入candidates [2,3,6,7], target 7 输出[[2,2,3],[7]] 解释 2 和 3 可以形成一组候选2 2 3 7 。注意2可以使用多次。 7 也是一个候选 7 7 仅有这两种组合。 如果不考虑重复本题与LeetCode113题就是一个题如果可以重复那是否会无限制取下去呢也不会因为题目给了说明每个元素最小为1因此最多也就target个1。 我们画图看该怎么做对于序列{2,3,6,7}target7。很显然我们可以先选择一个2然后剩下的target就是7-25。再选一个2剩余5-23。之后再选一个2剩余3-21。已经小于2了我们不能继续向下了要返回一下。看看有没有3。OK序列中有3那么就得到了第一个结果{2,2,3}。 之后我们继续回退到只选了一个2的时候这时候不能再取2了而是从{3,6,7}中选择如下图所示没有符合要求的 依次类推后面尝试从3、6和7开始选择。 所以我们最终得到的结果就是{2,2,3}和{2,5}。为了方便我们可以先对元素做个排序然后将上面的过程画成这个一个树形图 这个图横向是针对每个元素的暴力枚举纵向是递归也是一个纵横问题实现代码也不复杂
class CombinationSum {ListListInteger res new ArrayList(); //记录答案ListInteger path new ArrayList(); //记录当前正在访问的路径public ListListInteger combinationSum(int[] candidates, int target) {dfs(candidates,0, target);return res;}public void dfs(int[] c, int u, int target) {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]);//当前层将target减掉了一部分也就是子结构只要找是否有满足(target - c[i])就可以了dfs(c,i,target - c[i]); // 因为可以重复使用所以还是ipath.remove(path.size()-1); //回溯}}}
}
2.分割回文串
分割问题也是回溯要解决的典型问题之一常见的题目有分割回文串、分割IP地址以及分割字符串等。 LeetCode131 分割回文串给你一个字符串s请你将s分割成一些子串使每个子串都是回文串 返回s所有可能的分割方案。 回文串是正着读和反着读都一样的字符串。 示例1 输入s aab 输出[[a,a,b],[aa,b]] 字符串如何判断回文本身就是一个道算法题本题在其之上还要再解决一个问题如何切割如果暴力切割是非常困难的如果从回溯的角度来思考就清晰很多 我们说回溯本身仍然会进行枚举这里的也一样。切割线就是图中的红线切割到字符串的结尾位置说明找到了一个切割方法。这里就是先试一试,第一次切a,第二次切aa,第三次切aab。这对应的就是回溯里的for循环也就是横向方面。 我们还说回溯仍然会进行递归这里也是一样的第一次切了a,剩下的就是ab。递归就是再将其再切一个回文下来也就是第二个a,剩下的b再交给递归进一步切割。这就是纵向方面要干的事情其他以此类推。 至于回溯操作与前面是一样的道理不再赘述。通过代码就可以发现切割问题的回溯搜索的过程和组合问题的回溯搜索的过程是差不多的。
class Partition {ListListString lists new ArrayList();DequeString deque new LinkedList();public ListListString partition(String s) {backTracking(s,0);return lists;}private void backTracking(String s, int startIndex) {//如果起始位置大于s的大小说明找到了一组分割方案if(startIndexs.length){lists.add(new ArrayList(deque));return;}for(int istartIndex;is.length;i){//如果是回文子串则记录if(isPalindrome(s,startIndex,i)){String str s.substring(startIndex, i 1);deque.addLast(str);} else {continue;}//起始位置后移保证不重复backTracking(s,i1);deque.removeLast();}}//判断是否是回文串private boolean isPalindrome(String s, int startIndex, int end) {for(int istartIndex,jend;ij;i,j--){if(s.charAt(i)!s.charAt(j)){return false;}}return true;}
}
3 子集问题
子集问题也是回溯的经典使用场景。回溯可以画成一种树状结构子集、组合、分割问题都可以抽象为一棵树但是子集问题与其他的类型有个明显的区别组合问题一般找到满足要求的结果即可而集合则要找出所有的情况。 LeetCode78给你一个整数数组nums数组中的元素互不相同。返回该数组所有可能的子集幂集。解集不能包含重复的子集。你可以按任意顺序返回解集。 示例1 输入nums [1,2,3] 输出[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]] 看上面的例子nums [1,2,3]将子集抽象为树型结构如下 从图中红线部分可以看出遍历这个树的时候把所有节点都记录下来就是要求的子集集合。 这里什么时候要停下来呢其实可以不加终止条件因为startIndex nums.size()本层for循环本来也结束了。 而且求取子集问题不需要任何剪枝因为子集就是要遍历整棵树。这样实现起来也比较容易。
class Subsets {// 存放符合条件结果的集合ListListInteger result new ArrayList();// 用来存放符合条件结果LinkedListInteger path new LinkedList();public ListListInteger subsets(int[] nums) {//空集合也是一个子集if(nums.length0){result.add(new ArrayList());return result;}subsetsHelper(nums,0);return result;}private void subsetsHelper(int[] nums, int startIndex){//「遍历这个树的时候把所有节点都记录下来就是要求的子集集合」。result.add(new ArrayList(path));if(startIndexnums.length){return;}for(int istartIndex;inums.length;i){path.add(nums[i]);subsetsHelper(nums,i1);path.removeLast();}}
}
上面代码里定义了全局变量result和path这样整体比较简洁。这里可以转换成方法参数的形式只是看起来比较复杂一些。
4 排列问题
LeetCode46.给定一个没有重复数字的序列返回其所有可能的全排列。例如 输入: [1,2,3] 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ] 排列问题是典型的小学生都会但是难道众人的问题。这个问题与前面组合等问题的一个区别是使用过的后面还要再用例如1在开始使用了但是到了2 和3的时候仍然要再使用一次。这本质上是因为 [1,2] 和 [2,1] 从集合的角度看是一个但从排列的角度看是两个。 元素1在[1,2]中已经使用过了但是在[2,1]中还要再使用一次所以就不能使用startIndex了为此可以使用一个used数组来标记已经选择的元素完整过程如图所示: 这里的终止条件怎么判断呢从上图可以看出叶子节点就是结果。那什么时候是到达叶子节点呢 当收集元素的数组path的大小达到和nums数组一样大的时候说明找到了一个全排列也表示到达了叶子节点。
class Permute {ListListInteger result new ArrayList();LinkedListInteger path new LinkedList();boolean[] used;public ListListInteger permute(int[] nums) {if(nums.length0){return result;}used new boolean(nums.length);permuteHelper(nums);return result;}private void permuteHelper(int[] nums){if(path.size()nums.length){result.add(new ArrayList(path));return;}for (int i 0; i nums.length; i){if (used[i]){continue;}used[i] true;path.add(nums[i]);permuteHelper(nums);path.removeLast();used[i] false;}}
}
5 字母大小写全排列
LeetCode784. 字母大小写全排列给定一个字符串 s 通过将字符串 s 中的每个字母转变大小写我们可以获得一个新的字符串。返回所有可能得到的字符串集合。以任意顺序返回输出。 示例1输入s a1b2 输出[a1b2, a1B2, A1b2, A1B2] 如果本题去掉数字只告诉你两个字母ab让你每个字母变化大小写那就是ab、Ab、aB、AB四种情况题目比2.6电话号码问题还简单这里的数字就是干扰项我们需要做的是过滤掉数字 只处理字母。另外还要添加个大小写转换的问题。如下图所示 class LetterCasePermutation {public ListString letterCasePermutation(String s) {ListString ans new ArrayListString();dfs(s.toCharArray(), 0, ans);return ans;}public void dfs(char[] arr, int pos, ListString res) {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, res);arr[pos] ^ 32;dfs(arr, pos 1, res);}
}
6 单词搜索
LeetCode79.给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中返回 true 否则返回 false 。 单词必须按照字母顺序通过相邻的单元格内的字母构成其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。 示例1 输入board [[A,B,C,E],[S,F,C,S],[A,D,E,E]], word ABCCED 输出true 思路从上到下左到右遍历网格每个坐标递归调用dfs方法方法里的i,j表示网格坐标k表示word的第k个字符。 回溯最重要的是两个工作一个是确定递归方法的终止条件一个是确定递推公式这两个是相辅相成的。递归停止的场景我们来明确一下 如果要返回 false 则满足下面任何一种情况就可以
行或列索引越界当前矩阵元素与目标字符不同当前矩阵元素已访问过。
如果要返回true则应该k len(word) - 1 即字符串 word 已全部匹配。递推公式分析
标记当前矩阵元素 将 board[i][j] 修改为 空字符 代表此元素已访问过防止之后搜索时重复访问。搜索下一单元格 朝当前元素的 上、下、左、右 四个方向开启下层递归使用或连接 代表只需找到一条可行路径就直接返回不再做后续 DFS 并记录结果至 res 。还原当前矩阵元素 将 board[i][j] 元素还原至初始值即 word[k] 。
返回值 返回布尔量 res 代表是否搜索到目标字符串。 这样看似高大上实际并不复杂的实现就出来了
class Exist {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[0].length; j) {if (dfs(board, words, i, j, 0)) return true;}}return false;}boolean dfs(char[][] board, char[] word, int i, int j, int k) {if (i board.length || i 0 || j board[0].length || j 0 || board[i][j] ! word[k]) return false;if (k word.length - 1) return true;board[i][j] \0;boolean res dfs(board, word, i 1, j, k 1) || dfs(board, word, i - 1, j, k 1) || dfs(board, word, i, j 1, k 1) || dfs(board, word, i , j - 1, k 1);board[i][j] word[k];return res;}
}
