代码随想录算法刷题训练营day27：LeetCode(39)组合总和、LeetCode(40)组合总和 II、LeetCode(131)分割回文串

代码随想录算法刷题训练营day27：LeetCode(39)组合总和、LeetCode(40)组合总和 II、LeetCode(131)分割回文串

LeetCode(39)组合总和
题目

代码

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;class Solution {public List<List<Integer>> result=new ArrayList<>();public List<Integer> path=new ArrayList<>();/* public boolean flag=true;//加一个判断状态 */public List<List<Integer>> combinationSum(int[] candidates, int target) {//等于保留退，大于就退Arrays.sort(candidates);if(candidates[0]>target){return result;//处理边角料情况}int index=0;//可以重复选择backtracking(candidates,target,index);return result;}public void backtracking(int[] candidates,int target,int index){/* int sum = numbers.stream().reduce(Integer::sum).orElse(0); 求和公式*/int sum=path.stream().reduce(Integer::sum).orElse(0);if(sum>=target){if(sum==target){List<Integer> dateTemp=Arrays.asList(new Integer[path.size()]);//浅拷贝Collections.copy(dateTemp, path);result.add(dateTemp);}return;}//单次递归for(int i=index;i<candidates.length;i++){//这里是为了让它动path.add(candidates[i]);backtracking(candidates, target, i);//巧秒啊---深度//回溯path.remove(path.size()-1);}}
}

LeetCode(40)组合总和 II
题目

代码

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;class Solution {public List<List<Integer>> result=new ArrayList<>();public List<Integer> path=new ArrayList<>();public List<List<Integer>> combinationSum2(int[] candidates, int target) {//题目含义：每个元素仅使用一次，并完成去重，产生重复的结果，进行去除//1，数组排序Arrays.sort(candidates);//2、创建状态数组，用于区别树枝重复和树层重复，树枝重复是可取的，树层重复是不可取的int[] used=new int[candidates.length];//3、调用递归函数----获取结果int startIndex=0;int sum=0;backtracking(candidates,used,target,startIndex,sum);return result;}//回溯函数public void backtracking(int[] candidates,int[] used,int target,int startIndex,int sum){if(sum>=target){if(sum==target){List<Integer> tempPath=Arrays.asList(new Integer[path.size()]);Collections.copy(tempPath, path);result.add(tempPath);}return;//退回去}for(int i=startIndex;i<candidates.length;i++){//去重的关键操作if(i>0&&candidates[i]==candidates[i-1]&&used[i-1]==0){//树枝上可以重复，树层上不可以重复-----定义一个状态变量continue;//当前回合循环不用}path.add(candidates[i]);sum=sum+candidates[i];used[i]=1;backtracking(candidates, used, target, i+1, sum);path.remove(path.size()-1);sum=sum-candidates[i];used[i]=0;//回溯，弹出来}}
}

LeetCode(131)分割回文串
题目

代码

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.List;class Solution {public List<List<String>> result=new ArrayList<>();public List<String> path=new ArrayList<>();public List<List<String>> partition(String s) {int startIndex=0;//调用回溯函数backtracking(s,startIndex);return result;}public void backtracking(String s,int startIndex){//递归终止条件---startIndex就是切割线if(startIndex==s.length()){//直接收集数据-----把判断回文数放到后面----要是回文数判断不成功，那一条直接砍掉List<String> tempPath=Arrays.asList(new String[path.size()]);Collections.copy(tempPath, path);result.add(tempPath);return;}//单次递归-forfor(int i=startIndex;i<s.length();i++){String date=s.substring(startIndex, i+1);//判断是否为回文数boolean flag=isPalindrome(date);if(flag==true){path.add(date);}else{//这条分支剪断---for遍历代表分支continue;}backtracking(s, i+1);path.remove(path.size()-1);//吐出来}}//判断回文数的代码public boolean isPalindrome(String date){char[] testdate=date.toCharArray();int i=0;int j=testdate.length-1;boolean flag=true;while(i<=j){if(testdate[i]!=testdate[j]){flag=false;break;}i++;j--;}return flag;}
}