leetcode93. 复原 IP 地址(java)
复原 IP 地址
- leetcode93. 复原 IP 地址
- 回溯算法
- 代码演示
- 回溯算法
leetcode93. 复原 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 仅由数字组成
回溯算法
设计递归函数为 void dfs(int idx, int n, List cur),其中 idx 和 n 分别代表当前处理字符串 s 的哪个位置,以及字符串 s 的总长度,而 cur 的则是代表子串部分的具体划分方案
用题目样例 s = “25525511135” 作为 🌰,n 固定为 11,当 idx = 3 时,cur 为s[0…2] = 255,部分的划分方案,cur 可能是 [2,5,5]、[2,55]、[25,5]、[255] 之一,在 cur 的基础上,我们继续爆搜剩余部分,即递归执行 dfs(idx, n, cur),算法会将剩余部分的划分方案添加到 cur 上,我们只需要确保每次追加到 cur 的数值符合要求即可(没有前导零 且 范围在 [0,255]中.
在单次回溯过程中,我们可以将 idx 作为当前划分数字的左端点,通过枚举的形式找到右端点 j.
当 idx = n 代表整个 s 已经处理完成,若此时 cur 恰好有 个元素,说明我们找到了一组合法方案,将其拼接成字符串追加到答案数组中。同时也是由于划分过程中 cur 最多只有 个元素,我们可以用此做简单剪枝。
代码演示
ArrayList<String> ans = new ArrayList<>();char[]cs;public List<String> restoreIpAddresses(String s){if (s == null || s.length() < 4){return new ArrayList<>();}cs = s.toCharArray();dfs(0,new ArrayList<>());return ans;}/*** 回溯算法* @param index* @param cur*/public void dfs(int index,List<Integer>cur){if (index > cs.length){return;}if (index == cs.length){if (cur.size() == 4){StringBuilder sb = new StringBuilder();for (int i = 0;i < 4;i++){sb.append(cur.get(i)).append(".");}ans.add(sb.substring(0,sb.length() - 1));}}else {for (int i = index;i < cs.length;i++){int t = 0;for (int j = index;j <= i;j++){t = t * 10 + (cs[j] - '0');}if (cs[index] == '0' && i != index){break;}if (t > 255){break;}cur.add(t);dfs(i + 1,cur);cur.remove(cur.size() - 1);}}}
回溯算法
leetcode131. 分割回文串
相关文章:
leetcode93. 复原 IP 地址(java)
复原 IP 地址 leetcode93. 复原 IP 地址回溯算法代码演示 回溯算法 leetcode93. 复原 IP 地址 有效 IP 地址 正好由四个整数(每个整数位于 0 到 255 之间组成,且不能含有前导 0),整数之间用 ‘.’ 分隔。 例如:“0.1.2…...
极光Java 版本服务器端实现别名消息推送
文章目录 引言I 概述1.1 依赖包1.2 极光证书环境参数1.3 构建推送对象II 推送内容2.1 配置推送内容2.2 获取通知消息内容2.3 配置IOS通知内容2.4 配置Android通知内容2.5 发起推送2.6 分批推送2.7 初始化密钥2.8 配置密钥引言 REST API 文档:https://docs.jiguang.cn/jpush/se…...
【Lua学习笔记】Lua进阶——Table(4)继承,封装,多态
文章目录 封装继承多态 封装 // 定义基类 Object {}//由于表的特性,该句就相当于定义基类变量 Object.id 1//该句相当于定义方法,Object可以视为定义的对象,Test可以视为方法名 //我们知道Object是一个表,但是抽象地看ÿ…...
Linux中常用的指令
ls ls [选项] [目录或文件] 功能:对于目录,列出该目录下所有的子目录和文件;对于文件,列出该文件的文件名和其他属性 常用选项: -a:列出目录下的所有文件,包括以.开头的隐藏文件 -l:列出文件的详细信息。…...
【java】【面对对象高级4】内部类、枚举、泛型
目录 1、内部类 1.1 成员内部类【了解】 1.1.1 定义 1.1.2 扩展变量 1.2 静态内部类【了解】 1.2.1 定义 1.2.2 扩展变量 1.3 局部内部类【了解】 1.4 匿名内部类【重点】 1.4.1 定义 1.4.1.1 常规写法 1.4.1.2 匿名内部类改造 1.4.2 匿名内部类的常见使用场景 1.4.2…...
Python的用处到底是什么?(三)
11. 数据库操作:Python的库,如sqlite3和SQLAlchemy,可以连接和操作各种类型的数据库。 Python提供了一些库和工具,如sqlite3和SQLAlchemy,用于连接和操作各种类型的数据库。以下是关于这两个库的详细解释:…...
【Nodejs】Express基本使用
Express 中文网 基于 Node.js 平台,快速、开放、极简的 web 开发框架。 1.Express的安装方式 Express的安装可直接使用npm包管理器上的项目,在安装npm之前可先安装淘宝镜像: npm install -g cnpm --registryhttps://registry.npmmirror.com/…...
k8s集群安装v1.20.9
参考网上资料并将异常问题解决,经测试可正常安装集群。 1.我的环境准备 本人使用vmware pro 17新建三个centos7虚拟机,每个2cpu,20GB磁盘存储,内存2GB,其中主节点的内存3GB,可使用外网. 2.所有节点安装D…...
Staples Drop Ship EDI 需求分析
Staples 是一家美国零售公司,总部位于马萨诸塞州弗拉明汉,主要提供支持工作和学习的产品和服务。该公司于 1986 年在马萨诸塞州布莱顿开设了第一家门店。到 1996 年,该公司已跻身《财富》世界 500 强,后来又收购了办公用品公司 Qu…...
模型调参及优化
调参 调权重参数,偏置参数 训练数据集用来训练参数w,b 调超参数 验证数据集用来选择超参数学习率lr,隐藏层大小等 如何调参 当泛化误差和训练误差都没有降下去说明欠拟合;当训练误差降下去,但泛化误差出现上升形式&…...
多数据源数据转换和同步的ETL工具推荐
有许多支持多数据源数据转换和同步的ETL工具可供选择。以下是一些常见的ETL工具和它们支持多数据源数据转换和同步的特点: Apache NiFi:Apache NiFi是一个开源的ETL工具,支持多种数据源的连接,包括文件系统、数据库、消息队列、网…...
配置 gitlab https 访问
文章目录 1. 备份2. 生成SSL证书3. 配置文件4. 重启5. 访问 1. 备份 docker exec -ti gitlab-ce gitlab-rake gitlab:backup:create2. 生成SSL证书 yum install openssl openssl-devel -y mkdir /data/gitlab/config/ssl ; cd /data/gitlab/config/ssl### 生成证书 openssl…...
Kepware Modbus驱动简介
1. Modbus驱动能够解决什么问题? 它是Modbus设备驱动的集合,为用户提供一种方便快捷的Modbus设备数采解决方案。 只需要通过简单的配置就可以将常见的例如Modbus TCP/IP Ethernet、RTU Serial 和 ASCII Serial等协议设备无缝连接到 HMI/SCADA、MES/His…...
从零开始学习CTF——CTF是什么
引言: 从2019年10月开始接触CTF,学习了sql注入、文件包含等web知识点,但都是只知道知识点却实用不上,后来在刷CTF题才发现知识点的使用方法,知道在哪里使用,哪里容易出漏洞,可是在挖src漏洞中还…...
为Android构建现代应用——主体结构
创建Screents和ViewModels 在前面的章节中,我们已经分析了OrderNow项目的理论概念和我们将赋予的组织。 在本章中,我们将开始实现初始结构和模板,这将联接每一个应用程序的部分。 首先将添加以下带有各自视图模型的主屏幕: •…...
【shell脚本】shell脚本之日志切割(进阶实战三)
恭喜你,找到宝藏博主了,这里会分享shell的学习整过程。 shell 对于运维来说是必备技能之一,它可以提高很多运维重复工作,提高效率。 shell的专栏,我会详细地讲解shell的基础和使用,以及一些比较常用的she…...
VMLogin和虚拟机里的浏览器有什么区别?
虚拟机(Virtual Machine)指通过软件模拟的具有完整硬件系统功能的、运行在一个完全隔离环境中的完整计算机系统。 指纹浏览器,也称防关联浏览器。 简单来说,就是允许在同一台电设备上操作和管理多个平台、多个账号,账…...
unimrcp server的session资源分配与回收
unimrcp使用APR的内存池管理内存,因此,处理函数中一般都会传递一个pool指针,需要内存时,就从pool里分配一块,一般也不需要关心内存的释放。因为,一路呼叫关联一个session,一个session对应一个po…...
【图论】三种中心性 —— 特征向量、katz 和 PageRank
维基百科:在图论和网络分析中,中心性指标为图中相应网络位置的节点分配排名或数值。中心性这一概念最初起源于社交网络分析,因此很多衡量中心性的术语也反映了其社会学背景。 不同中心性指标对 “重要” 的衡量方式不同,因此适用于…...
论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)
HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...
【JVM】- 内存结构
引言 JVM:Java Virtual Machine 定义:Java虚拟机,Java二进制字节码的运行环境好处: 一次编写,到处运行自动内存管理,垃圾回收的功能数组下标越界检查(会抛异常,不会覆盖到其他代码…...
服务器硬防的应用场景都有哪些?
服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式,避免服务器受到各种恶意攻击和网络威胁,那么,服务器硬防通常都会应用在哪些场景当中呢? 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...
HTML前端开发:JavaScript 常用事件详解
作为前端开发的核心,JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例: 1. onclick - 点击事件 当元素被单击时触发(左键点击) button.onclick function() {alert("按钮被点击了!&…...
k8s业务程序联调工具-KtConnect
概述 原理 工具作用是建立了一个从本地到集群的单向VPN,根据VPN原理,打通两个内网必然需要借助一个公共中继节点,ktconnect工具巧妙的利用k8s原生的portforward能力,简化了建立连接的过程,apiserver间接起到了中继节…...
2025季度云服务器排行榜
在全球云服务器市场,各厂商的排名和地位并非一成不变,而是由其独特的优势、战略布局和市场适应性共同决定的。以下是根据2025年市场趋势,对主要云服务器厂商在排行榜中占据重要位置的原因和优势进行深度分析: 一、全球“三巨头”…...
算法岗面试经验分享-大模型篇
文章目录 A 基础语言模型A.1 TransformerA.2 Bert B 大语言模型结构B.1 GPTB.2 LLamaB.3 ChatGLMB.4 Qwen C 大语言模型微调C.1 Fine-tuningC.2 Adapter-tuningC.3 Prefix-tuningC.4 P-tuningC.5 LoRA A 基础语言模型 A.1 Transformer (1)资源 论文&a…...
NPOI Excel用OLE对象的形式插入文件附件以及插入图片
static void Main(string[] args) {XlsWithObjData();Console.WriteLine("输出完成"); }static void XlsWithObjData() {// 创建工作簿和单元格,只有HSSFWorkbook,XSSFWorkbook不可以HSSFWorkbook workbook new HSSFWorkbook();HSSFSheet sheet (HSSFSheet)workboo…...
jmeter聚合报告中参数详解
sample、average、min、max、90%line、95%line,99%line、Error错误率、吞吐量Thoughput、KB/sec每秒传输的数据量 sample(样本数) 表示测试中发送的请求数量,即测试执行了多少次请求。 单位,以个或者次数表示。 示例:…...
uni-app学习笔记三十五--扩展组件的安装和使用
由于内置组件不能满足日常开发需要,uniapp官方也提供了众多的扩展组件供我们使用。由于不是内置组件,需要安装才能使用。 一、安装扩展插件 安装方法: 1.访问uniapp官方文档组件部分:组件使用的入门教程 | uni-app官网 点击左侧…...
