代码随想录刷题学习日记

仅为个人记录复盘学习历程，解题思路来自代码随想录

代码随想录刷题笔记总结网址:
代码随想录

93.复原IP地址

给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。有效的 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

提供参数：只包含数字的字符串s。

关键思路：是一个“分割”的思想，同时需要对ip地址格式的判断。

由于横向遍历是从少到多开始的，少的不行则多的一定不行，例如：“01”不行，“01”开头的后面无论怎么都不行，或者“256”不行，后面数字只会更大，也不行。所以在横向遍历时，满足条件即可回溯递归纵向遍历，如果发现不满足条件则可以直接跳出此循环。

我使用全局变量来记录单个结果，而在判断时根据点的个数判断是否进入终止条件的判断，确认点的个数等于三后，判断剩余字符串是否合法，如果合法则需要在此处补充单个结果，加入结果集后回溯，然后返回。

主要操作：

递归三要素

1.返回值类型和输入参数：

使用全局变量res记录全部结果，使用全局变量path记录单个结果，返回值类型为void；

需要输入参数数字字符串s，起始索引startIndex，加点数量pointNum，用pointNum判断是否允许进入终止条件的判断。起始索引避免重复遍历。

2.终止条件：

若加了三个点，且剩余字符满足条件，则加入结果集返回，否则直接返回。

3.单层递归逻辑：
for循环横向遍历，如果当前子串满足条件则使用回溯递归向下遍历，如果遇到不满足的直接终止佛如循环，因为遇到不满足的，后面的子串也不满足。

代码大致如下：

    public List<String>res;
    public String path;
    public List<String> restoreIpAddresses(String s) {

        res=new ArrayList<>();
        path="";
        backTrace(s,0,0);
        return res;
        
    }

    public void backTrace(String s,int startIndex,int pointNum){
        //终止条件
        if(pointNum==3){
            //第四段有效性判断
            if(isValid(s,startIndex,s.length()-1)){
                int temp=path.length();
                path=path+s.substring(startIndex,s.length());
                res.add(path);
                path=path.substring(0,temp);
            }
            return;
        }
        //单层递归逻辑
        for(int i=startIndex;i<s.length();i++){
            if(isValid(s,startIndex,i)){
                int temp=path.length();
                path=path+s.substring(startIndex,i+1)+".";
                pointNum++;
                backTrace(s,i+1,pointNum);
                pointNum--;
                path=path.substring(0,temp);
            }
            else{
                break;
            }

        }

    }

    public boolean isValid(String s,int start,int end){
        if(start>end) return false;
        if(s.charAt(start)=='0'&&start!=end)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) return false;
        }
        return true;
    }

78.子集

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

提供参数：整型数组nums。

关键思路：不重复的遍历整个解空间树，遍历的同时记录整个解空间树的每个节点，每个节点就是一个子集。

主要操作：

递归三要素

1.返回值类型和输入参数：

使用全局变量res记录所有结果，使用全局变量path记录单个结果，返回值类型为void；

需要输入参数nums，由于集合是一个组合问题，即{1,2,3}和{1，3，2}是等价的，不存在重复，所以需要记录起始索引startIndex。

2.终止条件：

当startIndex>=nums.length时，说明已经到达叶子节点，需要返回。

3.单层递归逻辑：

3.1记录该结点。

3.2使用for循环横向遍历解空间树，使用递归纵向遍历解空间树。

代码大致如下：

    public List<List<Integer>>res;
    public List<Integer>path;
    public List<List<Integer>> subsets(int[] nums) {
        res=new ArrayList<>();
        path=new ArrayList<>();
        backTrace(nums,0);
        return res;
        
    }
    public void backTrace(int[]nums,int startIndex){
        
        res.add(new ArrayList(path));
        //终止条件
        if(startIndex>=nums.length)return;

        //单层递归逻辑
        for(int i=startIndex;i<nums.length;i++){
            path.add(nums[i]);
            backTrace(nums,i+1);
            path.remove(path.size()-1);
        }
    }

原文地址：https://blog.csdn.net/weixin_73939095/article/details/143819409

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！