论文网站建设格式,thinkphp网站建设,中小型企业网站大全,免费推广手段目录
39. 组合总和
40.组合总和II
131.分割回文串 39. 组合总和 本题是 集合里元素可以用无数次#xff0c;那么和组合问题的差别 其实仅在于 startIndex上的控制 题目链接/文章讲解#xff1a;代码随想录 视频讲解#xff1a;带你学透回溯算法-组合总和#xff08;对应…目录
39. 组合总和
40.组合总和II
131.分割回文串 39. 组合总和 本题是 集合里元素可以用无数次那么和组合问题的差别 其实仅在于 startIndex上的控制 题目链接/文章讲解代码随想录 视频讲解带你学透回溯算法-组合总和对应「leetcode」力扣题目39.组合总和| 回溯法精讲_哔哩哔哩_bilibili 题解思路
这是基本的回溯算法求组合问题的代码思路没有什么问题能ac就是说记录第一次不看题解写题思想就是暴力算法的本质剪枝条件的优化套路其实差不多这里就是多了一个先对数组进行升序排序的操作好更加有利于剪枝条件作判断
class Solution {LinkedListInteger path new LinkedList();ListListInteger result new ArrayList();int sum 0;public ListListInteger combinationSum(int[] candidates, int target) {Arrays.sort(candidates); //使用Arrays工具类对给定的数组先按升序排列好让回溯方法里面的剪枝条件作快速判断backtracking(candidates,target,0);return result;}public void backtracking(int[] candidates, int target, int satart){if(sum target) return; //先对数组进行升序排序可以更加对其作判断不加也没事就是说if(sum target){result.add(new LinkedListInteger(path));return;}for(int i satart; i candidates.length; i){path.add(candidates[i]);sum candidates[i];backtracking(candidates,target,i); //这里是i因为避免取到重复的组合path.removeLast();sum - candidates[i];}}
} 40.组合总和II 本题开始涉及到一个问题了去重。 注意题目中给我们 集合是有重复元素的那么求出来的 组合有可能重复但题目要求不能有重复组合。 题目链接/文章讲解代码随想录 题解思路 本题主要在于去重条件操作的理解这很重要然后就是整体思路和求组合问题差不多具体的去重操作理解可以分成两种树层去重和树枝去重以本题结合代码注释为例说明如下第一种树层去重used[i - 1] false -- 说明此时第一轮递归已经结束了此时整个if语句的判断条件意思是当第二轮开始递归的开头元素和第一轮开始的递归的开头元素相同时直接跳过此轮递归因为之前那一轮已经包括了所有种以1开头的组合第二种树枝去重used[i - 1] true -- 说明此时还在第一轮里面此时整个if语句的判断条件意思是当在第一轮搜索所有的组合过程中如果遇到和前一个元素相同时直接跳过相邻元素相同组合的搜索这就意味着不会出现 [ 1 1 6]这种组合了显然是错误的 最后想分享的就是可以多看卡哥视频讲解的思路再自己好好去理解这两种情况 class Solution {LinkedListInteger path new LinkedList();ListListInteger result new ArrayList();int sum 0;boolean[] used;public ListListInteger combinationSum2(int[] candidates, int target) {Arrays.sort(candidates); //先对数组进行排序used new boolean[candidates.length]; //定义一个和给定数组相同大小、具有标记功能的数组Arrays.fill(used, false); //使用used数组标记之前是否使用过元素0表示未使用过1表示使用过backtracking(candidates, target, 0);return result;}public void backtracking(int[] candidates, int target, int start){if(sum target) return;if(sum target){result.add(new LinkedListInteger(path));return;}for(int i start; i candidates.length; i){if(i 0 candidates[i - 1] candidates[i] used[i - 1] false) continue; //used[i - 1] false树层去重操作used[i - 1] true树枝去重操作//这里可以这么去理解这种判断条件以第一轮和第二轮递归说明给定的排序后的数组为[1 1 2 5 6 7]target 8//used[i - 1] false -- 说明此时第一轮递归已经结束了此时整个if语句的判断条件意思是当第二轮开始递归的开头元素和第一轮开始的递归的开头元素相同时直接跳过此轮递归因为之前那一轮已经包括了所有种以1开头的组合//used[i - 1] true -- 说明此时还在第一轮里面此时整个if语句的判断条件意思是当在第一轮搜索所有的组合过程中如果遇到和前一个元素相同时直接跳过相邻元素相同组合的搜索这就意味着不会出现 [ 1 1 6]这种组合了显然是错误的used[i] true;path.add(candidates[i]);sum candidates[i];backtracking(candidates, target, i 1);used[i] false; //递归之后一定要回溯这是不能忘的把之前使用过的元素重新都标记为0开始下一次的递归搜索path.removeLast();sum - candidates[i];}}
} 131.分割回文串 本题较难大家先看视频来理解 分割问题明天还会有一道分割问题先打打基础。 题目链接/文章讲解代码随想录 题解思路 本题还是有难度的需要把切割的动作抽象成组合的问题多看卡哥视频里面讲解的思路捋清之后再下手写执行代码卡哥里面说的思路还是很清楚的多品味品味就好代码具体注意的事项看注释如何把切割动作抽象成组合问题卡哥视频说的很详细移动到卡哥视频就行 class Solution {LinkedListString path new LinkedList();ListListString result new ArrayList();public ListListString partition(String s) {backtracking(s, 0);return result;}public void backtracking(String s, int startIndex){if(startIndex s.length()){ result.add(new LinkedListString(path));return;}for(int i startIndex; i s.length(); i){if(isPalindrome(s, startIndex, i)){ //如果索引的范围内的子串是回文串则直接切割子串及时添加到path路径里面这里使用下标直接进行切割数组的操作不用装到容器里面判断String temp s.substring(startIndex, i 1); //startIndex是固定不变的而i会在每轮递归的时候都会进行i操作主要substring(start,end)是左闭右开的path.add(temp);}else{continue;}backtracking(s, i 1); //下一轮递归的时候i i1, 保证不会重复切割path.removeLast();}}public boolean isPalindrome(String s, int startIndex, int end){for(int i startIndex, j end; i j; i, j--){if(s.charAt(i) ! s.charAt(j)){return false;}}return true;}}
