当前位置: 首页 > news >正文

【算法与数据结构】93、LeetCode复原 IP 地址

文章目录

  • 一、题目
  • 二、解法
  • 三、完整代码

所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。

一、题目

在这里插入图片描述

二、解法

  思路分析:参照【算法与数据结构】131、LeetCode分割回文串的思路,需要将IP字符串进行分割,同时要对分割字符串的合法性进行判断。IP字符串一共有四个子串,前三个子串在for循环中找到,最后咋终止条件中判断第四个子串是否合法,如果合法则加入结果数组。
  程序如下

class Solution {
private:vector<string> result;int PointNum = 0;bool isValid(const string& s, int start, int end) {if (start > end) return false;	// start>end的数字不合法if (s[start] == '0' && start!=end) return false;	// 0开头的数字不合法		int num = 0;for (int i = start; i <= end; i++) {if (s[i] < '0' || s[i]>'9') return false;num = num * 10 + (s[i] - '0');if (num > 255) return false;}return true;}void backtracking(string& s, int startIndex) {if (PointNum == 3) {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)) {	// 判断子串是否合法s.insert(s.begin() + i + 1, '.');	// 插入分隔符PointNum++;backtracking(s, i + 2);			// 递归PointNum--;s.erase(s.begin() + i + 1);	// 回溯}else break;			}}
public:vector<string> restoreIpAddresses(string s) {backtracking(s, 0);return result;}
};

复杂度分析:

  • 时间复杂度: O ( 3 4 ) O(3^4) O(34), IP地址一共包含四个子串,相当于递归的深度,每个子串有三种分割方式,因此最终时间复杂度为 O ( 3 4 ) O(3^4) O(34)
  • 空间复杂度: O ( n ) O(n) O(n)

三、完整代码

# include <iostream>
# include <string>
# include <vector>
using namespace std;class Solution {
private:vector<string> result;int PointNum = 0;bool isValid(const string& s, int start, int end) {if (start > end) return false;	// start>end的数字不合法if (s[start] == '0' && start!=end) return false;	// 0开头的数字不合法		int num = 0;for (int i = start; i <= end; i++) {if (s[i] < '0' || s[i]>'9') return false;num = num * 10 + (s[i] - '0');if (num > 255) return false;}return true;}void backtracking(string& s, int startIndex) {if (PointNum == 3) {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)) {	// 判断子串是否合法s.insert(s.begin() + i + 1, '.');	// 插入分隔符PointNum++;backtracking(s, i + 2);			// 递归PointNum--;s.erase(s.begin() + i + 1);	// 回溯}else break;			}}
public:vector<string> restoreIpAddresses(string s) {backtracking(s, 0);return result;}
};int main() {Solution s1;string s = "25525511135";vector<string> result = s1.restoreIpAddresses(s);for (vector<string>::iterator jt = result.begin(); jt != result.end(); jt++) {cout << *jt << endl;}cout << endl;system("pause");return 0;
}

end

相关文章:

【算法与数据结构】93、LeetCode复原 IP 地址

文章目录 一、题目二、解法三、完整代码 所有的LeetCode题解索引&#xff0c;可以看这篇文章——【算法和数据结构】LeetCode题解。 一、题目 二、解法 思路分析&#xff1a;参照【算法与数据结构】131、LeetCode分割回文串的思路&#xff0c;需要将IP字符串进行分割&#xff0…...

uniapp点击图片放大预览

阐述 有些时候我们在用uniapp显示图片时&#xff0c;有的不宜全部显示到屏幕上&#xff0c;uniapp提供了一个非常好用的api。 实现方式如下&#xff1a; <template><view class"content"><image class"logo" src"/static/images/a.…...

Java TreeMap

TreeMap 是一个基于 key 有序的 key value 散列表。 map 根据其键的自然顺序排序&#xff0c;或者根据 map 创建时提供的 Comparator 排序不是线程安全的key 不可以存入null底层是基于红黑树实现的 TreeMap 的类结构图&#xff1a; 实现了 NavigableMap 接口&#xff0c;Na…...

ubuntu 内网源如何搭建 —— 筑梦之路

为什么要搭建内网源&#xff1f; 原因&#xff1a;内网开发环境由于其特定原因不能上外网&#xff0c;所以需要本地环境下的内网源来方便开发人员下载安装软件 搭建建议 单独使用一块磁盘来存放源文件或者单独一个目录下&#xff0c;避免混淆。 环境说明 ubuntu 系统 两张…...

测试用例的设计方法(黑盒)

1.基于需求的设计方法 比如针对网易邮箱进行测试&#xff1a;分为功能相关和非功能相关两大类 但是这么设计的话&#xff0c;有无数多个测试用例&#xff0c;我们现在看到的只是一些大概的测试用例&#xff0c;要想设计具体的测试用例&#xff0c;需要用到下面测试用例的方法…...

Shell编程入门--概念、特性、bash配置文件

目录 一、Shell概念1.定义2.分类和使用场景2.1.分类和切换2.2.使用场景 3.特性3.1.文件描述符与输出重定向3.2.历史命令---history3.3.别名 --alias3.4.命令排序执行3.5.部分快捷键3.6.通配符置换 4.脚本规范5.脚本运行方式5.1.bash脚本执行5.2.bash脚本测试 二、bash配置文件1…...

读书笔记:彼得·德鲁克《认识管理》第14章 工作、做工与员工

一、章节内容概述 虽然工作的历史与人类一样久远&#xff0c;但对工作展开系统研究不过是近百年之内的事&#xff0c;并且“做工”&#xff0c;也就是人从事工作&#xff0c;迄今为止仍很少受到 系统关注。然而我们知道&#xff0c;工作和做工不同&#xff0c;工作是客观的“事…...

diffusers库中stable Diffusion模块的解析

diffusers库中stable Diffusion模块的解析 diffusers中&#xff0c;stable Diffusion v1.5主要由以下几个部分组成 Out[3]: dict_keys([vae, text_encoder, tokenizer, unet, scheduler, safety_checker, feature_extractor])下面给出具体的结构说明。 “text_encoder block…...

智慧城市照明为城市节能降耗提供支持继电器开关钡铼S270

智慧城市照明&#xff1a;为城市节能降耗提供支持——以钡铼技术S270继电器开关为例 随着城市化进程的加速&#xff0c;城市照明系统的需求也日益增长。与此同时&#xff0c;能源消耗和环境污染问题日益严重&#xff0c;使得城市照明的节能减排成为重要议题。智慧城市照明系统…...

固高GTS800控制卡开发数控系统宏程序心得

在对固高GTS800控制卡做数控系统开发时&#xff0c;经过多年的总结与积累&#xff0c;总算是实现了一个数控系统的基本功能。 基本实现宏程序的译码与执行同时执行&#xff0c;虽然不是实时执行&#xff0c;但在充分利用插补缓存区的基础上&#xff0c;实现了相对的实时性。 …...

linux入门---线程池的模拟实现

目录标题 什么是线程池线程的封装准备工作构造函数和析构函数start函数join函数threadname函数完整代码 线程池的实现准备工作构造函数和析构函数push函数pop函数run函数完整的代码 测试代码 什么是线程池 在实现线程池之前我们先了解一下什么是线程池&#xff0c;所谓的池大家…...

jQuery HTML/CSS 参考文档

jQuery HTML/CSS 参考文档 文章目录 应用样式 示例属性方法示例 jQuery HTML/CSS 参考文档 应用样式 addClass( classes ) 方法可用于将定义好的样式表应用于所有匹配的元素上。可以通过空格分隔指定多个类。 示例 以下是一个简单示例&#xff0c;设置了para标签 <p&g…...

QT 布局管理综合实例

通过一个实例基本布局管理&#xff0c;演示QHBoxLayout类、QVBoxLayout类及QGridLayout类效果 本实例共用到四个布局管理器&#xff0c;分别是 LeftLayout、RightLayout、BottomLayout和MainLayout。 在源文件“dialog.cpp”具体代码如下&#xff1a; 运行效果&#xff1a; Se…...

使用 pubsub-js 进行消息发布订阅

npm 包地址 github 包地址 pubsub-js 是一个轻量级的 JavaScript 基于主题的消息订阅发布库 &#xff0c;压缩后小于1b。它具有使用简单、性能高效、支持多平台等优点&#xff0c;可以很好地满足各种需求。 功能特点&#xff1a; 无依赖同步解耦ES3 兼容。pubsub-js 能够在…...

TA Shader基础

渲染管线 概念&#xff1a;GPU绘制物体的时候&#xff0c;标准的&#xff0c;流水线一样的操作 游戏引擎如何绘制物体&#xff1a;CPU提供绘制数据&#xff08;顶点数据&#xff0c;纹理贴图等&#xff09;给GPU&#xff0c;配置渲染管线&#xff08;装载Shader代码到GPU&…...

VScode + opencv(cmake编译) + c++ + win配置教程

1、下载opencv 2、下载CMake 3、下载MinGW 放到一个文件夹中 并解压另外两个文件 4、cmake编译opencv 新建文件夹mingw-build 双击cmake-gui 程序会开始自动生成Makefiles等文件配置&#xff0c;需要耐心等待一段时间。 简单总结下&#xff1a;finish->configuring …...

Vue中的常用指令v-html / v-show / v-if / v-else / v-on / v-bind / v-for / v-model

前言 持续学习总结输出中&#xff0c;Vue中的常用指令v-html / v-show / v-if / v-else / v-on / v-bind / v-for / v-model 概念&#xff1a;指令&#xff08;Directives&#xff09;是Vue提供的带有 v- 前缀 的特殊标签属性。可以提高操作 DOM 的效率。 vue 中的指令按照不…...

ChatGPT 提问技巧

ChatGPT是由 OpenAI 训练的⼀款⼤型语⾔模型&#xff0c;能够和你进⾏任何领域的对话。 它能够⽣成类似于⼈类写作的⽂本。您只需要给出提示或提出问题&#xff0c;它就可以⽣成你想要的东⻄。 在此⻚⾯中&#xff0c;您将找到可与 ChatGPT ⼀起使⽤的各种提示。 只需按照下…...

2023-11-09 LeetCode每日一题(逃离火灾)

2023-11-09每日一题 一、题目编号 2258. 逃离火灾二、题目链接 点击跳转到题目位置 三、题目描述 给你一个下标从 0 开始大小为 m x n 的二维整数数组 grid &#xff0c;它表示一个网格图。每个格子为下面 3 个值之一&#xff1a; 0 表示草地。1 表示着火的格子。2 表示一…...

阿里云-maven私服idea访问私服与组件上传

1.进入aliyun制品仓库 2. 点击 生产库-release进入 根据以上步骤修改本地 m2/setting.xml文件 3.pom.xml文件 点击设置获取url 4. idea发布组件...

数据摄取构建模块简介(预览版)(一)弛

一、语言特性&#xff1a;Java 26 与模式匹配进化 1.1 Java 26 语言级别支持 IDEA 2026.1 EAP 最引人注目的变化之一&#xff0c;就是新增 Java 26 语言级别支持。这意味着开发者可以提前体验和测试即将在 JDK 26 中正式发布的语言特性。 其中最重要的变化是对 JEP 530 的全面支…...

.NET 新特性概览与相关文章索引檀

从 UI 工程师到 AI 应用架构者 13 年前&#xff0c;我的工作是让按钮在 IE6 上对齐&#xff1b; 13 年后&#xff0c;我用 fetch-event-source 订阅大模型的“思维流”&#xff0c;用 OCR 解锁图片中的文字——前端&#xff0c;正在成为 AI 产品的第一道体验防线。 最近&#x…...

2026届毕业生推荐的六大AI科研平台推荐榜单

Ai论文网站排名&#xff08;开题报告、文献综述、降aigc率、降重综合对比&#xff09; TOP1. 千笔AI TOP2. aipasspaper TOP3. 清北论文 TOP4. 豆包 TOP5. kimi TOP6. deepseek 人工智能技术于学术写作领域的运用愈发广泛&#xff0c;其关键价值展现于文献检索、数据整理…...

gitru:一个由 Rust 打造的零依赖 Git 提交信息校验工具雅

一、项目背景与核心价值 1. 解决的核心痛点 Navicat的数据库连接密码并非明文存储&#xff0c;而是通过AES算法加密后写入.ncx格式的XML配置文件中。一旦用户忘记密码&#xff0c;常规方式只能重新配置连接&#xff0c;效率极低。本项目只作为学习研究使用&#xff0c;不做其他…...

GLM-. 全面支持与 Gemini CLI 集成:HagiCode 的多模型进化之路厣

1. 流图&#xff1a;数据的河流 如果把传统的堆叠面积图想象成一块块整齐堆叠的积木&#xff0c;那么流图就像一条蜿蜒流淌的河流&#xff0c;河道的宽窄变化自然流畅&#xff0c;波峰波谷过渡平滑。 它特别适合展示多个类别数据随时间的变化趋势&#xff0c;尤其是当你想强调整…...

别再踩坑了!保姆级教程:用PHPStudy在Win10上搞定Webug4.0靶场(附Navicat连接避坑指南)

别再踩坑了&#xff01;保姆级教程&#xff1a;用PHPStudy在Win10上搞定Webug4.0靶场&#xff08;附Navicat连接避坑指南&#xff09; Webug4.0作为国内知名的Web漏洞练习靶场&#xff0c;是网络安全初学者提升实战能力的绝佳工具。但在Windows 10环境下使用PHPStudy搭建时&…...

nRF52840 BLE 多服务开发中的 NRF_ERROR_NO_MEM 排查与解决实战

问题现象 在基于 nRF5 SDK 的 Heart Rate 示例上添加自定义 LBS&#xff08;LED Button Service&#xff09;私有服务后&#xff0c;程序启动后立即进入 Fatal Error → System Reset 循环&#xff0c;串口反复打印&#xff1a; textapp: ble_lbs_init failed! Error code 0x0…...

时变分位数ΔCoVaR模型代码功能说明

时变动态分位数CoVaR、delta-CoVaR&#xff0c;分位数回归 △CoVaR测度 溢出效应 动态 Adrian2016基于分位数回归方法计算动态条件在险价值。 R语言代码&#xff0c;代码更换数据就能用&#xff0c;需要修改的地方都已标明&#xff0c;并且举例怎么修改 每一行代码都有注释&am…...

Unity新手必看:如何用Input系统实现FPS游戏的键盘鼠标控制(附完整代码)

Unity FPS游戏开发实战&#xff1a;Input系统高级控制与优化技巧 第一次在Unity中尝试制作FPS游戏时&#xff0c;我花了两天时间才让角色不再像喝醉酒一样摇晃行走。键盘和鼠标输入的微妙配合、视角旋转的平滑处理、不同设备间的控制切换——这些看似基础的功能背后藏着许多新手…...

告别简单池化:用PyTorch实现Attention MIL,让模型学会‘聚焦’关键实例

告别简单池化&#xff1a;用PyTorch实现Attention MIL&#xff0c;让模型学会‘聚焦’关键实例 在医学图像分析或文本分类任务中&#xff0c;我们常常遇到这样的场景&#xff1a;单个样本由多个实例组成&#xff08;如病理切片中的多个细胞区域、文档中的多个句子段落&#xff…...