回溯算法 part04

发布时间:2024年01月10日

回溯算法 part04

今日任务

● 93.复原IP地址
● 78.子集
● 90.子集II

1.leetcode 93.复原IP地址

https://leetcode.cn/problems/restore-ip-addresses/description/

class Solution {
    List<String> result=new ArrayList<>();
    public List<String> restoreIpAddresses(String s) {
        StringBuilder path=new StringBuilder(s);
        backtracing(path,0,0);
        return result;
    }
    public void backtracing(StringBuilder s,int startIndex,int pointSum){
       if(pointSum==3){
           //证明已经有三个切割线了,对切割线以后的区间判断是不是有效的,
           if(isValid(s,startIndex,s.length()-1)){
               //如果是有效的,证明全员有效,
               //可以加入结果集中
               result.add(s.toString());
               return;
           }
       }
       for(int i=startIndex;i<s.length();i++){
           //从0开始
           //判断区间是不是有效的,有效的我们就进行切割,也就是加个逗点.
           if(isValid(s,startIndex,i)){
               //加逗点
               //StringBuilder库函数insert,在原来的字符串上改变
               s.insert(i+1,'.');//在要插入的地方,值
               //增加计数(切割线累加)
               pointSum+=1;

               //开始递归深度了
               backtracing(s,i+2,pointSum);//本来是不重复就是i+1,但是因为这里多了个逗点,需要继续跳过
               //开始回溯
                pointSum-=1;
                s.deleteCharAt(i+1);
           }else{
               //不有效
               break;
           }
           
       }
    }
    //判断是不是有效的[0,255],并且前导不为0
    public boolean isValid(StringBuilder s,int start,int end){
        if (start > end) {
            return false;
        }
        //前面开头为0,且后面没有字符了,那就是前导为0
        if (s.charAt(start) == '0' && start != end) { // 0开头的数字不合法
            return false;
        }
        int num = 0;
        for (int i = start; i <= end; i++) {
            if (s.charAt(i) > '9' || s.charAt(i) < '0') { // 遇到?数字字符不合法
                return false;
            }
            num = num * 10 + (s.charAt(i) - '0');
            if (num > 255) { // 如果?于255了不合法
                return false;
            }
        }
        return true;
    }
}

2.leetcode 78.子集

https://leetcode.cn/problems/subsets/description/

class Solution {
    List<List<Integer>> result=new ArrayList<>();
    //result.add(null);
    List<Integer> path=new ArrayList<>();
    public List<List<Integer>> subsets(int[] nums) {
        backtracing(nums,0);
        return result;
    }
    public void backtracing(int[] nums,int startIndex){
        result.add(new ArrayList<>(path));
        // if(startIndex==nums.length){
        //     result.add(new ArrayList<>(path));
        //     return;
        // }
        if (startIndex >= nums.length){ //终止条件可不加
            return;
        }
        for(int i=startIndex;i<nums.length;i++){
            path.add(nums[i]);
            backtracing(nums,i+1);
            path.removeLast();
        }
    }
}

3.leetcode 90.子集II

https://leetcode.cn/problems/subsets-ii/description/

class Solution {
    List<List<Integer>> result=new ArrayList<>();
    List<Integer> path=new ArrayList<>();
    boolean[] isUsed;
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        //将空集放进结果集中
        if(nums.length==0){
            result.add(path);
            return result;
        }
        isUsed=new boolean[nums.length];//提前将每个元素设置为false
         // 加标志数组,用来辅助判断同层节点是否已经遍历
        //Arrays.fill(isUsed, false);
        // 为了将重复的数字都放到一起,所以先进行排序
        Arrays.sort(nums);

        backtracing(nums,0);
        return result;
    }
    public void backtracing(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]&&!isUsed[i-1]){
                //isUsed初始化的时候是false,如果是用过那么会被标记为true
                //而这里是!isUsed,所以如果被用过,这里就是false
                continue;
                //而nums[i]==nums[i-1],证明现在的和之前的值是一样的,都是true的话,就都是用过的
            }
            //将这个用过的标记为true
            isUsed[i]=true;
            //进行加入
            path.add(nums[i]);
            //进行回溯
            backtracing(nums,i+1);//每次重新遍历都需要对布尔数组进行初始化,那么我们就不把它做参数了,一直放着下一次又是全false(下一层)
            path.removeLast();
            //撤销
            isUsed[i]=false;
        }
    }
}
文章来源:https://blog.csdn.net/Belle_Daisy/article/details/135492955
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。