39. 组合总和
题目链接:39. 组合总和 - 力扣(LeetCode)
思路
既然题目说可以数组中的数可以无限制重复被选取,那么说明在选取该元素的下一个分支也可以继续使用。
选取和剪枝过程如图:
注意:为什么取了2以后,剩余元素为5,3。因为如果剩余元素为2,5,3的话在后续操作中会出现重复值的情况,不符合题意。
代码
1 // 剪枝优化 2 class Solution { 3 public List<List<Integer>> combinationSum(int[] candidates, int target) { 4 List<List<Integer>> res = new ArrayList<>(); 5 Arrays.sort(candidates); // 先进行排序 6 backtracking(res, new ArrayList<>(), candidates, target, 0, 0); 7 return res; 8 } 9 10 public void backtracking(List<List<Integer>> res, List<Integer> path, int[] candidates, int target, int sum, int idx) { 11 // 找到了数字和为 target 的组合 12 if (sum == target) { 13 res.add(new ArrayList<>(path)); 14 return; 15 } 16 17 for (int i = idx; i < candidates.length; i++) { 18 // 如果 sum + candidates[i] > target 就终止遍历 19 if (sum + candidates[i] > target) break; 20 path.add(candidates[i]); 21 backtracking(res, path, candidates, target, sum + candidates[i], i); 22 path.remove(path.size() - 1); // 回溯,移除路径 path 最后一个元素 23 } 24 } 25 }
40.组合总和II
题目链接:40. 组合总和 II - 力扣(LeetCode)
思路
这道题和上题思路差不多,不过在本题中存在重复数字,需要去重操作。
如果用map或者caontains函数去重会超时。
本题主要的麻烦是去重问题,而本题去重又分为树层去重(横向)和树枝去重(纵向),而在这道题中,我们只需要对树层去重,这时要注意要先对数组进行排序,目的是为了让相等的元素相邻在一起。 树层去重的方式 如果candidates[i] == candidates[i - 1]
并且 used[i - 1] == false
,就说明:元素相同且前一个树枝,使用了candidates[i - 1],
也就是说同一树层使用过candidates[i - 1]。
如图所示:![](/i/l/?n=23&i=blog/3089234/202302/3089234-20230227224437285-1946986069.png)
根据改图我们可以得到:
- used[i - 1] == true,说明同一树枝candidates[i - 1]使用过
- used[i - 1] == false,说明同一树层candidates[i - 1]使用过
为什么 used[i - 1] == false 就是同一树层呢,因为同一树层,used[i - 1] == false 才能表示,当前取的 candidates[i] 是从 candidates[i - 1] 回溯而来的。
而 used[i - 1] == true,说明是进入下一层递归,去下一个数,所以是树枝上去重,这道题树枝是不需要去重的。
代码
1 // 使用used数组 2 class Solution { 3 LinkedList<Integer> path = new LinkedList<>(); 4 List<List<Integer>> ans = new ArrayList<>(); 5 boolean[] used; 6 int sum = 0; 7 8 public List<List<Integer>> combinationSum2(int[] candidates, int target) { 9 used = new boolean[candidates.length]; 10 // 加标志数组,用来辅助判断同层节点是否已经遍历 11 Arrays.fill(used, false); 12 // 为了将重复的数字都放到一起,所以先进行排序 13 Arrays.sort(candidates); 14 backTracking(candidates, target, 0); 15 return ans; 16 } 17 18 private void backTracking(int[] candidates, int target, int startIndex) { 19 if (sum == target) { 20 ans.add(new ArrayList(path)); 21 } 22 for (int i = startIndex; i < candidates.length; i++) { 23 if (sum + candidates[i] > target) { 24 break; 25 } 26 // 出现重复节点,同层的第一个节点已经被访问过,所以直接跳过 27 if (i > 0 && candidates[i] == candidates[i - 1] && !used[i - 1]) { 28 continue; 29 } 30 used[i] = true; 31 sum += candidates[i]; 32 path.add(candidates[i]); 33 // 每个节点仅能选择一次,所以从下一位开始 34 backTracking(candidates, target, i + 1); 35 used[i] = false; 36 sum -= candidates[i]; 37 path.removeLast(); 38 } 39 } 40 }
1 // 不使用标记数组,用idx代替 2 class Solution { 3 List<List<Integer>> res = new ArrayList<>(); 4 LinkedList<Integer> path = new LinkedList<>(); 5 int sum = 0; 6 7 public List<List<Integer>> combinationSum2( int[] candidates, int target ) { 8 //为了将重复的数字都放到一起,所以先进行排序 9 Arrays.sort( candidates ); 10 backTracking( candidates, target, 0 ); 11 return res; 12 } 13 14 private void backTracking( int[] candidates, int target, int start ) { 15 if ( sum == target ) { 16 res.add( new ArrayList<>( path ) ); 17 return; 18 } 19 for ( int i = start; i < candidates.length && sum + candidates[i] <= target; i++ ) { 20 //正确剔除重复解的办法 21 //跳过同一树层使用过的元素 22 if ( i > start && candidates[i] == candidates[i - 1] ) { 23 continue; 24 } 25 26 sum += candidates[i]; 27 path.add( candidates[i] ); 28 // i+1 代表当前组内元素只选取一次 29 backTracking( candidates, target, i + 1 ); 30 31 int temp = path.getLast(); 32 sum -= temp; 33 path.removeLast(); 34 } 35 } 36 }
131.分割回文串
题目链接:131. 分割回文串 - 力扣(LeetCode)
思路
这道题有几个难点需要解决
1、切割问题可以抽象为组合问题
例如对于字符串abcdef:
- 组合问题:选取一个a之后,在bcdef中再去选取第二个,选取b之后在cdef中再选取第三个.....。
- 切割问题:切割一个a之后,在bcdef中再去切割第二段,切割b之后在cdef中再切割第三段.....。
如图。
2、如何模拟那些切割线
在处理组合问题的时候,递归参数需要传入startIndex,表示下一轮递归遍历的起始位置,这个startIndex就是切割线。
3、切割问题中递归如何终止
从树形结构的图中可以看出:切割线切到了字符串最后面,说明找到了一种切割方法,此时就是本层递归的终止条件。
4、在递归循环中如何截取子串
需要截取的子串startIndex
开始到i
,[i, j]
的区间范围是一个回文串,即找到截取位置的方法是从startIndex
出发找到一个最近的回文串。
5、如何判断回文
可以使用双指针法,一个指针从前向后,一个指针从后向前,如果前后指针所指向的元素是相等的,就是回文字符串了。
代码
1 class Solution { 2 List<List<String>> lists = new ArrayList<>(); 3 Deque<String> deque = new LinkedList<>(); 4 5 public List<List<String>> partition(String s) { 6 backTracking(s, 0); 7 return lists; 8 } 9 10 private void backTracking(String s, int startIndex) { 11 //如果起始位置大于s的大小,说明找到了一组分割方案 12 if (startIndex >= s.length()) { 13 lists.add(new ArrayList(deque)); 14 return; 15 } 16 for (int i = startIndex; i < s.length(); i++) { 17 //如果是回文子串,则记录 18 // 无需在终止地方进行判断,可以一边判断一边加入 19 if (isPalindrome(s, startIndex, i)) { 20 String str = s.substring(startIndex, i + 1); 21 deque.addLast(str); 22 } else { 23 continue; 24 } 25 //起始位置后移,保证不重复 26 backTracking(s, i + 1); 27 deque.removeLast(); 28 } 29 } 30 //判断是否是回文串 31 private boolean isPalindrome(String s, int startIndex, int end) { 32 for (int i = startIndex, j = end; i < j; i++, j--) { 33 if (s.charAt(i) != s.charAt(j)) { 34 return false; 35 } 36 } 37 return true; 38 } 39 }
标签:target,组合,int,sum,随想录,candidates,new,path,总和 From: https://www.cnblogs.com/xpp3/p/17162358.html