代码随想录算法刷题训练营day28：LeetCode(93)复原IP地址、LeetCode(78)子集、LeetCode(90)子集II

LeetCode(93)复原IP地址
题目
在这里插入图片描述

代码

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;class Solution {public List<String> result=new ArrayList<>();//存放最终结果public List<Integer> path=new ArrayList<>();//存放路径结果public  List<String> restoreIpAddresses(String s) {int startIndex=0;//调用回溯函数backtracking(s,startIndex);return result;}public  void backtracking(String s,int startIndex){//终止节点if(path.size()==4){List<Integer> tempdate=Arrays.asList(new Integer[path.size()]);Collections.copy(tempdate, path);StringBuffer date=new StringBuffer();for (Integer tempdate2 : tempdate) {date.append(String.valueOf(tempdate2));date.append(".");}date.deleteCharAt(date.length()-1);String tempDate=date.toString();result.add(tempDate);return ;}//单层递归循环逻辑for(int i=startIndex;i<s.length();i++){String date1=s.substring(startIndex, i+1);//把数据截取出来if(date1.length()>1&&date1.charAt(0)=='0'){continue;}if(date1.length()>3){continue;}int date2=Integer.parseInt(date1);if(date2<0||date2>255){continue;}path.add(date2);if(path.size()==4&&i+1!=s.length()){path.remove(path.size()-1);continue;//关键}backtracking(s, i+1);//回溯path.remove(path.size()-1);}}
}

LeetCode(78)子集
题目
在这里插入图片描述

代码

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<Integer>> result=new ArrayList<>();public List<Integer> path=new ArrayList<>();public List<List<Integer>> subsets(int[] nums) {/* List<Integer> nullPath=new ArrayList<>();result.add(nullPath); */int startIndex=0;backtracking(nums,startIndex);return result;}public void backtracking(int[] nums,int startIndex){//终止条件List<Integer> tempDate=Arrays.asList(new Integer[path.size()]);Collections.copy(tempDate, path);result.add(tempDate);for(int i=startIndex;i<nums.length;i++){path.add(nums[i]);backtracking(nums, i+1);path.remove(path.size()-1);}}
}

LeetCode(90)子集II
题目
在这里插入图片描述

代码

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Set;class Solution {public List<List<Integer>> result=new ArrayList<>();public List<Integer> path=new ArrayList<>();public List<List<Integer>> subsetsWithDup(int[] nums) {int startIndex=0;//排序Arrays.sort(nums);int[] used=new int[nums.length];//0代表没使用，1代表使用了backtracking(nums,used,startIndex);return result;}public void backtracking(int[] nums,int[] used, int startIndex){List<Integer>  tempPath=Arrays.asList(new Integer[path.size()]);Collections.copy(tempPath, path);result.add(tempPath);for(int i=startIndex;i<nums.length;i++){if(i>0&&nums[i]==nums[i-1]&&used[i-1]==0){//重点思考continue;}path.add(nums[i]);used[i]=1;backtracking(nums, used, i+1);path.remove(path.size()-1);used[i]=0;}   }
}