做企业网站时需要注意哪些地方,百度推广开户流程,网站美工设计基础,网站公司缺点一、39. 组合总和
题目链接#xff1a;39. 组合总和
题目描述#xff1a;
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target #xff0c;找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 #xff0c;并以列表形式返回。你可以按 任意…一、39. 组合总和
题目链接39. 组合总和
题目描述
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target 找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同则两种组合是不同的。
对于给定的输入保证和为 target 的不同组合数少于 150 个。 示例 1
输入candidates [2,3,6,7], target 7
输出[[2,2,3],[7]]
解释
2 和 3 可以形成一组候选2 2 3 7 。注意 2 可以使用多次。
7 也是一个候选 7 7 。
仅有这两种组合。
示例 2
输入: candidates [2,3,5], target 8
输出: [[2,2,2,2],[2,3,3],[3,5]]
示例 3
输入: candidates [2], target 1
输出: []提示
1 candidates.length 302 candidates[i] 40candidates 的所有元素 互不相同1 target 40
算法分析
利用经典的回溯算法。
首先创建一个二维数组用来存放所有组合的结果集以及一个用来遍历每种合理组合的一维数组。
然后调用递归纵向遍历组合
传递参数无重复数组遍历数组的起始下标。
递归结束条件当组合中的总和等于目标值时将组合放入结果集然后返回如果组合中的总和大于目标值则直接返回结束递归。
从起始下标横向遍历无重复数组candidates[i]插入组合总和sum加上candidates[i]的值然后递归判断该组合是否满足最后再回溯将candidates[i]从组合中拿出来sum减去candidates[i]的值然后进行下一层for循环。
代码如下
class Solution {ListListIntegerresult new ArrayList();//用来存放所有组合的结果集LinkedListInteger path new LinkedList();//用来遍历每种组合的一维数组int T;//将目标整数定义在全局区域int sum;//记录组合总和int len;//记录数组candidates的长度public void backTravel(int[] candidates, int startIndex) { if(sum T) {//如果组合总和等于目标值将改组和放入结果集然后返回result.add(new LinkedListInteger(path));return;}else if(sum T) return;//由于数组中每个元素2 candidates[i] 40,所以当总和大于目标值时后面无论加多少个元素总和一定大于target,所以之间返回。for(int i startIndex; i len; i) {//从起始下标遍横向历数组path.add(candidates[i]);sum candidates[i];backTravel(candidates, i);//递归path.pollLast();//回溯sum - candidates[i];}}public ListListInteger combinationSum(int[] candidates, int target) {T target;sum 0;len candidates.length;backTravel(candidates, 0);return result;}
}
二、40. 组合总和 II
题目链接40. 组合总和 II
题目描述
给定一个候选人编号的集合 candidates 和一个目标数 target 找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
注意解集不能包含重复的组合。 示例 1:
输入: candidates [10,1,2,7,6,1,5], target 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
示例 2:
输入: candidates [2,5,2,1,2], target 5,
输出:
[
[1,2,2],
[5]
] 提示:
1 candidates.length 1001 candidates[i] 501 target 30
算法分析
这道题的做法跟上一道题类似不过要注意的时要对于重复的组合进行去重操作。
具体去重操作为
首先回溯之前对数组进行排序如此相同的元素会放在一起。
然后再横向遍历数组是对同一个元素重复出现在同一个位置去重注意同一个元素出现在不同位置时不去重。
代码如下
class Solution {ListListIntegerresult new ArrayList();//存放所有组合的结果集LinkedListInteger path new LinkedList();//搜索每种组合int T;int sum;int len;public void backTravel(int[] candidates, int startIndex) {if(sum T) {//如果总和等于目标值将组合放入结果集返回result.add(new LinkedList(path));return;}else if(sum T) return;//如果总和大于目标值直接返回for(int i startIndex; i len; i) {//从起始下标横向遍历数组if(i startIndex candidates[i] candidates[i - 1]) continue;//一个元素重复出现在同一位置时进行去重path.add(candidates[i]);sum candidates[i];backTravel(candidates, i 1);//递归path.removeLast();//回溯sum - candidates[i];}}public ListListInteger combinationSum2(int[] candidates, int target) {Arrays.sort(candidates);T target;sum 0;len candidates.length;backTravel(candidates, 0);return result;}
}
三、131. 分割回文串
题目链接131. 分割回文串
题目描述
给你一个字符串 s请你将 s 分割成一些子串使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。 示例 1
输入s aab
输出[[a,a,b],[aa,b]]示例 2
输入s a
输出[[a]]提示
1 s.length 16s 仅由小写英文字母组成
算法分析
做法跟上两道题类似也是用回溯算法不过在对每种方案添加元素字符串时要判断一下该子串是否是回文串。
所以我们还要在上面的基础上增加一个判断子串是否是回文串的方法。
具体待码如下
class Solution {ListListString result new ArrayList();//用来存放每种方案的结果集LinkedListString path new LinkedList();//用来遍历每种方案int len;//字符串的长度public boolean isPartition(String s, int left, int right) {//判断字串是否是回文串while(left right) {if(s.charAt(left) ! s.charAt(right)) return false;left;right--;}return true;}public void backTravel(String s, int startIndex) {if(startIndex len) {//如果起始下标等于字符串的长度说明有一个分割方案了将方案放入结果集然后返回result.add(new LinkedList(path));return;}else if(startIndex len) return;//如果起始下标大于字符串长度说明没有分割方案直接返回。for(int i startIndex; i len; i) {//遍历从起始下标到结尾的子串并判断从起始下标到i的字串是否是回文串if(isPartition(s, startIndex, i) ! true) continue;//如果不是回文串继续下一层for循环。path.add(s.substring(startIndex, i 1));backTravel(s, i 1);//递归path.removeLast(); //回溯}}public ListListString partition(String s) {len s.length();backTravel(s, 0);return result;}
}
总结
回溯时我们不要只会对整数数组回溯还要会对各种数组进行回溯。
