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

面试热题(复原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;}

  • 判断子串是否合法

最后就是在写一个判断分割是否是有效分割了。

主要考虑到如下三点:

  1. 段位以0为开头的数字不合法
  2. 段位里有非正整数字符不合法
  3. 段位如果大于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 地址 正好由四个整数&#xff08;每个整数位于 0 到 255 之间组成&#xff0c;且不能含有前导 0&#xff09;&#xff0c;整数之间用 . 分隔。 例如&#xff1a;"0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址&#xff0c;但是 "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&#xff1a; 下载Node.js安装程序&#xff1a; 前往Node.js官方网站&#xff08;https://nodejs.org/&#xff09;&#xff0c;在主页上找到"Downloads"&#xff08;下载&#xff09;选项。然后选择适用于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)&#xff0c;uname -r可以看到内核版本是3.10.0-957.21.3.el7.x86_64 yum install stress sysstat -y安装stress和sysstat。 使用pidstat -u 5 1没有%wait项&#xff1a; 原因是CentOS 7仓…...

POI groupRow 折叠分组,折叠部分不显示问题

折叠组是什么&#xff1f;如图就是用POI 实现的&#xff0c;代码很简单&#xff1a;sheet.groupRow(开始行&#xff0c;结束行)即可 但是万万没想到&#xff0c;最终实现出的结果&#xff0c;合并的组&#xff0c;有一部分并没有渲染出来&#xff0c;如下图&#xff1a; 因为我…...

一、数据库基础

数据库 一、数据库基础 1、一些概念 数据库&#xff1a;数据库&#xff08;DataBase &#xff0c;简称DB&#xff09;&#xff0c;就是信息的集合。数据库是由数据库管理系统管理的数据的集合&#xff1b;数据库管理系统&#xff1a;简称DBMS 。是一种操纵和管理数据库的大型…...

Harmony OS教程学习笔记

基础知识 1.如何修改程序启动的第一个页面&#xff1f; 不想使用创建的默认的页面&#xff0c;这时需要修改启动页面&#xff0c;修改的地方在EntryAbility文件中的onWindowStageCreate方法中。 onWindowStageCreate(windowStage: window.WindowStage) {// Main window is cr…...

605. 种花问题

链接 假设有一个很长的花坛&#xff0c;一部分地块种植了花&#xff0c;另一部分却没有。可是&#xff0c;花不能种植在相邻的地块上&#xff0c;它们会争夺水源&#xff0c;两者都会死去。给你一个整数数组 flowerbed 表示花坛&#xff0c;由若干 0 和 1 组成&#xff0c;其中…...

Elasticsearch 常见的简单查询

查看es中有哪些索引 请求方式&#xff1a;GET 请求地址&#xff1a;http://localhost:9200 /_cat/indices?v 参数&#xff1a;无 结果&#xff1a; 查看索引全部数据 请求方式&#xff1a;GET 请求地址&#xff1a;http://localhost:9200/index-2023-08/_search 参数&a…...

C#使用xamarin进行跨平台开发

使用 Xamarin 进行跨平台开发可以使用 C# 和 .NET 平台来开发移动应用程序&#xff0c;同时将代码在多个主要移动操作系统上运行&#xff0c;包括 Android 和 iOS。以下是在 C# 中使用 Xamarin 进行跨平台开发的一般步骤&#xff1a; 安装 Xamarin&#xff1a; 在开始之前&…...

xargs 的用法 在1个文件夹中批量删除文件,这些删除的文件名是另一个文件夹中的文件名。

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

集简云本周新增/更新:新增2大功能,集成2款应用,更新4款应用,新增近20个动作

本周更新概要 新增功能 新增功能&#xff1a;Claude2 新增功能&#xff1a;语聚AI对话助手对话背景设定 应用新增 新增应用&#xff1a;领星ERP 新增应用&#xff1a;slack(自建) 应用更新 更新应用&#xff1a;企业微信(代开发) 更新应用&#xff1a;阿里云效2020(新版…...

MySQL存储过程怎么写?看完这篇秒懂

今天测试一个数据展示模块&#xff0c;依赖于数据部推送数据&#xff0c;但是他们没有人员配合&#xff0c;为了赶工&#xff0c;于是自己徒手造数据&#xff0c;有些页面&#xff0c;要查看翻页和权限等相关的功能&#xff0c;手动造是不可能的&#xff0c;因为我懒....哈哈哈…...

STM32电源名词解释

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

《操作系统真象还原》学习笔记:第七章 中断

由于 CPU 获知了计算机中发生的某些事&#xff0c;CPU 暂停正在执行的程序&#xff0c;转而去执行处理该事件的程序&#xff0c;当这段程序执行完毕后&#xff0c;CPU 继续执行刚才的程序。整个过程称为中断处理&#xff0c;也称为中断。 把中断按事件来源分类&#xff0c;来自…...

【学习笔记之vue】These dependencies were not found:

These dependencies were not found:方案一 全部安装一遍 我们先浅试一个axios >> npm install axios 安装完报错就没有axios了&#xff0c;验证咱们的想法没有问题&#xff0c;实行&#xff01; ok...

【数据结构】实现栈和队列

目录 一、栈1.栈的概念及结构&#xff08;1&#xff09;栈的概念&#xff08;2&#xff09;栈的结构 2.栈的实现&#xff08;1&#xff09;类型和函数的声明&#xff08;2&#xff09;初始化栈&#xff08;3&#xff09;销毁&#xff08;4&#xff09;入栈&#xff08;5&#x…...

APT60DQ20BG-ASEMI新能源功率器件APT60DQ20BG

编辑&#xff1a;ll APT60DQ20BG-ASEMI新能源功率器件APT60DQ20BG 型号&#xff1a;APT60DQ20BG 品牌&#xff1a;ASEMI 封装&#xff1a;TO-3P 恢复时间&#xff1a;&#xff1e;50ns 正向电流&#xff1a;60A 反向耐压&#xff1a;200V 芯片个数&#xff1a;2 引脚数…...

[Android Framework] 系统 ANR 问题排查实践小结

文章目录 背景卡顿的定义:卡顿分类:卡顿原因汇总ANR 出现的原理应用层导致ANR系统导致ANR日志抓取traces.txt 是如何生成的分析思路与验证相关日志分析data/anr/traces.txt其他分析思路如何分析生成的 trace.html 文件呢?最后解决参考:背景 本文记录了工作中遇到的Andorid …...

测试微信模版消息推送

进入“开发接口管理”--“公众平台测试账号”&#xff0c;无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息&#xff1a; 关注测试号&#xff1a;扫二维码关注测试号。 发送模版消息&#xff1a; import requests da…...

树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法

树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作&#xff0c;无需更改相机配置。但是&#xff0c;一…...

(十)学生端搭建

本次旨在将之前的已完成的部分功能进行拼装到学生端&#xff0c;同时完善学生端的构建。本次工作主要包括&#xff1a; 1.学生端整体界面布局 2.模拟考场与部分个人画像流程的串联 3.整体学生端逻辑 一、学生端 在主界面可以选择自己的用户角色 选择学生则进入学生登录界面…...

Admin.Net中的消息通信SignalR解释

定义集线器接口 IOnlineUserHub public interface IOnlineUserHub {/// 在线用户列表Task OnlineUserList(OnlineUserList context);/// 强制下线Task ForceOffline(object context);/// 发布站内消息Task PublicNotice(SysNotice context);/// 接收消息Task ReceiveMessage(…...

遍历 Map 类型集合的方法汇总

1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...

剑指offer20_链表中环的入口节点

链表中环的入口节点 给定一个链表&#xff0c;若其中包含环&#xff0c;则输出环的入口节点。 若其中不包含环&#xff0c;则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...

12.找到字符串中所有字母异位词

&#x1f9e0; 题目解析 题目描述&#xff1a; 给定两个字符串 s 和 p&#xff0c;找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义&#xff1a; 若两个字符串包含的字符种类和出现次数完全相同&#xff0c;顺序无所谓&#xff0c;则互为…...

网络编程(UDP编程)

思维导图 UDP基础编程&#xff08;单播&#xff09; 1.流程图 服务器&#xff1a;短信的接收方 创建套接字 (socket)-----------------------------------------》有手机指定网络信息-----------------------------------------------》有号码绑定套接字 (bind)--------------…...

【Java学习笔记】BigInteger 和 BigDecimal 类

BigInteger 和 BigDecimal 类 二者共有的常见方法 方法功能add加subtract减multiply乘divide除 注意点&#xff1a;传参类型必须是类对象 一、BigInteger 1. 作用&#xff1a;适合保存比较大的整型数 2. 使用说明 创建BigInteger对象 传入字符串 3. 代码示例 import j…...

中医有效性探讨

文章目录 西医是如何发展到以生物化学为药理基础的现代医学&#xff1f;传统医学奠基期&#xff08;远古 - 17 世纪&#xff09;近代医学转型期&#xff08;17 世纪 - 19 世纪末&#xff09;​现代医学成熟期&#xff08;20世纪至今&#xff09; 中医的源远流长和一脉相承远古至…...