算法通关村第十八关-白银挑战回溯热门问题
大家好我是苏麟 , 今天带来几道小题 .
回溯主要解决一些暴力枚举也搞不定的问题，例如组合、分割、子集、排列，棋盘等。这一关我们就看几个例子
回溯热身-再论二叉树路径问题
二叉树的所有路径
描述 :
给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点。
题目 :
LeetCode 257. 二叉树的所有路径 :
分析 :
这题之前做过解析请看往期 博客
这关用的回溯法解题 , 看懂了LeetCode 77 组合问题的解析 , 这题不在话下
解析 :
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
List<String> list = new ArrayList<>();
public List<String> binaryTreePaths(TreeNode root) {
dfs(root,new ArrayList<>());
return list;
}
public void dfs(TreeNode root,List<String> temp){
if(root == null){
return;
}
temp.add("" + root.val);
if(root.left == null && root.right == null){
list.add(getString(temp));
}
dfs(root.left,temp);
dfs(root.right,temp);
temp.remove(temp.size() - 1);
}
//结果
public String getString(List<String> list){
StringBuilder sb = new StringBuilder();
sb.append(list.get(0));
for(int i = 1;i < list.size();i++){
sb.append("->").append(list.get(i));
}
return sb.toString();
}
}
路径总和 II
描述 :
给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。
题目 :
LeetCode 113. 路径总和 II
分析 :
往期解析 : 博客
这题也一样 , 懂了回溯法这题也不难
解析 :
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
List<List<Integer>> list = new ArrayList<>();
LinkedList<Integer> onelist = new LinkedList<>();
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
dfs(root,targetSum);
return list;
}
public void dfs(TreeNode root, int targetSum){
if(root == null){
return;
}
targetSum -= root.val;
onelist.add(root.val);
if(targetSum == 0 && root.left == null && root.right == null){
list.add(new LinkedList(onelist));
}
dfs(root.left,targetSum);
dfs(root.right,targetSum);
onelist.removeLast();
}
}
回溯热门问题
组合总和问题
组合总和
描述 :
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。
题目 :
LeetCode 39. 组合总和 :
分析 :
如果不考虑重复，本题与LeetCode113题就是一个题，如果可以重复，那是否会无限制取下去呢? 也不会，因为题目给了说明，每个元素最小为1，因此最多也就target个1。
我们画图看该怎么做，对于序列{2,3,6,7}，target=7。很显然我们可以先选择一个2，然后剩下的target就是7-2=5。再选一个2，剩余5-2=3。之后再选一个2，剩余3-2=1。已经小于2了，我们不能继续向下了要返回一下。看看有没有3。OK，序列中有3，那么就得到了第一个结果(2,2,3}。
之后我们继续回退到只选了一个2的时候，这时候不能再取2了，而是从3,6,7)中选择，如下图所示，没有符合要求的!
依次类推，后面尝试从3、6和7开始选择。
所以我们最终得到的结果就是{2,2,3)和 {2,5}。为了方便，我们可以先对元素做个排序，然后将上面的过程画成这个一个树形图:
解析 :
class Solution {
List<List<Integer>> list = new ArrayList<>();
List<Integer> temp = new ArrayList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
dfs(candidates,0,target);
return list;
}
public void dfs(int[] candidates,int cur, int target){
if(target < 0){
return;
}
if(target == 0){
list.add(new LinkedList(temp));
return;
}
for(int i = cur;i < candidates.length;i++){
if(candidates[i] <= target){
temp.add(candidates[i]);
dfs(candidates,i,target - candidates[i]);
temp.remove(temp.size() - 1);
}
}
}
}
子集问题
子集
描述 :
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
题目 :
LeetCode 78.子集 :
分析 :
我们以[1,2,3] 为例
从图中红线部分，可以看出遍历这个树的时候，把所有节点都记录下来，就是要求的子集集合。这里什么时候要停下来呢? 其实可以不加终止条件，因为start >= nums.size0，本层for循环本来也结束了。
而且求取子集问题，不需要任何剪枝!因为子集就是要遍历整棵树。这样实现起来也比较容易。
解析 :
class Solution {
List<List<Integer>> list = new ArrayList<>();
List<Integer> temp = new ArrayList<>();
public List<List<Integer>> subsets(int[] nums) {
dfs(nums,0);
return list;
}
public void dfs(int[] nums , int start){
list.add(new ArrayList<>(temp));
if(start >= nums.length){
return;
}
for(int i = start;i < nums.length;i++){
temp.add(nums[i]);
dfs(nums,i + 1);
temp.remove(temp.size() - 1);
}
}
}
切割字符串问题
分割回文串
描述 :
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
题目 :
LeetCode 131.分割回文串 :
分析 :
字符串如何判断回文本身就是一个道算法题，本题在其之上还要再解决一个问题: 如何切割? 如果暴力切割，是非常困难的，如果从回溯的角度来思考就清晰很多:
我们说回溯本身仍然会进行枚举，这里的也一样。切割线(就是图中的红线)切割到字符串的结尾位置,说明找到了一个切割方法。这里就是先试一试,第一次切a第二次切aa第三次切aab。这对应的就是回溯里的for循环，也就是横向方面。
我们还说回溯仍然会进行递归，这里也是一样的，第一次切了a剩下的就是“ab"。递归就是再将其再切-个回文下来，也就是第二个a,剩下的再交给递归进一步切。这就是纵向方面要干的事情，其他以此类推。
至于回溯操作与前面是一样的道理，不再整述。通过代码就可以发现，切割问题的回溯搜索的过程和组合问题的回溯搜索的过程是差不多的。
class Solution {
List<List<String>> list = new ArrayList<>();
List<String> temp = new ArrayList<>();
public List<List<String>> partition(String s) {
dfs(s,0);
return list;
}
public void dfs(String s,int start){
if(start >= s.length()){
list.add(new ArrayList(temp));
return;
}
for(int i = start;i < s.length();i++){
if(isString(s,start,i)){
String tempString = s.substring(start,i + 1);
temp.add(tempString);
}else{
continue;
}
dfs(s,i + 1);
temp.remove(temp.size() - 1);
}
}
public boolean isString(String s,int start,int end){
for(int i = start, j = end;i < j;i++,j--){
if(s.charAt(i) != s.charAt(j)){
return false;
}
}
return true;
}
}
这期就到这里下期见!
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！