day28 回溯

• 93.复原IP地址
  • 本质上是分割问题
  • 判断一个分割的值是否有效
  • 回溯需要去掉 '.'

• 78.子集
  • ​​​​​​​收集每个树的节点

• 90.子集II
  • ​​​​​​​收集每个树的节点 + 树层去重

package algor.trainingcamp;

import java.util.ArrayList;
import java.util.List;

/**
 * @author lizhe
 * @version 1.0
 * @description: TODO
 * @date 2023/5/2 09:11
 *
 * 有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
 * 例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。
 * 给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/restore-ip-addresses
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCode93 {
    List<String> result = new ArrayList<>();

    public List<String> restoreIpAddresses(String s) {
        helper(s, 0, 0);
        return result;
    }

    public void helper(String s, int startIdx, int pointNum){
        //递归截止条件
        if(pointNum == 3){
            //判断第四段是否合法
            if(isValid(s, startIdx, s.length() - 1)){
                result.add(s);
            }

            return;
        }

        for(int i = startIdx;i < s.length();i++){
            if(isValid(s, startIdx, i)){
                //给当前的str打点
                s = s.substring(0, i + 1) + "." + s.substring(i + 1);
                pointNum++;
                /**
                 * 此时 '.'已经占了一位 递归从i + 2开始 都是细节
                 */
                helper(s, i + 2, pointNum);
                pointNum--;
                //回溯 去除 '.';
                s = s.substring(0, i + 1) + s.substring(i + 2);
            }else{
                //continue? 不满足条件 直接break
                break;
            }
        }
    }

    /**
     * 判断ip地址是否合法
     * 1. 0开头不合法
     * 2. 非数字字符不合法
     * 3. 大于255不合法
     */
    private boolean isValid(String s, int start, int end) {
        int sum = 0;
        if(start > end){
            return false;
        }

        //判断首位为0
        if(s.charAt(start) == '0' && start != end){
            return false;
        }

        for(int i = start;i <= end;i++){
            if(s.charAt(i) < '0' || s.charAt(i) > '9'){
                return false;
            }

            sum = 10 * sum + (s.charAt(i) - '0');
            if(sum > 255){
                return false;
            }
        }

        return true;
    }

    public static void main(String[] args) {
        LeetCode93 demo = new LeetCode93();
        demo.restoreIpAddresses("25525511135");
    }
}

package algor.trainingcamp;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author lizhe
 * @version 1.0
 * @description: 子集
 * @date 2023/5/2 10:17
 *
 * 给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
 *
 * 说明：解集不能包含重复的子集。
 * 示例: 输入: nums = [1,2,3] 输出: [ [3],   [1],   [2],   [1,2,3],   [1,3],   [2,3],   [1,2],   [] ]
 *
 * 不能包含重复子集:
 * 抽象成树 -> 寻找树的全部节点
 */
public class LeetCode78 {
    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> sub = new LinkedList<>();

    public List<List<Integer>> subsets(int[] nums) {
        if(null == nums || nums.length == 0){
            return res;
        }

        helper(nums, 0);
        return res;
    }

    public void helper(int[] nums, int startIdx){
        if(startIdx > nums.length){
            return;
        }


        res.add(new ArrayList<>(sub));

        for(int i = startIdx;i < nums.length;i++){
            sub.add(nums[i]);
            helper(nums, i + 1);
            sub.removeLast();
        }
    }
}

package algor.trainingcamp;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @author lizhe
 * @version 1.0
 * @description: LeetCode90_子集2
 * @date 2023/5/2 10:57
 *
 * 比LeetCode78多一个树层去重
 */
public class LeetCode90 {
    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> sub = new LinkedList<>();

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        if(null == nums || nums.length == 0){
            return res;
        }

        Arrays.sort(nums);
        boolean[] used = new boolean[nums.length];
        helper(nums, 0, used);
        return res;
    }

    public void helper(int[] nums, int startIdx, boolean[] used){
        if(startIdx > nums.length){
            return;
        }

        res.add(new ArrayList<>(sub));

        for(int i = startIdx;i < nums.length;i++){
            //树层去重
            if(i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false){
                continue;
            }

            used[i] = true;
            sub.add(nums[i]);
            helper(nums, i + 1, used);
            sub.removeLast();
            used[i] = false;
        }
    }
}