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
维基百科:在图论和网络分析中,中心性指标为图中相应网络位置的节点分配排名或数值。中心性这一概念最初起源于社交网络分析,因此很多衡量中心性的术语也反映了其社会学背景。 不同中心性指标对 “重要” 的衡量方式不同,因此适用于…...
MPNet:旋转机械轻量化故障诊断模型详解python代码复现
目录 一、问题背景与挑战 二、MPNet核心架构 2.1 多分支特征融合模块(MBFM) 2.2 残差注意力金字塔模块(RAPM) 2.2.1 空间金字塔注意力(SPA) 2.2.2 金字塔残差块(PRBlock) 2.3 分类器设计 三、关键技术突破 3.1 多尺度特征融合 3.2 轻量化设计策略 3.3 抗噪声…...
vscode里如何用git
打开vs终端执行如下: 1 初始化 Git 仓库(如果尚未初始化) git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...
C++初阶-list的底层
目录 1.std::list实现的所有代码 2.list的简单介绍 2.1实现list的类 2.2_list_iterator的实现 2.2.1_list_iterator实现的原因和好处 2.2.2_list_iterator实现 2.3_list_node的实现 2.3.1. 避免递归的模板依赖 2.3.2. 内存布局一致性 2.3.3. 类型安全的替代方案 2.3.…...
论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)
HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...
从WWDC看苹果产品发展的规律
WWDC 是苹果公司一年一度面向全球开发者的盛会,其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具,对过去十年 WWDC 主题演讲内容进行了系统化分析,形成了这份…...
day52 ResNet18 CBAM
在深度学习的旅程中,我们不断探索如何提升模型的性能。今天,我将分享我在 ResNet18 模型中插入 CBAM(Convolutional Block Attention Module)模块,并采用分阶段微调策略的实践过程。通过这个过程,我不仅提升…...
MFC内存泄露
1、泄露代码示例 void X::SetApplicationBtn() {CMFCRibbonApplicationButton* pBtn GetApplicationButton();// 获取 Ribbon Bar 指针// 创建自定义按钮CCustomRibbonAppButton* pCustomButton new CCustomRibbonAppButton();pCustomButton->SetImage(IDB_BITMAP_Jdp26)…...
Cesium1.95中高性能加载1500个点
一、基本方式: 图标使用.png比.svg性能要好 <template><div id"cesiumContainer"></div><div class"toolbar"><button id"resetButton">重新生成点</button><span id"countDisplay&qu…...
postgresql|数据库|只读用户的创建和删除(备忘)
CREATE USER read_only WITH PASSWORD 密码 -- 连接到xxx数据库 \c xxx -- 授予对xxx数据库的只读权限 GRANT CONNECT ON DATABASE xxx TO read_only; GRANT USAGE ON SCHEMA public TO read_only; GRANT SELECT ON ALL TABLES IN SCHEMA public TO read_only; GRANT EXECUTE O…...
【服务器压力测试】本地PC电脑作为服务器运行时出现卡顿和资源紧张(Windows/Linux)
要让本地PC电脑作为服务器运行时出现卡顿和资源紧张的情况,可以通过以下几种方式模拟或触发: 1. 增加CPU负载 运行大量计算密集型任务,例如: 使用多线程循环执行复杂计算(如数学运算、加密解密等)。运行图…...
