当前位置: 首页 > 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发布组件...

现在不掌握MoE,半年后将无法参与主流大模型迭代——2026奇点大会技术白皮书核心结论首发

第一章&#xff1a;MoE架构&#xff1a;大模型演进的奇点分水岭 2026奇点智能技术大会(https://ml-summit.org) 混合专家&#xff08;Mixture of Experts, MoE&#xff09;并非新概念&#xff0c;但其在大语言模型中的规模化落地&#xff0c;标志着参数增长范式从“全参激活”…...

辛顿 | 我习惯了房间里只有我一个人是对的

注&#xff1a;本文为 “辛顿 | 智者历程” 相关合辑。 略作重排&#xff0c;如有内容异常&#xff0c;请看原文。 X 热点&#xff5c;30 年冷板凳&#xff0c;诺贝尔物理学奖得主 Hinton 的 AI 往事 原创 Rika 适道 2024 年 10 月 9 日 11:13 北京 作者&#xff1a;Rika 编辑…...

基于非支配排序遗传算法NSGAII的综合能源优化调度附Matlab代码

✅作者简介&#xff1a;热爱科研的Matlab仿真开发者&#xff0c;擅长数据处理、建模仿真、程序设计、完整代码获取、论文复现及科研仿真。&#x1f34e; 往期回顾关注个人主页&#xff1a;Matlab科研工作室&#x1f34a;个人信条&#xff1a;格物致知,完整Matlab代码及仿真咨询…...

电子电路中的“心脏”:电源匕

前言 Kubernetes 本身并不复杂&#xff0c;是我们把它搞复杂的。无论是刻意为之还是那种虽然出于好意却将优雅的原语堆砌成 鲁布戈德堡机械 的狂热。平台最初提供的 ReplicaSets、Services、ConfigMaps&#xff0c;这些基础组件简单直接&#xff0c;甚至显得有些枯燥。但后来我…...

【架构实战】SQL调优实战:从执行计划到索引优化

一、为什么需要SQL调优 在应用开发中&#xff0c;SQL性能直接影响系统响应速度&#xff1a; 慢SQL的影响&#xff1a; 页面加载缓慢&#xff0c;用户体验差数据库CPU使用率飙升连接池耗尽&#xff0c;应用不可用甚至引发连锁故障 调优的目标&#xff1a; 查询时间从秒级降到毫秒…...

【大模型上线前必过隐私审计关】:7类高危数据场景识别表+3套自动化检测脚本(附开源工具链)

第一章&#xff1a;大模型工程化中的数据隐私保护 2026奇点智能技术大会(https://ml-summit.org) 在大模型工程化落地过程中&#xff0c;原始训练数据、微调语料及推理输入往往蕴含敏感个人信息、企业专有知识或受监管的行业数据。若缺乏系统性隐私防护机制&#xff0c;模型可…...

镜像视界空间智能体系统的核心原理是否涉及人工智能技术?

一句话结论涉及人工智能&#xff0c;但本质不是AI系统。我们的核心是空间计算系统&#xff0c;AI只是其中一个工具层。&#x1f9e0; 分层拆解1️⃣ 底层&#xff1a;不是AI ——是空间几何计算系统最核心的能力是&#xff1a;空间反演&#xff08;Pixel → World&#xff09;多…...

不只是部署:在 Windows 11 上用 Conda 玩转 KTransformers,深入对比 GGUF 与 Safetensors 模型加载的实战差异

在 Windows 11 上用 Conda 玩转 KTransformers&#xff1a;GGUF 与 Safetensors 模型加载的深度实战指南 当你已经成功在 Windows 11 上通过 Conda 环境部署了 KTransformers&#xff0c;接下来的问题往往是&#xff1a;如何根据不同的模型格式和硬件条件&#xff0c;选择最优的…...

别再乱删DLL了!深入解析PyInstaller打包Pyside2的依赖树与正确瘦身姿势

别再乱删DLL了&#xff01;深入解析PyInstaller打包Pyside2的依赖树与正确瘦身姿势 每次看到开发者手动删除PyInstaller打包生成的DLL文件时&#xff0c;我都忍不住想喊停。上周又遇到一个典型案例&#xff1a;某团队为了减少安装包体积&#xff0c;删除了Qt5Core.dll等"看…...

还在手戳像素点选性别?带你避开 HTML 表单 `<input>` 与 `<label>` 的核心大坑(附源码)

表单是用户与数据库交互的唯一大门!黑客想要搞 SQL 注入、XSS 跨站脚本攻击,第一步就是盯上你的输入框。而在审查很多新人的代码时,我不仅经常看到安全隐患,更看到了极其反人类的交互体验——比如让你注册账号时,性别单选框小到要拿显微镜去点! 今天,就从底层逻辑出发,…...