力扣日记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(获得光标…...

测试微信模版消息推送
进入“开发接口管理”--“公众平台测试账号”,无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息: 关注测试号:扫二维码关注测试号。 发送模版消息: import requests da…...
macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用
文章目录 问题现象问题原因解决办法 问题现象 macOS启动台(Launchpad)多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显,都是Google家的办公全家桶。这些应用并不是通过独立安装的…...

P3 QT项目----记事本(3.8)
3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...

PL0语法,分析器实现!
简介 PL/0 是一种简单的编程语言,通常用于教学编译原理。它的语法结构清晰,功能包括常量定义、变量声明、过程(子程序)定义以及基本的控制结构(如条件语句和循环语句)。 PL/0 语法规范 PL/0 是一种教学用的小型编程语言,由 Niklaus Wirth 设计,用于展示编译原理的核…...

JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作
一、上下文切换 即使单核CPU也可以进行多线程执行代码,CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短,所以CPU会不断地切换线程执行,从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...

Android15默认授权浮窗权限
我们经常有那种需求,客户需要定制的apk集成在ROM中,并且默认授予其【显示在其他应用的上层】权限,也就是我们常说的浮窗权限,那么我们就可以通过以下方法在wms、ams等系统服务的systemReady()方法中调用即可实现预置应用默认授权浮…...
python报错No module named ‘tensorflow.keras‘
是由于不同版本的tensorflow下的keras所在的路径不同,结合所安装的tensorflow的目录结构修改from语句即可。 原语句: from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后: from tensorflow.python.keras.lay…...

力扣热题100 k个一组反转链表题解
题目: 代码: func reverseKGroup(head *ListNode, k int) *ListNode {cur : headfor i : 0; i < k; i {if cur nil {return head}cur cur.Next}newHead : reverse(head, cur)head.Next reverseKGroup(cur, k)return newHead }func reverse(start, end *ListNode) *ListN…...
作为测试我们应该关注redis哪些方面
1、功能测试 数据结构操作:验证字符串、列表、哈希、集合和有序的基本操作是否正确 持久化:测试aof和aof持久化机制,确保数据在开启后正确恢复。 事务:检查事务的原子性和回滚机制。 发布订阅:确保消息正确传递。 2、性…...
Qt 事件处理中 return 的深入解析
Qt 事件处理中 return 的深入解析 在 Qt 事件处理中,return 语句的使用是另一个关键概念,它与 event->accept()/event->ignore() 密切相关但作用不同。让我们详细分析一下它们之间的关系和工作原理。 核心区别:不同层级的事件处理 方…...