力扣日记1.28-【回溯算法篇】93. 复原 IP 地址
力扣日记:【回溯算法篇】93. 复原 IP 地址
日期:2023.1.28
参考:代码随想录、力扣
93. 复原 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 中的任何数字。你可以按 任何 顺序返回答案。
示例 1:
输入:s = “25525511135”
输出:[“255.255.11.135”,“255.255.111.35”]
示例 2:
输入:s = “0000”
输出:[“0.0.0.0”]
示例 3:
输入:s = “101023”
输出:[“1.0.10.23”,“1.0.102.3”,“10.1.0.23”,“10.10.2.3”,“101.0.2.3”]
提示:
- 1 <= s.length <= 20
- s 仅由数字组成
题解
class Solution {
public:vector<string> results;string path = ""; vector<string> restoreIpAddresses(string s) {backtracking(s, 0, 0);return results;}int validInt(string s) {// 0xx 异常情况if (s.size() > 1 && s[0] == '0') return -1; // 注意这里是'0'啊!!!if (s.size() >= 4) return -1; // 四位数,则一定无效int num = stoi(s);if (num >=0 && num <= 255) return num;return -1; // 其他情况返回-1表示invalid}// 参数:count为path中已有"."的数量void backtracking(string s, int startindex, int count) {// 终止条件:count达到3if (count == 3) {// 直接对最后一个值进行判断(当"."有3个了,剩余的就是最后一个值了string sub = s.substr(startindex, s.size() - startindex);if (validInt(sub) != -1) { // 最后一个值有效path += sub;results.push_back(path); // 添加之后记得回溯!!!path.resize(path.size() - sub.size());}return; // 无效则直接返回}// for 循环横向遍历 [startindex, i]表示截取的元素for (int i = startindex; i < s.size(); i++) {// 如果剩余的字符个数不足使ip达到四个数,直接return(这个也可以写在条件里)if (s.size() - i - 1 < 4 - count - 1) return;// count 在进入下一层时才会+1// 截取当前元素并转换string sub = s.substr(startindex, i - startindex + 1);int num = validInt(sub);// 如果当前值无效,直接return,不需再遍历当前层(后面都无效)if (num == -1) return;// 如果值有效path += sub + ".";// 递归backtracking(s, i + 1, count + 1); // startindex指向i下一个元素,count + 1 表示"."多了一个// 回溯path.resize(path.size() - (sub.size() + 1)); // 删除sub + "."}}
};
复杂度
时间复杂度: O(3^4),IP地址最多包含4个数字,每个数字最多有3种可能的分割方式,则搜索树的最大深度为4,每个节点最多有3个子节点。
空间复杂度: O(n)
by 代码随想录
思路总结
-
本题也是一道切割类型的题目,“切割”思路(截取、纵向递归、横向for遍历)可类比131. 分割回文串。
-
首先关键也是要转换为组合问题(得到树状结构),这里我对示例3(即s=“101023”)进行模拟构建出树状图
-
-
从树状图总结规律:
- 参数:首先根据 131. 分割回文串的截取思路,这里还是需要一个
startindex
来表示截取的起始位置;除此之外,定义一个count
表示截取的次数(path中"."的数量),见下方。 - 终止条件:当我们截取了三次(即添加了三个".")之后,实际上就完成了分割(得到四个值了),此时path中已经添加了前三个有效值,因此在终止条件处对直接对最后一个值进行判断,如果剩余的字符能构成一个有效值,则path为有效的ip地址,可添加入results中(这里尤其要注意path添加了最后一个值后要回溯,即弹出该值!!!)
- for 横向遍历:
- 基础:每次遍历截取[startindex, i]的元素作为当前值(节点)。
- 剪枝:这里观察图中“剩余值不足,不再遍历”的情况,表示剩余的字符个数不足以使得ip地址达到四个数(如对“10.1023”取102后,剩余3,而构成ip地址还需要两个值,所以不足。用
count
记录当前path中已有的值的个数,则此剪枝条件可表示为if (s.size() - i - 1 < 4 - count - 1) return;// count 在进入下一层时才会+1
- 至于开始递归的条件,即当前值需有效才能放入path并递归截取后面的元素(类比131. 分割回文串中需为回文串才处理节点并开始递归)——因此将截取的元素进行
s->int
转换并判断转换是否有效:- 如果值无效,则由图可知,后面都无效,不需要再遍历当前层,直接return;
- 值有效的话,便是处理节点(添加值)、递归、回溯:注意path字符串添加时可直接用+,但是回溯删除时,得用
resize()
或erase()
;递归时startindex指向i的下一个值,而count也要+1,表示path多添加了一个值(多了一个".")
- 判断值是否有效:
- 首先是排除
0xx
的情况,如023
(这里要注意比较时需与字符'0'
进行比较 ) - 接着是截取元素对应整数需在[0,255]范围内。注意这里由于
stoi()
函数在值较大时溢出,所以先排除了字符个数>=4的情况。 - 对有效值返回对应值,无效值返回-1。
- 首先是排除
- 参数:首先根据 131. 分割回文串的截取思路,这里还是需要一个
-
经过调试才发现的bug:
validInt()
排除0xx
异常值时,写成了s[0]==0
,注意应该是'0'
stoi()
值溢出,所以添加了先排除四位数及以上的情况。- 终止条件中,path添加了最后一个值但没有回溯,导致结果集出现异常值,记得path每次添加都要回溯。
-
TODO:进一步优化:
- 不使用path,而是直接在原字符串上添加
"."
;s.insert(s.begin() + i + 1 , '.'); // 在i的后面插入一个逗点` ... s.erase(s.begin() + i + 1); // 回溯删掉逗点
- 不切割字符串得到子串进行是否为有效值的判断,而是用下标索引。
// 判断字符串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; }
- 详见代码随想录思路。
- 不使用path,而是直接在原字符串上添加
相关文章:

力扣日记1.28-【回溯算法篇】93. 复原 IP 地址
力扣日记:【回溯算法篇】93. 复原 IP 地址 日期:2023.1.28 参考:代码随想录、力扣 93. 复原 IP 地址 题目描述 难度:中等 有效 IP 地址 正好由四个整数(每个整数位于 0 到 255 之间组成,且不能含有前导 0&…...

Java 的反射学习总结
目录 一、什么是反射? 二、如何获取类对象? 三、如何通过类对象来创建类的对象? 四、类对象获取类构造器的方式 五、通过类对象获取类的属性 六、通过类对象获取类的方法 一、什么是反射? 反射是指在运行时动态地获取、检查…...
图论第二天|695. 岛屿的最大面积 1020. 飞地的数量 130. 被围绕的区域 417. 太平洋大西洋水流问题 827.最大人工岛
目录 Leetcode695. 岛屿的最大面积Leetcode1020. 飞地的数量Leetcode130. 被围绕的区域Leetcode417. 太平洋大西洋水流问题Leetcode827.最大人工岛 Leetcode695. 岛屿的最大面积 文章链接:代码随想录 题目链接:695. 岛屿的最大面积 思路:dfs …...

【JavaScript 基础入门】02 JavaScrip 详细介绍
JavaScrip 详细介绍 目录 JavaScrip 详细介绍1. JavaScript 是什么2. JavaScript的作用3. HTML/CSS/JS 的关系4. 浏览器执行 JS 简介5. JavaScript 的组成6. JavaScript 的特点 1. JavaScript 是什么 JavaScript,通常缩写为 JS,是一种高级的,…...

鸿蒙(HarmonyOS)项目方舟框架(ArkUI)之CheckboxGroup组件
鸿蒙(HarmonyOS)项目方舟框架(ArkUI)之CheckboxGroup组件 一、操作环境 操作系统: Windows 10 专业版、IDE:DevEco Studio 3.1、SDK:HarmonyOS 3.1 二、CheckboxGroup组件 提供多选框组件,通常用于某选项的打开或关…...

【极数系列】Flink配置参数如何获取?(06)
文章目录 gitee码云地址简介概述01 配置值来自.properties文件1.通过路径读取2.通过文件流读取3.通过IO流读取 02 配置值来自命令行03 配置来自系统属性04 注册以及使用全局变量05 Flink获取参数值Demo1.项目结构2.pom.xml文件如下3.配置文件4.项目主类5.运行查看相关日志 gite…...

【docker】linux系统docker的安装及使用
一、docker应用的安装 1.1 安装方式 Docker的自动化安装,即使用提供的一键安装的脚本,进行安装。 官方的一键安装方式:curl -fsSL https://get.docker.com | bash -s docker --mirror Aliyun 国内 daocloud一键安装命令:curl -s…...

【C++】一题掌握空指针
今天看见一道面试题,比较有意思,这一分享出来: 1.下面程序能编译通过吗? 2.下面程序会崩溃吗?在哪里崩溃 class A {public:void PrintA(){cout<<_a<<endl;}void Show(){cout<<"Show()"&…...
初识HarmonyOS
一、HarmonyOS VS Android 相信很多关注鸿蒙的⼈,都会关注的⼀个焦点话题,那就是HarmonyOS是不是Android的套壳,对于这个话题,我只想阐明以下⼏个观点: HarmonyOS并不是Android的替代品,HarmonyOS与Android并⾮同⼀个赛道。HarmonyOS⽬前缺乏⽣态⽀持这⼀点远远⽐不上An…...

备战蓝桥杯---二分(入门)
话不多说,先来个模板题来回顾一下上次讲的: 下面是AC代码: 下面进入正题: 本题对1,2行与3,4行组合,再用二分查找即可实现n^2logn的复杂度。 下面是AC代码: 接题: 让我们…...
开发 Chrome 浏览器插件时进行 Vue3+Vite 多页面多入口配置
使用 Vite 开发 Chrome 插件时,构建多页面以及多 js 文件 因为发现 Vite 多页面构建有很多分歧以及问题点,所以我把我在 Chrome 插件开发上面使用到的 Vite 多页面以及多入口文件构建配置单独拿出来 开发 Chrome 插件是,一般会需要一个 popup…...

MacOS X 中 OpenGL 环境搭建 Makefile的方式
1,预备环境 安装 brew: /bin/bash -c "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/HEAD/install.sh)" 安装glfw: brew install glfw 安装glew: brew install glew 2.编译 下载源代码…...

前端工程化之:webpack1-6(编译过程)
一、webpack编译过程 webpack 的作用是将源代码编译(构建、打包)成最终代码。 整个过程大致分为三个步骤: 初始化编译输出 1.初始化 初始化时我们运行的命令 webpack 为核心包, webpack-cli 提供了 webpack 命令,通过…...
javaweb学习问题集
1 创建一个Javaweb项目 因为项目要放在tomcat10里运行,在添加tomcat10的依赖时,右键模块没有add frameworks support ,解决方法:按两下shift键,直接搜索 add frameworks support index.jsp文件我们已经不用了 我们在ideal上开发…...

java—AWT
AWT 课程:1、GUI编程简介_哔哩哔哩_bilibili 一.介绍 包含了很多类和接口!GUI!元素:窗口、按钮、文本框java.awt 二.窗口 1.构造 2.方法 // 实例化frame类Frame frame new Frame("这个一个框");// 设置可见性frame.…...

SQL注入-sqli-labs-master第一关
实验环境: Nginx.1.15.11 MySQL:5.7.26 实验步骤: 1.第一步: 在id1后加入一个闭合符号,如果报错,再在后面加上 -- 将后面注释掉,如果不报错,则证明为字符型。 http://127.0.0.1/…...

简述云原生基础定义及关键技术
云原生是什么 云原生是面向“云”而设计的应用,因此技术部分依赖于传统云计算的 3 层概念,基础设施即服务(IaaS)、平台即服务(PaaS)和软件即服务(SaaS)。 例如,敏捷的不可变基础设施交付类似于 IaaS,用来提供计算网络存储等基础资源,这些资源是可编程且不可变的,直…...
游戏中排行榜的后台实现
游戏中经常会有排行榜需求需要实现,例如常见的战力排行榜、积分排行榜等等。 排行榜一般会用到 Redis 来实现,原因是: Redis 基于内存操作,速度快Redis 提供了高效的有序集合 zset 例如创建一个名为 rank 的排行榜 # 为用户use…...

《动手学深度学习(PyTorch版)》笔记3.1
Chapter3 Linear Neural Networks 3.1 Linear Regression 3.1.1 Basic Concepts 我们通常使用 n n n来表示数据集中的样本数。对索引为 i i i的样本,其输入表示为 x ( i ) [ x 1 ( i ) , x 2 ( i ) , . . . , x n ( i ) ] ⊤ \mathbf{x}^{(i)} [x_1^{(i)}, x_2…...

【贪吃蛇:C语言实现】
文章目录 前言1.了解Win32API相关知识1.1什么是Win32API1.2设置控制台的大小、名称1.3控制台上的光标1.4 GetStdHandle(获得控制台信息)1.5 SetConsoleCursorPosition(设置光标位置)1.6 GetConsoleCursorInfo(获得光标…...
在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module
1、为什么要修改 CONNECT 报文? 多租户隔离:自动为接入设备追加租户前缀,后端按 ClientID 拆分队列。零代码鉴权:将入站用户名替换为 OAuth Access-Token,后端 Broker 统一校验。灰度发布:根据 IP/地理位写…...

现代密码学 | 椭圆曲线密码学—附py代码
Elliptic Curve Cryptography 椭圆曲线密码学(ECC)是一种基于有限域上椭圆曲线数学特性的公钥加密技术。其核心原理涉及椭圆曲线的代数性质、离散对数问题以及有限域上的运算。 椭圆曲线密码学是多种数字签名算法的基础,例如椭圆曲线数字签…...
Java入门学习详细版(一)
大家好,Java 学习是一个系统学习的过程,核心原则就是“理论 实践 坚持”,并且需循序渐进,不可过于着急,本篇文章推出的这份详细入门学习资料将带大家从零基础开始,逐步掌握 Java 的核心概念和编程技能。 …...

学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2
每日一言 今天的每一份坚持,都是在为未来积攒底气。 案例:OLED显示一个A 这边观察到一个点,怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 : 如果代码里信号切换太快(比如 SDA 刚变,SCL 立刻变&#…...
【生成模型】视频生成论文调研
工作清单 上游应用方向:控制、速度、时长、高动态、多主体驱动 类型工作基础模型WAN / WAN-VACE / HunyuanVideo控制条件轨迹控制ATI~镜头控制ReCamMaster~多主体驱动Phantom~音频驱动Let Them Talk: Audio-Driven Multi-Person Conversational Video Generation速…...

佰力博科技与您探讨热释电测量的几种方法
热释电的测量主要涉及热释电系数的测定,这是表征热释电材料性能的重要参数。热释电系数的测量方法主要包括静态法、动态法和积分电荷法。其中,积分电荷法最为常用,其原理是通过测量在电容器上积累的热释电电荷,从而确定热释电系数…...

02.运算符
目录 什么是运算符 算术运算符 1.基本四则运算符 2.增量运算符 3.自增/自减运算符 关系运算符 逻辑运算符 &&:逻辑与 ||:逻辑或 !:逻辑非 短路求值 位运算符 按位与&: 按位或 | 按位取反~ …...
用 Rust 重写 Linux 内核模块实战:迈向安全内核的新篇章
用 Rust 重写 Linux 内核模块实战:迈向安全内核的新篇章 摘要: 操作系统内核的安全性、稳定性至关重要。传统 Linux 内核模块开发长期依赖于 C 语言,受限于 C 语言本身的内存安全和并发安全问题,开发复杂模块极易引入难以…...
Python第七周作业
Python第七周作业 文章目录 Python第七周作业 1.使用open以只读模式打开文件data.txt,并逐行打印内容 2.使用pathlib模块获取当前脚本的绝对路径,并创建logs目录(若不存在) 3.递归遍历目录data,输出所有.csv文件的路径…...

AWSLambda之设置时区
目标 希望Lambda运行的时区是东八区。 解决 只需要设置lambda的环境变量TZ为东八区时区即可,即Asia/Shanghai。 参考 使用 Lambda 环境变量...