代码随想录算法训练营第二十七天|93.复原IP地址、78.子集、90.子集II

93.复原IP地址

• 刷题https://leetcode.cn/problems/restore-ip-addresses/description/
• 文章讲解https://programmercarl.com/0093.%E5%A4%8D%E5%8E%9FIP%E5%9C%B0%E5%9D%80.html
• 视频讲解https://www.bilibili.com/video/BV1XP4y1U73i/?vd_source=af4853e80f89e28094a5fe1e220d9062

• 回溯树图示：

• 题解（字符串普通解法）：

class Solution {//存储结果List<String> result = new ArrayList<>();public List<String> restoreIpAddresses(String s) {//剪枝，去除非法长度if(s.length() > 12){return result;}restoreIpAddresses1(s, 0, 0);return result;}//startIndex:for循环起始index//pointNum:标记逗点添加的个数，作为递归出口public void restoreIpAddresses1(String s, int startIndex, int pointNum){//递归出口//已添加3个逗点，分割结束if(pointNum == 3){//需要判断最后一段是否合法(区间均为左闭右闭)if(isValid(s, startIndex, s.length() - 1)){result.add(s);}//无论是否合法，此时均需结束，returnreturn;}//递归回溯部分//以startIndex为划分界限for(int i = startIndex; i < s.length(); i++){//若当前划分区间符合要求则往下处理if(isValid(s, startIndex, i)){//加工逗点处理(substring左闭右开)//在i和i+1中间插入逗点s = s.substring(0, i + 1) + "." + s.substring(i + 1);//已添加了一个逗点pointNum++;//递归//需要把已添加逗点的位置空出来，所以是i+2为起始(i+1为逗点)restoreIpAddresses1(s, i + 2, pointNum);//回溯pointNum--;//空出了i+1的逗点位置，删掉逗点s = s.substring(0, i + 1) + s.substring(i + 2);}else{//若当前划分区间不合要求，则结束当前循环返回上一层break;}}}public boolean isValid(String s, int start, int end){//根据区间左闭右闭判断终止条件if(start > end){return false;}//不合法情况；0开头数字不合法，0单独的数字合法if(s.charAt(start) == '0' && start != end){return false;}int num = 0;for(int i = start; i <= end; i++){//字符Ascll码比较if(s.charAt(i) > '9' || s.charAt(i) < '0'){return false;}//计算当前总和是否合法num = num * 10 + (s.charAt(i) - '0');if(num > 255){return false;}}return true;}
}

78.子集

• 刷题https://leetcode.cn/problems/subsets/description/
• 文章讲解https://programmercarl.com/0078.%E5%AD%90%E9%9B%86.html
• 视频讲解https://www.bilibili.com/video/BV1U84y1q7Ci/?vd_source=af4853e80f89e28094a5fe1e220d9062

• 回溯树图示：

• 题解：

class Solution {//存放最后符合条件结果的集合List<List<Integer>> result = new ArrayList<>();//每次符合条件的结果LinkedList<Integer> path = new LinkedList<>();//这道题目与之前题目的区别在于：//这道题是求子集，回溯树上每一个结点都需要取值//之前的组合问题，回溯树上只取叶子结点的值public List<List<Integer>> subsets(int[] nums) {subsets1(nums, 0);return result;}public void subsets1(int[] nums, int startIndex){//需要先将当前结点放入最后结果集，因为若放在递归出口后面，就会漏掉叶子结点的结果result.add(new ArrayList<>(path));//递归出口if(startIndex >= nums.length){return;}for(int i = startIndex; i < nums.length; i++){path.add(nums[i]);//递归部分//为了防止集合重复，需要startIndex+1subsets1(nums, i + 1);//回溯部分path.removeLast();}}
}

90.子集II

• 刷题https://leetcode.cn/problems/subsets-ii/description/
• 文章讲解https://programmercarl.com/0090.%E5%AD%90%E9%9B%86II.html
• 视频讲解https://www.bilibili.com/video/BV1vm4y1F71J/?vd_source=af4853e80f89e28094a5fe1e220d9062
   

•  回溯树图示：

• 题解：

class Solution {//存储所有的结果List<List<Integer>> result = new ArrayList<>();//存放当前符合条件的结果LinkedList<Integer> path = new LinkedList<>();//标记当前元素是否使用过，用来进行树层去重boolean[] used;//本题与上一个的区别在于去重，其他则同样需要收集回溯树上的每一个结点public List<List<Integer>> subsetsWithDup(int[] nums) {if(nums.length == 0){return result;}Arrays.sort(nums);used = new boolean[nums.length];subsetsWithDup1(nums, 0);return result;}public void subsetsWithDup1(int[] nums, int startIndex){//因为需要添加回溯树上的每个结点，所以需要最先添加//并且为了不漏下叶子结点上的结果，要放在递归出口的前面result.add(new ArrayList<>(path));//递归出口if(startIndex >= nums.length){return;}//递归回溯部分for(int i = startIndex; i < nums.length; i++){//树层去重if(i > 0 && nums[i] == nums[i - 1] && !used[i - 1]){continue;}path.add(nums[i]);used[i] = true;//递归部分,上下级需要防重复subsetsWithDup1(nums, i + 1);//回溯部分path.removeLast();used[i] = false;}}
}