算法通关村第十八关-黄金挑战回溯困难问题

发布时间:2023年12月18日

大家好我是苏麟 , 今天带来几道回溯比较困难的题 .

回溯有很多比较难的问题,这里我们看两个,整体来说这两个只是处理略复杂,还不是最难的问题 .

大纲

IP问题

描述 :

有效 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 93. 复原 IP 地址 :

复原IP地址 :

在这里插入图片描述
分析 :

该问题的思路与与前面的分割回文串基本一致,也是切割问题。回溯的第一步就是使用枚举将所有可能性搜出来,找到一个符合要求的就先切下来,后面的部分继续进行枚举和切割,如果到了最后发现不符合要求,则开始回溯。

本题的难度明显比上一题要大,主要是判断是否合法的要求更高了,比如第一个元素我们可以截取2、25255、2552,很显然到了2552之后就不合法了,此时就要回溯。后面也一样,假如我们第一层截取的是2,第二层就从”5525511135“中截取,此时可以有5,55,552,显然552已经不合法了,依次类推。画出图来就如下所示:

在这里插入图片描述
当然这里还要判断是0的情况等等,在字符串转换成数字一章,我们讲解了很多种要处理的情况,为此我们可以写一个方法单独来执行相关的判断。

另外,IP地址只有四段,不是无限分割的,因此本题只会明确的分成4段,不能多也不能少。所以不能用切割线切到最后作为终止条件,而是分割的段数到了4就必须终止。考虑到我们构造IP地址时还要手动给添加=个小数点,所以我们用变量pNum来表示小数点数量,pNum为3说明字符串分成了4段了。

要手动添加一个小数点,这要增加一个位置来存储,所以下一层递归的start要从i+2开始。其他的主要工作就是递归和回溯的过程了。这里的撤销部分要注意将刚刚加入的分隔符删掉,并且pNum也要-1 .

解析 :

class Solution {
    List<String> list = new ArrayList<>();
    public List<String> restoreIpAddresses(String s) {
        if(s.length() < 4 || s.length() > 12){
            return list;
        }
        dfs(s,0,0);
        return list;
    }
    public void dfs(String s,int start,int pNum){
        if(pNum == 3){
            if(isValue(s,start,s.length() - 1)){
                list.add(s);
            }
            return;
        }
        for(int i = start;i < s.length();i++){
            if(isValue(s,start,i)){
                s = s.substring(0,i + 1) + "." + s.substring(i + 1);
                pNum++;
                dfs(s,i + 2,pNum);
                pNum--;
                s = s.substring(0,i + 1) + s.substring(i + 2); 
            }else{
                break;
            }
        }
    }
    //判断是否合法
    public boolean isValue(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;
    }
}

这期就到这里 , 下期见!

文章来源:https://blog.csdn.net/sytdsqzr/article/details/134955197
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。