代码随想录算法训练营第二十天|39. 组合总和、40.组合总和II、131.分割回文串
39. 组合总和
题目链接：. - 力扣（LeetCode）
文章讲解：代码随想录
https://www.bilibili.com/video/BV1KT4y1M7HJclass 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, target, 0, 0);
return result;
}
public void backtracking(int[] candidates, int target, int sum, int startIndex) {
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]);
backtracking(candidates, target, sum + candidates[i], i);
path.remove(path.size() - 1);
}
}
}40.组合总和II
题目链接：. - 力扣（LeetCode）
文章讲解：代码随想录
思路：定义一个used数组来去重。去重主要是在数层上操作。如果used[i-1]==false&&candidates[i]==candidates[i-1]，那么说明是在树层上，直接跳过；而如果used[i-1]==true，说明在树枝上，加入path中。因为在递归指的是树枝，在递归中used的值为true，该树枝递归完毕后，把used变为false。以此来判断是树层还是树枝上。
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, target, 0, 0);
return result;
}*/
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates);
boolean[] used = new boolean[candidates.length];
backtracking(candidates, target, 0, 0, used);
return result;
}
public void backtracking(int[] candidates, int target, int sum, 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] == false) {
continue;
}
path.add(candidates[i]);
used[i] = true;
backtracking(candidates, target, sum + candidates[i], i + 1, used);
path.remove(path.size() - 1);
used[i] = false;
}
}
}131.分割回文串
题目链接：. - 力扣（LeetCode）
文章讲解：代码随想录
思路： 回溯切割字符串，动态规划先求出字符串区间i到j是否是回文串。
class Solution {
List<List<String>> result = new ArrayList<>();
List<String> path = new ArrayList<>();
boolean[][] isPalindrome;
public List<List<String>> partition(String s) {
isPalindrome = new boolean[s.length()][s.length()];
for (int i = 0; i < s.length(); i++) {
for (int j = i; j >= 0; j--) {
if (i == j) {
isPalindrome[i][j] = true;
} else if (i - j == 1) {
isPalindrome[j][i] = (s.charAt(i) == s.charAt(j));
} else {
isPalindrome[j][i] = ((s.charAt(i) == s.charAt(j)) && isPalindrome[j+1][i-1]);
}
}
}
backtracking(s, 0);
return result;
}
public void backtracking(String s, int startIndex) {
if (startIndex >= s.length()) {
result.add(new ArrayList<>(path));
return;
}
for (int i = startIndex; i < s.length(); i++) {
if (isPalindrome[startIndex][i]) {
path.add(s.substring(startIndex, i + 1));
backtracking(s, i + 1);
path.remove(path.size() - 1);
}
}
}
}原文地址：https://blog.csdn.net/qq_73932604/article/details/143724740
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！