本文主要是介绍【力扣一刷】代码随想录day27(39. 组合总和、40.组合总和II、131.分割回文串),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
目录
【39. 组合总和】中等题
【40.组合总和II】中等题
【131. 分割回文串】中等题
【39. 组合总和】中等题
思路:
- 确定终止条件:sum = target时记录路径并返回。
- 剪枝:当前节点的路径之和已经大于sum就不可能再等于sum了,结束该分支的递归
- 确定单层递归逻辑:遍历所有子节点,遍历的关键在于遍历的同时去重,只要保证子节点从当前索引开始,就可以对无限制重复抽取的结果进行去重。
易错点:path不能直接加入res中,否则加入的是path的引用,res中已经记录的值会随着path的改变而改变,一定要复制一份再加入res
相似题目:40.组合总和II,相似点都是考虑如何去重
class Solution {List<List<Integer>> res = new ArrayList<>();List<Integer> path = new ArrayList<>();int sum = 0;public List<List<Integer>> combinationSum(int[] candidates, int target) {backtracking(candidates, 0, target);return res;}public void backtracking(int[] candidates, int start, int target){// 确定终止条件if (sum == target) {res.add(new ArrayList(path));return;}// 剪枝:当前节点的路径之和已经大于sum就不可能再等于sum了,结束该分支的递归if (sum > target) return;// 确定单层递归逻辑,遍历所有子节点(关键是要在遍历的时候去重,因为可无限制重复抽取)for (int i = start; i < candidates.length; i++){path.add(candidates[i]);sum += candidates[i];backtracking(candidates, i, target);path.remove(path.size() - 1);sum -= candidates[i];}}}
- 时间复杂度:?
- 空间复杂度: O(target),path记录求和的路径,如果全是最小值2的话,那么最坏情况下path长为target/2
【40.组合总和II】中等题
难点:数组candidates中同值的元素可能有多个,而且数组candidates中每个元素只能最多用一次,可能会出现重复的结果
关键:遍历的同时实现去重,先排序,然后根据当前子节点与前一个子节点的值是否相同,不相同再遍历,以实现进行去重。
class Solution {List<List<Integer>> res = new ArrayList<>();List<Integer> path = new ArrayList<>();int sum = 0; public List<List<Integer>> combinationSum2(int[] candidates, int target) {// 排序Arrays.sort(candidates);// 递归 & 回溯backtracking(candidates, 0, target);return res;}public void backtracking(int[] candidates, int start, int target){if (sum == target){res.add(new ArrayList(path));return;}// 剪枝1if (sum > target) return;// 遍历子节点for (int i = start; i < candidates.length; i++){// 剪枝2 & 去重(如果上个子节点和当前字节点的值相同,那么就不需要再遍历了,否则结果会重复)if (i > start && candidates[i - 1] == candidates[i]) continue;System.out.println(candidates[i]);path.add(candidates[i]);sum += candidates[i];backtracking(candidates, i + 1, target);path.remove(path.size() - 1);sum -= candidates[i];}}}
- 时间复杂度: ?
- 空间复杂度: O(n),path最长为n
【131. 分割回文串】中等题
关键:将递归&回溯想象成一棵树,关键是思考【树的子节点含义是什么?】、【当前节点包含哪些子节点?】、【如何判断路径是否符合要求?】
思路:以 s = "abaca" 为例
- 第一层中,start = 0,即所有子节点都包含s中的第一个字符a,如果子节点对应的子串不是回文串(例如第二个子节点"ab"),那么就不符合题目要求,该分支不需要进行递归,直接遍历下一个节点即可。
- 第二层中,start = 1, 与上面的start的关系是,第二层的start是第一层子串的结束索引/子串最后一个字符对应的索引 + 1。
- 递归结束条件,如果当前开始的索引已经超过合法索引的最大值,则记录结果并返回。
class Solution {List<List<String>> res = new ArrayList<>();List<String> path = new ArrayList<>();public List<List<String>> partition(String s) {backtracking(s, 0);return res;}public void backtracking(String s, int start){if (start == s.length()){res.add(new ArrayList(path));return;}// 左闭右开for (int i = start + 1; i <= s.length(); i++){String subS = s.substring(start, i); // substring不包含结束索引,所以必须左闭右开// 如果当前子节点不是回文串,则继续遍历下个子节点,不记录该路径的结果if (!isPalindrome(subS)) continue;// 如果当前子节点是回文串,加入路径->继续往下递归->回溯,恢复路径path.add(subS);backtracking(s, i);path.remove(path.size() - 1);}}// 判断长度至少为1的字符串是否为回文串public boolean isPalindrome(String s){boolean judge = true;int left = 0;int right = s.length() - 1;while (left < right){if (s.charAt(left) != s.charAt(right)){judge = false;break;}left++;right--;}return judge;}
}
- 时间复杂度: ?
- 空间复杂度: O(n),path最长为字符串的长度n
这三题的时间复杂度很迷,感觉很难定义,弄清除了再补充。
这篇关于【力扣一刷】代码随想录day27(39. 组合总和、40.组合总和II、131.分割回文串)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!