网站建设合同服务内容,外链工具,聊城网络公司,深圳网站建设制作设计算法笔记|Day20回溯算法II ☆☆☆☆☆leetcode 39. 组合总和题目分析代码 ☆☆☆☆☆leetcode 40.组合总和II题目分析代码 ☆☆☆☆☆leetcode 131.分割回文串题目分析代码 ☆☆☆☆☆leetcode 39. 组合总和
题目链接#xff1a;leetcode 39. 组合总和
题目分析
本题采用回… 算法笔记|Day20回溯算法II ☆☆☆☆☆leetcode 39. 组合总和题目分析代码 ☆☆☆☆☆leetcode 40.组合总和II题目分析代码 ☆☆☆☆☆leetcode 131.分割回文串题目分析代码 ☆☆☆☆☆leetcode 39. 组合总和
题目链接leetcode 39. 组合总和
题目分析
本题采用回溯算法组合没有数量要求且元素可无限重复选取故每次遍历都可以从第一个元素开始。
代码
class Solution {ListListInteger resnew ArrayList();ListInteger pathnew LinkedList();public ListListInteger combinationSum(int[] candidates, int target) {backtrcking(candidates,target,0,0);return res;}public void backtrcking(int candidates[],int target,int sum,int start){if(sumtarget)return;if(sumtarget){res.add(new ArrayList(path));return;}for(int istart;icandidates.length;i){sumcandidates[i];path.add(candidates[i]);backtrcking(candidates,target,sum,i);sum-candidates[i];path.removeLast();}}
}☆☆☆☆☆leetcode 40.组合总和II
题目链接leetcode 40.组合总和II
题目分析
本题集合数组candidates有重复元素但不能有重复的组合涉及到去重的逻辑采用了used数组若该元素在本轮回溯遍历树层中用到过赋值为1后续不再使用回溯时恢复为0但在递归遍历树枝中用到过还可以继续使用。
代码
class Solution {ListListInteger resnew ArrayList();ListInteger pathnew LinkedList();public ListListInteger combinationSum2(int[] candidates, int target) {Arrays.sort(candidates);int used[]new int[candidates.length];backtracking(candidates,target,0,0,used);return res;}public void backtracking(int candidates[],int target,int sum,int start,int used[]){if(sumtarget)return;if(sumtarget){res.add(new ArrayList(path));return;}for(int istart;icandidates.length;i){if(i0candidates[i]candidates[i-1]used[i-1]0)continue;sumcandidates[i];path.add(candidates[i]);used[i]1;backtracking(candidates,target,sum,i1,used);sum-candidates[i];path.removeLast();used[i]0;}}
}☆☆☆☆☆leetcode 131.分割回文串
题目链接leetcode 131.分割回文串
题目分析
切割问题可以仿照组合问题利用回溯从前往后搜索如果发现回文进入backtracking起始位置后移一位循环结束照例移除str的末位。
代码
class Solution {ListListString resnew ArrayList();ListString strnew ArrayList();public ListListString partition(String s) {backtracking(s,0,new StringBuilder());return res;}public void backtracking(String s,int start,StringBuilder sb){if(starts.length()){res.add(new ArrayList(str));return;}for(int istart;is.length();i){sb.append(s.charAt(i));if(check(sb)){str.add(sb.toString());backtracking(s,i1,new StringBuilder());str.removeLast();}}}public boolean check(StringBuilder sb){for(int i0;isb.length()/2;i){if(sb.charAt(i)!sb.charAt(sb.length()-1-i))return false;}return true;}
}提示回文串是向前和向后读都相同的字符串可以考虑使用双指针法一个指针从前向后一个指针从后向前如果前后指针所指向的元素是相等的就是回文字符串了也可以直接判断前一半元素和对称位置的元素是否相等。
