39. 组合总和
题目链接
题目描述:
给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明:
所有数字(包括 target)都是正整数。
解集不能包含重复的组合。
示例 1:
- 输入:candidates = [2,3,6,7], target = 7,
- 所求解集为: [ [7], [2,2,3] ]
示例 2:
- 输入:candidates = [2,3,5], target = 8,
- 所求解集为: [ [2,2,2,2], [2,3,3], [3,5] ]
难点:
剪枝
思路:
回溯回溯~~
构造结果集,path集
回溯主体:
按部就班
class Solution {List<List<Integer>> result = new ArrayList<>();List<Integer> path = new ArrayList<>();public List<List<Integer>> combinationSum(int[] candidates, int target) {Arrays.sort(candidates);backtracking(candidates, 0, target, 0);return result;}public void backtracking(int[] candidates, int curSum, int target, int startIdx) {if (curSum > target) return;if (curSum == target) {result.add(new ArrayList<>(path));return;}for (int i = startIdx; i < candidates.length; i++) {// if (curSum + candidates[i] > target) break; //自己写没想到这里的剪枝path.add(candidates[i]);curSum += candidates[i];backtracking(candidates, curSum, target, i);path.remove(path.size()-1);curSum -= candidates[i];}}
}
时长:
10min
收获:
不用IDEA也很顺手(*^_^*)
第二遍写一下就AC了,除了一个剪枝的地方没想到xixi
40. 组合总和 II
题目链接
题目描述:
给定一个数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
说明: 所有数字(包括目标数)都是正整数。解集不能包含重复的组合。
示例 1:
- 输入:
candidates = [10,1,2,7,6,1,5], target = 8, - 所求解集为:
[[1, 7],[1, 2, 5],[2, 6],[1, 1, 6]
]
示例 2:
- 输入:
candidates = [2,5,2,1,2], target = 5, - 所求解集为:
[[1,2,2],[5]
]
难点:
思路:
构造全局数组来标记元素是否被使用过,避免重复添加结果
- 构造candidates长度的布尔型全局数组used
- 在回溯的当前层遍历时进行判断
3. 如果当前元素等于上一个元素(i>0)并且上一个元素未使用,continue
class Solution {List<List<Integer>> result = new ArrayList<>();List<Integer> path = new ArrayList<>();boolean used[];public List<List<Integer>> combinationSum2(int[] candidates, int target) {used = new boolean[candidates.length];Arrays.fill(used, false);Arrays.sort(candidates);backtracking(candidates, target, 0, 0);return result;}public void backtracking(int[] candidates, int target, int curSum, int startIdx) {if (curSum > target) return;if (curSum == target) {result.add(new ArrayList<>(path));return;}for (int i = startIdx; i < candidates.length; i++) {if (curSum + candidates[i] > target) return;//难点if (i > 0 && candidates[i-1] == candidates[i] && !used[i-1]) {continue;}used[i] = true;path.add(candidates[i]);curSum += candidates[i];backtracking(candidates, target, curSum, i+1);path.remove(path.size()-1);curSum -= candidates[i];used[i] = false;}}
}
时长:
15min
收获:
构造数组来标记元素是否被使用
131. 分割回文串
题目链接
题目描述:
给定一个字符串 s,将 s 分割成一些子串,使每个子串都是回文串。
返回 s 所有可能的分割方案。
示例: 输入: “aab” 输出: [ [“aa”,“b”], [“a”,“a”,“b”] ]
难点:
如何定义切割?
什么时候收集结果?
在哪剪枝?
思路:
每次遍历到的元素,想象一个虚拟的分隔符在其后
用区间[startIdx, i]
来取子串,并判断其是否是回文串
- 如果不是,continue(剪枝)
- 如果是,加入path
class Solution {List<List<String>> result = new ArrayList<>();List<String> path = new ArrayList<>();public List<List<String>> partition(String s) {backTracking(s, 0);return result;}private void backTracking(String s, int startIdx) {//如果起始位置大于s的大小,说明找到了一组分割方案if (startIdx >= s.length()) {result.add(new ArrayList(path));return;}for (int i = startIdx; i < s.length(); i++) {//如果是回文子串,则记录if (isPalindrome(s, startIdx, i)) {String str = s.substring(startIdx, i + 1);path.add(str);} else {continue; //剪枝}//起始位置后移,保证不重复backTracking(s, i + 1);path.remove(path.size()-1);}}//判断是否是回文串private boolean isPalindrome(String s, int startIdx, int end) {for (int i = startIdx, j = end; i < j; i++, j--) {if (s.charAt(i) != s.charAt(j)) {return false;}}return true;}
}
时长:
20min
收获:
切个问题