青岛做网站方案,miniui做的网站,设计软件免费下载官方网站,桂城网站建设目录 【39. 组合总和】中等题 【40.组合总和II】中等题 【131. 分割回文串】中等题 【39. 组合总和】中等题 思路#xff1a; 确定终止条件#xff1a;sum target时记录路径并返回。剪枝#xff1a;当前节点的路径之和已经大于sum就不可能再等于sum了#xff0c;结束该分支… 目录 【39. 组合总和】中等题 【40.组合总和II】中等题 【131. 分割回文串】中等题 【39. 组合总和】中等题 思路 确定终止条件sum target时记录路径并返回。剪枝当前节点的路径之和已经大于sum就不可能再等于sum了结束该分支的递归确定单层递归逻辑遍历所有子节点遍历的关键在于遍历的同时去重只要保证子节点从当前索引开始就可以对无限制重复抽取的结果进行去重。 易错点path不能直接加入res中否则加入的是path的引用res中已经记录的值会随着path的改变而改变一定要复制一份再加入res 相似题目40.组合总和II相似点都是考虑如何去重 class Solution {ListListInteger res new ArrayList();ListInteger path new ArrayList();int sum 0;public ListListInteger 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 {ListListInteger res new ArrayList();ListInteger path new ArrayList();int sum 0; public ListListInteger 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 {ListListString res new ArrayList();ListString path new ArrayList();public ListListString 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 这三题的时间复杂度很迷感觉很难定义弄清除了再补充。
