本文主要是介绍代码随想录算法训练营第二十七天| LeetCode39. 组合总和、LeetCode40.组合总和II、LeetCode131.分割回文串,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
#LeetCode 39. Combination Sum
#LeetCode 39. 视频讲解:带你学透回溯算法-组合总和(对应「leetcode」力扣题目:39.组合总和)| 回溯法精讲!_哔哩哔哩_bilibili
当建立树的结构的时候,target 可以限制树的深度,一旦大于target 则不会再进行后面的扩展。这个题目需要考虑的是数字可以被重复添加和使用,但是要注意组合的无序性,即:5, 2 = 2, 5。数字可以被重复添加是通过backtracking(candidates, target, sum, i); 这里的i 来实现的,之前的题目是i + 1。
代码:
class Solution {List<List<Integer>> result = new ArrayList<>();List<Integer> path = new ArrayList<>();public List<List<Integer>> combinationSum(int[] candidates, int target) {int sum = 0;backtracking(candidates, target, sum, 0);return result;}public void backtracking (int[] candidates, int target, int sum, int startIndex) {if (sum > target) {return;}if (sum == target) {result.add(new ArrayList<>(path));return;}for (int i = startIndex; i < candidates.length; i++) {path.add(candidates[i]);sum += candidates[i];backtracking(candidates, target, sum, i);sum -= candidates[i];path.remove(path.size() - 1);}}
}
Prune 后的代码:
实现的方式为:在处理candidates 数组之前对其进行排序,在每次在for loop 的添加之前会先与target 进行比较,如果大于target ,则break ,不再进行后面的比较。
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);int sum = 0;backtracking(candidates, target, sum, 0);return result;}public void backtracking (int[] candidates, int target, int sum, int startIndex) {if (sum > target) {return;}if (sum == target) {result.add(new ArrayList<>(path));return;}for (int i = startIndex; i < candidates.length; i++) {if (sum + candidates[i] > target) break;path.add(candidates[i]);sum += candidates[i];backtracking(candidates, target, sum, i);sum -= candidates[i];path.remove(path.size() - 1);}}
}
#LeetCode 40. Combination Sum II
#LeetCode 40. 视频讲解:回溯算法中的去重,树层去重树枝去重,你弄清楚了没?| LeetCode:40.组合总和II_哔哩哔哩_bilibili
有两个概念,树层(广度)和树枝(深度)。在这里的去重指的是树层去重,如果数组是[1, 1, 2]那么选择两个元素的话,选择第一个1 和2 ,和第二个1 和2 是相同的,这一组就需要去重。
used 数组记录状态很重要,要不然会很混乱以及可能造成树枝去重。区分是递归导致的重复还是遍历导致的重复。在for loop中的if 用于实现树枝去重,前一个树枝,使用了candidates[i - 1],也就是说同一树层使用过candidates[i - 1]。
代码:
class Solution {List<List<Integer>> result = new ArrayList<>();List<Integer> path = new ArrayList<>();int sum = 0;public List<List<Integer>> combinationSum2(int[] candidates, int target) { boolean[] used = new boolean[candidates.length];Arrays.fill(used, false);Arrays.sort(candidates);backtracking(candidates, target, 0, used);return result;}public void backtracking(int[] candidates, int target, int startIndex, boolean[] used) {if (sum == target) {result.add(new ArrayList<>(path));return;}for (int i = startIndex; i < candidates.length; i++) {if (sum + candidates[i] > target) {break;}if (i > 0 && candidates[i] == candidates[i - 1] && !used[i - 1]) {continue;}path.add(candidates[i]);used[i] = true;sum += candidates[i];backtracking(candidates, target, i + 1, used);used[i] = false;sum -= candidates[i];path.remove(path.size() - 1);}}
}
#LeetCode 131. Palindrome Partitioning
#LeetCode 131. 视频讲解:带你学透回溯算法-分割回文串(对应力扣题目:131.分割回文串)| 回溯法精讲!_哔哩哔哩_bilibili
分割其实也是组合的一种方式,具体的过程如图:
这里的分割回文串,用的是startIndex 来模拟那些切割线的。当遍历到了最后一个字符的时候,就会加入result 二维数组,这样的数组则是一个分割方式。判断是否是回文子串用的是双指针法,一个指针从前向后,一个指针从后向前,如果前后指针所指向的元素是相等的,就返回true(是回文字符串),否则返回flase (非回文字符串)。
代码:
class Solution {List<List<String>> result = new ArrayList<>();Deque<String> path = new LinkedList<>();public List<List<String>> partition(String s) {backTracking(s, 0);return result;}public void backTracking(String s, int startIndex) {if (startIndex >= s.length()) {result.add(new LinkedList<>(path));return;}for (int i = startIndex; i < s.length(); i++) {if (isPalindrome(s, startIndex, i)) {String subString = s.substring(startIndex, i + 1);path.addLast(subString);}else {continue;}backTracking(s, i + 1);path.removeLast();}}public boolean isPalindrome(String s, int startIndex, int i) {boolean palindrome = true;int leftIndex = startIndex;int rightIndex = i;int length = i - startIndex + 1;for (int j = leftIndex; j <= leftIndex + length / 2; j++) {if (s.charAt(j) == s.charAt(rightIndex)) {rightIndex -= 1;}else {palindrome = false;break;}}return palindrome;}
}
重启打卡ing...
这篇关于代码随想录算法训练营第二十七天| LeetCode39. 组合总和、LeetCode40.组合总和II、LeetCode131.分割回文串的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!