本文主要是介绍夸父追日:第七章 回溯算法part02,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
今日收获:组合总和,组合总和Ⅱ,分割回文串
代码随想录:for循环横向遍历,递归纵向遍历,回溯不断调整结果集。
1. 组合总和
题目链接:39. 组合总和 - 力扣(LeetCode)
思路:和216. 组合总和 III - 力扣(LeetCode)很像,不同之处在于可以重复选择当前元素,所以递归时start不用+1
方法:
class Solution {List<Integer> path=new ArrayList<>();List<List<Integer>> result=new ArrayList<>();public List<List<Integer>> combinationSum(int[] candidates, int target) {// 先进行排序Arrays.sort(candidates);back(candidates,target,0);return result;}public void back(int[] candidates,int target,int start){// 终止if (target==0){result.add(new ArrayList<>(path));return;}for (int i=start;i<candidates.length;i++){if ((target-candidates[i])<0){ // 提前剪枝return;}path.add(candidates[i]);target-=candidates[i];back(candidates,target,i);path.removeLast();target+=candidates[i];}}
}
总结:
1. 集合中元素可以不断重复,递归中的参数start不加1,表示当前元素还可以在下一层中选
2. 组合中的元素可以无限多,没有k个限制,for循环终止条件是集合的长度(不再有个数限制的剪枝了)
3. 求组合总和时可以利用总和大小提前剪枝,再判断要不要选择当前元素(前提:数组已经排好序了,否则当前和大于总和,不能说明之后就没有更小的元素了)
2. 组合总和Ⅱ
题目链接:40. 组合总和 II - 力扣(LeetCode)
思路:去重的逻辑:同一层不能选一样的(就是for循环中if判断的逻辑),否则结果一样;但是同一个路径中可以选不同位置的相同元素
方法:
class Solution {List<Integer> path=new ArrayList<>();List<List<Integer>> result=new ArrayList<>();public List<List<Integer>> combinationSum2(int[] candidates, int target) {// 标记选择的数字是否在同一层使用过int[] used=new int[candidates.length];for (int i=0;i<candidates.length;i++){used[i]=0;}Arrays.sort(candidates);back(candidates,target,0,used);return result;}public void back(int[] candidates,int target,int start,int[] used){if (target==0){ // 终止result.add(new ArrayList<>(path));return;}for (int i=start;i<candidates.length;i++){if (i>0&&candidates[i]==candidates[i-1]&&used[i-1]==0){continue;}if ((target-candidates[i])<0){ // 剪枝return;}path.add(candidates[i]);target-=candidates[i];used[i]=1;back(candidates,target,i+1,used);path.removeLast();target+=candidates[i];used[i]=0;}}
}
总结:使用used数组是为了区分究竟在同一层还是同一条路径上选取相同的元素,如果前一个相同元素已经使用过,那么是同一树枝上;如果前一个相同元素还没有使用过,说明是在同一层上。
3. 分割回文串
题目链接:131. 分割回文串 - 力扣(LeetCode)
思路:第一次选择第一个字母,判断是否是回文串,如果是添加到结果集中,如果不是就切割当前字符后面的字符串;后面的字符串切割完成后,StringBuilder添加第二个字符,相当于切割线这次从第二个字符开始切割。注意每次都要传入一个新的StringBuilder对象,表明只有第一次的切割线不断移动位置,后面都是从第一个字符开始切割。
方法:
class Solution {List<List<String>> result=new ArrayList<>();List<String> path=new ArrayList<>();public List<List<String>> partition(String s) {back(s,0,new StringBuilder());return result;}public void back(String s,int cut,StringBuilder sb){// 终止if (cut==s.length()){result.add(new ArrayList<>(path));return;}for (int i=cut;i<s.length();i++){sb.append(s.charAt(i));if (isHui(sb.toString())){path.add(sb.toString());back(s,i+1,new StringBuilder());path.removeLast();}}}// 判断字符串是否回文public boolean isHui(String str){int len=str.length();for (int i=0,j=len-1;i<j;i++,j--){if (str.charAt(i)!=str.charAt(j)){return false;}}return true;}
}
总结:
1. 切割问题可以抽象为组合问题,只要一步步确定分割线
2. 判断回文子串可以先根据字符串长度剪枝,然后利用相向双指针法(相反方向)
3. 当切割线移动到右边已经没有字符时,收集结果并返回
这篇关于夸父追日:第七章 回溯算法part02的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!