面试热题(复原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
中的任何数字。你可以按 任何 顺序返回答案。输入:s = "25525511135" 输出:["255.255.11.135","255.255.111.35"]
分割字符串的方法一般都是用回溯法进行解决,将所有的情况枚举出来,回溯法类似于一个树型结构
- 递归参数
在这些对顺序有要求的回溯中startIndex一定是需要的,因为不能重复分割,记录下一层递归分割的起始位置,本题我们还需要一个变量pointNum,记录添加逗点的数量。
所以代码如下:
List<String> list = new ArrayList<>();int pointNum=0;public List<String> restoreIpAddresses(String s) {if (s == null || s.length() == 0) {return list;}backtracking(s,0,0);return list;}
- 递归终止条件
本题明确要求只会分成4段,所以不能用切割线切到最后作为终止条件,而是分割的段数作为终止条件,pointNum表示逗点数量,pointNum为3说明字符串分成了4段了,然后验证一下第四段是否合法,如果合法就加入到结果集里
代码如下:
if(pointNum==3){//判断最后一个点后面是否合法if (isVaild(s,startIndex,s.length()-1)){list.add(s);}return;}
- 单层搜索的逻辑
在for (int i = startIndex; i < s.size(); i++)循环中 [startIndex, i] 这个区间就是截取的子串,需要判断这个子串是否合法,如果合法就在字符串后面加上符号.表示已经分割,如果不合法就结束本层循环,如图中剪掉的分支:
- 然后就是递归和回溯的过程:
递归调用时,下一层递归的startIndex要从i+2开始(因为需要在字符串中加入了分隔符.),同时记录分割符的数量pointNum 要 +1,回溯的时候,就将刚刚加入的分隔符. 删掉就可以了,pointNum也要-1。
代码如下:
for (int i = startIndex; i <s.length(); i++) {if(isVaild(s,startIndex,i)){//加逗号s=s.substring(0,i+1)+"."+s.substring(i+1);pointNum++;//逗号也占了一个位置,所以是i+2backtracking(s,i+2,pointNum);//回溯s=s.substring(0,i+1)+s.substring(i+2);pointNum--;}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;
}
相关文章:

面试热题(复原ip地址)
有效 IP 地址 正好由四个整数(每个整数位于 0 到 255 之间组成,且不能含有前导 0),整数之间用 . 分隔。 例如:"0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址,但是 "0.011.255.24…...

【JavaSE】Java方法的使用
【本节目标】 1. 掌握方法的定义以及使用 2. 掌握方法传参 3. 掌握方法重载 4. 掌握递归 目录 1.方法概念及使用 1.1什么是方法(method) 1.2 方法定义 1.3 方法调用的执行过程 1.4 实参和形参的关系 2. 方法重载 2.1 为什么需要方法重载 2.2 方法重载概念 3. 递归 3.…...
Node.js 安装和配置(完整详细版)
在Windows上安装和配置Node.js: 下载Node.js安装程序: 前往Node.js官方网站(https://nodejs.org/),在主页上找到"Downloads"(下载)选项。然后选择适用于Windows的"Windows Insta…...
剪枝基础与实战(4):稀疏训练及剪枝效果展示
稀疏训练是通过在损失loss中增加BN的 γ \gamma γ 参数的L1正则,从而让绝大多数通道对应的 γ \gamma γ值趋近与0, 从而使得模型达到稀疏化的效果:...

CentOS 7.6使用yum安装stress,源码安装stree-ng 0.15.06,源码安装sysstat 12.7.2
cat /etc/redhat-release看到操作系统的版本是CentOS Linux release 7.6.1810 (Core),uname -r可以看到内核版本是3.10.0-957.21.3.el7.x86_64 yum install stress sysstat -y安装stress和sysstat。 使用pidstat -u 5 1没有%wait项: 原因是CentOS 7仓…...

POI groupRow 折叠分组,折叠部分不显示问题
折叠组是什么?如图就是用POI 实现的,代码很简单:sheet.groupRow(开始行,结束行)即可 但是万万没想到,最终实现出的结果,合并的组,有一部分并没有渲染出来,如下图: 因为我…...

一、数据库基础
数据库 一、数据库基础 1、一些概念 数据库:数据库(DataBase ,简称DB),就是信息的集合。数据库是由数据库管理系统管理的数据的集合;数据库管理系统:简称DBMS 。是一种操纵和管理数据库的大型…...

Harmony OS教程学习笔记
基础知识 1.如何修改程序启动的第一个页面? 不想使用创建的默认的页面,这时需要修改启动页面,修改的地方在EntryAbility文件中的onWindowStageCreate方法中。 onWindowStageCreate(windowStage: window.WindowStage) {// Main window is cr…...
605. 种花问题
链接 假设有一个很长的花坛,一部分地块种植了花,另一部分却没有。可是,花不能种植在相邻的地块上,它们会争夺水源,两者都会死去。给你一个整数数组 flowerbed 表示花坛,由若干 0 和 1 组成,其中…...

Elasticsearch 常见的简单查询
查看es中有哪些索引 请求方式:GET 请求地址:http://localhost:9200 /_cat/indices?v 参数:无 结果: 查看索引全部数据 请求方式:GET 请求地址:http://localhost:9200/index-2023-08/_search 参数&a…...
C#使用xamarin进行跨平台开发
使用 Xamarin 进行跨平台开发可以使用 C# 和 .NET 平台来开发移动应用程序,同时将代码在多个主要移动操作系统上运行,包括 Android 和 iOS。以下是在 C# 中使用 Xamarin 进行跨平台开发的一般步骤: 安装 Xamarin: 在开始之前&…...

xargs 的用法 在1个文件夹中批量删除文件,这些删除的文件名是另一个文件夹中的文件名。
xargs 的用法 在1个文件夹中批量删除文件,这些删除的文件名是另一个文件夹中的文件名。 1、问题背景 应用场景 1、问题背景 应用场景 在二进制部署docker时,会把docker的所有可执行文件复制到/usr/bin下。 如果说复制过去后,想要反悔&#x…...

集简云本周新增/更新:新增2大功能,集成2款应用,更新4款应用,新增近20个动作
本周更新概要 新增功能 新增功能:Claude2 新增功能:语聚AI对话助手对话背景设定 应用新增 新增应用:领星ERP 新增应用:slack(自建) 应用更新 更新应用:企业微信(代开发) 更新应用:阿里云效2020(新版…...

MySQL存储过程怎么写?看完这篇秒懂
今天测试一个数据展示模块,依赖于数据部推送数据,但是他们没有人员配合,为了赶工,于是自己徒手造数据,有些页面,要查看翻页和权限等相关的功能,手动造是不可能的,因为我懒....哈哈哈…...

STM32电源名词解释
STM32电源架构 常用名词 VCC Ccircuit 表示电路,即接入电路的电压。 VDD Ddevice 表示器件, 即器件内部的工作电压。 VSS Sseries 表示公共连接,通常指电路公共接地端电压。 VDDA Aanalog 表示模拟,是模拟电路部分的电源。主要为…...

《操作系统真象还原》学习笔记:第七章 中断
由于 CPU 获知了计算机中发生的某些事,CPU 暂停正在执行的程序,转而去执行处理该事件的程序,当这段程序执行完毕后,CPU 继续执行刚才的程序。整个过程称为中断处理,也称为中断。 把中断按事件来源分类,来自…...

【学习笔记之vue】These dependencies were not found:
These dependencies were not found:方案一 全部安装一遍 我们先浅试一个axios >> npm install axios 安装完报错就没有axios了,验证咱们的想法没有问题,实行! ok...

【数据结构】实现栈和队列
目录 一、栈1.栈的概念及结构(1)栈的概念(2)栈的结构 2.栈的实现(1)类型和函数的声明(2)初始化栈(3)销毁(4)入栈(5&#x…...

APT60DQ20BG-ASEMI新能源功率器件APT60DQ20BG
编辑:ll APT60DQ20BG-ASEMI新能源功率器件APT60DQ20BG 型号:APT60DQ20BG 品牌:ASEMI 封装:TO-3P 恢复时间:>50ns 正向电流:60A 反向耐压:200V 芯片个数:2 引脚数…...
[Android Framework] 系统 ANR 问题排查实践小结
文章目录 背景卡顿的定义:卡顿分类:卡顿原因汇总ANR 出现的原理应用层导致ANR系统导致ANR日志抓取traces.txt 是如何生成的分析思路与验证相关日志分析data/anr/traces.txt其他分析思路如何分析生成的 trace.html 文件呢?最后解决参考:背景 本文记录了工作中遇到的Andorid …...

国防科技大学计算机基础课程笔记02信息编码
1.机内码和国标码 国标码就是我们非常熟悉的这个GB2312,但是因为都是16进制,因此这个了16进制的数据既可以翻译成为这个机器码,也可以翻译成为这个国标码,所以这个时候很容易会出现这个歧义的情况; 因此,我们的这个国…...

TDengine 快速体验(Docker 镜像方式)
简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能,本节首先介绍如何通过 Docker 快速体验 TDengine,然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker,请使用 安装包的方式快…...

基于当前项目通过npm包形式暴露公共组件
1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹,并新增内容 3.创建package文件夹...

Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具
文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...

NLP学习路线图(二十三):长短期记忆网络(LSTM)
在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...

R语言速释制剂QBD解决方案之三
本文是《Quality by Design for ANDAs: An Example for Immediate-Release Dosage Forms》第一个处方的R语言解决方案。 第一个处方研究评估原料药粒径分布、MCC/Lactose比例、崩解剂用量对制剂CQAs的影响。 第二处方研究用于理解颗粒外加硬脂酸镁和滑石粉对片剂质量和可生产…...

[大语言模型]在个人电脑上部署ollama 并进行管理,最后配置AI程序开发助手.
ollama官网: 下载 https://ollama.com/ 安装 查看可以使用的模型 https://ollama.com/search 例如 https://ollama.com/library/deepseek-r1/tags # deepseek-r1:7bollama pull deepseek-r1:7b改token数量为409622 16384 ollama命令说明 ollama serve #:…...

day36-多路IO复用
一、基本概念 (服务器多客户端模型) 定义:单线程或单进程同时监测若干个文件描述符是否可以执行IO操作的能力 作用:应用程序通常需要处理来自多条事件流中的事件,比如我现在用的电脑,需要同时处理键盘鼠标…...

Python 实现 Web 静态服务器(HTTP 协议)
目录 一、在本地启动 HTTP 服务器1. Windows 下安装 node.js1)下载安装包2)配置环境变量3)安装镜像4)node.js 的常用命令 2. 安装 http-server 服务3. 使用 http-server 开启服务1)使用 http-server2)详解 …...
小木的算法日记-多叉树的递归/层序遍历
🌲 从二叉树到森林:一文彻底搞懂多叉树遍历的艺术 🚀 引言 你好,未来的算法大神! 在数据结构的世界里,“树”无疑是最核心、最迷人的概念之一。我们中的大多数人都是从 二叉树 开始入门的,它…...