代码随想录阅读笔记-回溯【复原IP地址】

题目

给定一个只包含数字的字符串,复原它并返回所有可能的 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 地址。

示例 1:

  • 输入:s = "25525511135"
  • 输出:["255.255.11.135","255.255.111.35"]

示例 2:

  • 输入:s = "0000"
  • 输出:["0.0.0.0"]

示例 3:

  • 输入:s = "1111"
  • 输出:["1.1.1.1"]

示例 4:

  • 输入:s = "010010"
  • 输出:["0.10.0.10","0.100.1.0"]

示例 5:

  • 输入:s = "101023"
  • 输出:["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

提示:

  • 0 <= s.length <= 3000
  • s 仅由数字组成

思路 

这道题目大家仔细分析就能意识到这是切割问题,切割问题就可以使用回溯搜索法把所有可能性搜出来,和上一道回文子串题目就十分类似了。

切割问题可以抽象为树型结构,如图:

93.复原IP地址

回溯三部曲

1、递归参数

在回文子串问题中我们就提到切割问题类似组合问题。

startIndex一定是需要的,因为不能重复分割,记录下一层递归分割的起始位置。

本题我们还需要一个变量pointNum,记录添加逗点的数量。

vector<string> result;// 记录结果
// startIndex: 搜索的起始位置,pointNum:添加逗点的数量
void backtracking(string& s, int startIndex, int pointNum) {

2、递归终止条件

本题明确要求只会分成4段,所以不能用切割线切到最后作为终止条件,而是分割的段数作为终止条件。pointNum表示逗点数量,pointNum为3说明字符串分成了4段了。

然后验证一下第四段是否合法,如果合法就加入到结果集里

if (pointNum == 3) { // 逗点数量为3时,分隔结束
    // 判断第四段子字符串是否合法,如果合法就放进result中
    if (isValid(s, startIndex, s.size() - 1)) {
        result.push_back(s);
    }
    return;
}

3、单层搜索的逻辑

for (int i = startIndex; i < s.size(); i++)循环中 [startIndex, i] 这个区间就是截取的子串,需要判断这个子串是否合法。

如果合法就在字符串后面加上符号.表示已经分割。

如果不合法就结束本层循环,如图中剪掉的分支:

93.复原IP地址

然后就是递归和回溯的过程:

递归调用时,下一层递归的startIndex要从i+2开始(因为需要在字符串中加入了分隔符.),同时记录分割符的数量pointNum 要 +1。

回溯的时候,就将刚刚加入的分隔符. 删掉就可以了,pointNum也要-1。

代码如下:

for (int i = startIndex; i < s.size(); i++) {
    if (isValid(s, startIndex, i)) { // 判断 [startIndex,i] 这个区间的子串是否合法
        s.insert(s.begin() + i + 1 , '.');  // 在i的后面插入一个逗点
        pointNum++;
        backtracking(s, i + 2, pointNum);   // 插入逗点之后下一个子串的起始位置为i+2
        pointNum--;                         // 回溯
        s.erase(s.begin() + i + 1);         // 回溯删掉逗点
    } else break; // 不合法,直接结束本层循环
}
判断子串是否合法

最后就是在写一个判断段位是否是有效段位了。

主要考虑到如下三点:

  • 段位以0为开头的数字不合法
  • 段位里有非正整数字符不合法
  • 段位如果大于255了不合法

代码如下:

// 判断字符串s在左闭又闭区间[start, end]所组成的数字是否合法
bool isValid(const string& s, int start, int end) {
    if (start > end) {
        return false;
    }
    if (s[start] == '0' && start != end) { // 0开头的数字不合法
            return false;
    }
    int num = 0;
    for (int i = start; i <= end; i++) {
        if (s[i] > '9' || s[i] < '0') { // 遇到非数字字符不合法
            return false;
        }
        num = num * 10 + (s[i] - '0');
        if (num > 255) { // 如果大于255了不合法
            return false;
        }
    }
    return true;
}

可以写出如下回溯算法C++代码:

class Solution {
private:
    vector<string> result;// 记录结果
    // startIndex: 搜索的起始位置,pointNum:添加逗点的数量
    void backtracking(string& s, int startIndex, int pointNum) {
        if (pointNum == 3) { // 逗点数量为3时,分隔结束
            // 判断第四段子字符串是否合法,如果合法就放进result中
            if (isValid(s, startIndex, s.size() - 1)) {
                result.push_back(s);
            }
            return;
        }
        for (int i = startIndex; i < s.size(); i++) {
            if (isValid(s, startIndex, i)) { // 判断 [startIndex,i] 这个区间的子串是否合法
                s.insert(s.begin() + i + 1 , '.');  // 在i的后面插入一个逗点
                pointNum++;
                backtracking(s, i + 2, pointNum);   // 插入逗点之后下一个子串的起始位置为i+2
                pointNum--;                         // 回溯
                s.erase(s.begin() + i + 1);         // 回溯删掉逗点
            } else break; // 不合法,直接结束本层循环
        }
    }
    // 判断字符串s在左闭又闭区间[start, end]所组成的数字是否合法
    bool isValid(const string& s, int start, int end) {
        if (start > end) {
            return false;
        }
        if (s[start] == '0' && start != end) { // 0开头的数字不合法
                return false;
        }
        int num = 0;
        for (int i = start; i <= end; i++) {
            if (s[i] > '9' || s[i] < '0') { // 遇到非数字字符不合法
                return false;
            }
            num = num * 10 + (s[i] - '0');
            if (num > 255) { // 如果大于255了不合法
                return false;
            }
        }
        return true;
    }
public:
    vector<string> restoreIpAddresses(string s) {
        result.clear();
        if (s.size() < 4 || s.size() > 12) return result; // 算是剪枝了
        backtracking(s, 0, 0);
        return result;
    }
};

  • 时间复杂度: O(3^4),IP地址最多包含4个数字,每个数字最多有3种可能的分割方式,则搜索树的最大深度为4,每个节点最多有3个子节点。
  • 空间复杂度: O(n)

最后附上笔者自己的代码,跟大家分享一下问题,代码如下:

class Solution {
public:
    vector<string> result;
    vector<int> path;
    string tmp;
    void backtracing(string s , int index)
    {
        if(index >= s.size())
        {
            if(path.size() == 4)
            {
                string re;
                re = std::to_string(path[0]);
                for(int i = 1 ; i < 4 ; i++)
                {
                    re += '.';
                    re += std::to_string(path[i]);
                }
                result.push_back(re);
                return;
            }
            return;
        }
        for(int i = index ; i < s.size() ; i++)
        {
            tmp = s.substr(index,i-index+1);
            if(tmp.size()>1 && tmp.substr(0,1) == "0") continue;
            long tmpNum;
            std::istringstream ss(tmp);
            ss >> tmpNum;
            // long long tmpNum = stoll(tmp);
            if(tmpNum < 0 || tmpNum > 255) continue;
            path.push_back(tmpNum);
            backtracing(s,i+1);
            path.pop_back();
        }
    }
    vector<string> restoreIpAddresses(string s) {
        backtracing(s,0);
        return result;
    }
};

思路和上面差不多,只不过我将每次的string结果保存到一个vector<int>path中,判断结束的条件就变成了这个vector的大小是否为4(和最上面代码提到的逗点是一个思路,不同的实现),判断是否满足条件就变成了判断vector中的四个整数是否以0开头,是否超过255,如果符合条件并且path大小为4满足要求,那么再按照要求将这四个整数中间插入"."再变成字符串并push进result中。想要跟大家分享的问题在for循环中,有一句被注释掉的语句long long tmpNum = stoll(tmp);这是我原来使用的将字符串转为整数类型的语句,但是提交时有一个样例没有通过,如下图:

提示超出范围,也就是样例中的数据大到无法通过stoll进行转换,这时候我们可以使用istringstream 进行转换 ,具体方法为:std::istringstream ss(tmp);ss >> tmpNum;使用 istringstream可以从字符流中读取整数,就可以忽略要转换数据的范围问题。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/546639.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

D3-八数码

D3-八数码 题目描述解题思路代码如下 题目描述 解题思路 本题若直接在3*3网格中思考较为困难&#xff0c;可以转换为一维的字符串&#xff0c;在一维字符串中考虑较为简单&#xff0c;要注意本题中两个字符交换位置时只能是x和另外字符交换&#xff0c;本题另外一个难点在于如何…

TypeScript系列之-深度理解基本类型画图讲解

JS的类型(8)&#xff1a; null undefined string number boolean bigint symbol object&#xff08;含 Array, Function,Date.....&#xff09; TS的类型(87): 以上所有&#xff0c;加上 void, never, enum, unknown, any 再加上自定义类型 type interface 上一节我们说…

判断IQ水平-第12届蓝桥杯选拔赛Python真题精选

[导读]&#xff1a;超平老师的Scratch蓝桥杯真题解读系列在推出之后&#xff0c;受到了广大老师和家长的好评&#xff0c;非常感谢各位的认可和厚爱。作为回馈&#xff0c;超平老师计划推出《Python蓝桥杯真题解析100讲》&#xff0c;这是解读系列的第50讲。 判断IQ水平&#…

利用栈删除数组中重复元素

先将数据排序&#xff08;降序或升序&#xff09; 建立一个“栈”&#xff0c;三种情况&#xff1a; 1.栈为空&#xff1a;压入一个元素 2.栈不为空 且 栈顶元素不等于将入栈元素&#xff1a;压入一个元素 3.栈不为空 且 栈顶元素等于将入栈元素&#xff1a;删除将压入元素…

SCI 四区(JEI)投稿到录用过程中的经历和心得体会

计算机视觉领域中&#xff0c;包含目标检测、三维重建、语义分割、图像分类等分支。其中&#xff0c;目标检测分支最卷&#xff0c;你知道的&#xff0c;没有背景和资源&#xff0c;发一篇SCI属实不易。本篇博客详细介绍本人投稿到录用过程中的经历和心得。 目录 1. 硬件资源落…

微信云开发小程序的服务器是属于服务商的还是商家的

越来越多的小程序&#xff0c;选择使用微信云开发来进行开发。然而&#xff0c;关于微信云开发小程序的服务器归属权问题&#xff0c;往往会引起一些商家的疑虑。本文将详细解析微信云开发小程序的服务器是属于服务商的还是商家的。 首先&#xff0c;我们需要明确微信云开发的概…

maven引入外部jar包

将jar包放入文件夹lib包中 pom文件 <dependency><groupId>com.jyx</groupId><artifactId>Spring-xxl</artifactId><version>1.0-SNAPSHOT</version><scope>system</scope><systemPath>${project.basedir}/lib/Spr…

1042: 中缀表达式转换为后缀表达式

解法&#xff1a;直接给算法 创建一个栈和一个空的后缀表达式字符串。 遍历中缀表达式中的每个字符。 如果当前字符是操作数&#xff0c;直接将其添加到后缀表达式字符串中。 如果当前字符是操作符&#xff0c;需要将其与栈顶的操作符进行比较&#xff1a; 如果栈为空&#…

动态规划专练( 337.组合总和Ⅳ)

337.组合总和Ⅳ 给你一个由 不同 整数组成的数组 nums &#xff0c;和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。 题目数据保证答案符合 32 位整数范围。 示例 1&#xff1a; 输入&#xff1a;nums [1,2,3], target 4 输出&#x…

2022年蓝桥杯省赛软件类C/C++B组----积木画

想借着这一个题回顾一下动态规划问题的基本解法&#xff0c;让解题方法清晰有条理&#xff0c;希望更多的人可以更轻松的理解动态规划&#xff01; 目录 【题目】 【本题解题思路】 【DP模版】 总体方针&#xff1a; 具体解题时的套路&#xff1a; 【题目】 【本题解题思…

Python判断节假日的几种方式,你学废了吗?

最近在推进信息安全巡检的工作&#xff0c;按公司制度要求和信息安全标准&#xff0c;要求按时对硬件设备、网络、机房、应用系统、数据库等等做巡检工作。为了保证达到信息安全的目标&#xff0c;要求在每周四和节假日的前一天对各类设备和系统进行巡检。 1、使用holidays库判…

zookeeper分布式应用程序协调服务+消息中间件kafka分布式数据处理平台

一、zookeeper基本介绍 1.1 zookeeper的概念 Zookeeper是一个开源的分布式的&#xff0c;为分布式框架提供协调服务的Apache项目。 是Hadoop和Hbase的重要组件。它是一个为分布式应用提供一致性服务的软件&#xff0c;提供的功能包括&#xff1a;配置维护、域名服务、…

python小游戏

这些游戏你玩过几个&#xff1f; 1.贪吃蛇2.吃豆人3.加农炮4.四子棋5. Fly Bird<font color #f3704ab>6.记忆&#xff1a;数字对拼图游戏&#xff08;欢迎挑战&#xff01;用时&#xff1a;2min&#xff09;7.乒乓球8.上课划水必备-井字游戏&#xff08;我敢说100%的人都…

代码随想录算法训练营第二十七天|39.组合总和、40.组合总和II、131.分割回文串

39.组合总和 思路&#xff1a; 本题和77.组合 &#xff0c;216.组合总和III的区别是&#xff1a;本题没有数量要求&#xff0c;可以无限重复&#xff0c;但是有总和的限制&#xff0c;所以间接的也是有个数的限制。 本题搜索的过程抽象成树形结构如下&#xff1a; 注意图中叶…

《HF经理》:二认知误区

一、管理者掌握重要权力&#xff1a; 二、全力来自管理者的职位&#xff1a; 三、管理者必须控制自己的直接下属&#xff1a; 对策&#xff1a;展示自己的品质&#xff0c;能力和影响力 四、管理者必须建立良好的个人关系&#xff1a; 五、管理这必须确保一切运行正常&…

【爬虫开发】爬虫从0到1全知识md笔记第5篇:Selenium课程概要,selenium的其它使用方法【附代码文档】

爬虫开发从0到1全知识教程完整教程&#xff08;附代码资料&#xff09;主要内容讲述&#xff1a;爬虫课程概要&#xff0c;爬虫基础爬虫概述,,http协议复习。requests模块&#xff0c;requests模块1. requests模块介绍,2. response响应对象,3. requests模块发送请求,4. request…

分享2024 golang学习路线

写在前面 Go语言&#xff08;也称为Golang&#xff09;是Google开发的一种静态强类型、编译型语言&#xff0c;它具有简洁、快速、安全、并发等特点&#xff0c;尤其适合构建大型软件、微服务架构和云平台服务。Go的学习曲线相对平缓&#xff0c;社区活跃&#xff0c;是现代编…

韩顺平 | 零基础快速学Python(16) 文件处理

文件 输入与输出 输入&#xff1a;数据从数据源(文件)到程序(内存)&#xff1b; 输出&#xff1a;数据从程序(内存)到数据源(文件)。 #mermaid-svg-06PG6JZq4jJMV1oH {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-sv…

五、LoadBalancer负载均衡服务调用

一、Ribbon目前也进入维护模式 1、是什么 Spring Cloud Ribbon是基于Netflix Ribbon实现的一套客户端负载均衡的工具。 简单的说&#xff0c;Ribbon是Netflix发布的开源项目&#xff0c;主要功能是提供客户端的软件负载均衡算法和服务调用。Ribbon客户端组件提供一系列完善的…

掌握CRM+邮箱技巧:销售速度与客户信任双丰收

在千行百业都在谈提效的今天&#xff0c;如果您的销售团队效率较低&#xff0c;恐怕很难过好2024。销售团队提效是个大话题&#xff0c;总的说来就是销售团队需要在正确的时间做正确的事。如何做到&#xff1f;自然要借助CRM工具。过去我们也讲了不少CRM如何辅助销售团队提效的…