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大模型?小白/程序员必看,打消转行所有顾虑
当下人工智能(大模型)领域发展势头迅猛,成为职场人眼中的“新风口”,不少就业者都想抓住这波新兴行业的红利,跻身AI赛道。但很多人卡在了起点——担心自己的专业不对口、过往经历不相关,纠结犹豫迟迟不敢迈…...
Llama-3.2-3B效果体验:Ollama简单操作,产出专业级文案
Llama-3.2-3B效果体验:Ollama简单操作,产出专业级文案 1. 模型概览:小而精的文本生成专家 Llama-3.2-3B是Meta最新推出的轻量级语言模型,在3B参数规模下实现了接近大模型的文本生成质量。经过指令微调优化后,它在多语…...
全能B站资源管理工具:BiliTools让视频下载与管理效率提升90%
全能B站资源管理工具:BiliTools让视频下载与管理效率提升90% 【免费下载链接】BiliTools A cross-platform bilibili toolbox. 跨平台哔哩哔哩工具箱,支持视频、音乐、番剧、课程下载……持续更新 项目地址: https://gitcode.com/GitHub_Trending/bili…...
x265帧内预测实战:从35种模式到MPM优化的效率提升技巧
x265帧内预测深度优化:从35种模式到MPM的工程实践 在视频编码领域,HEVC标准相比前代H.264引入了更复杂的帧内预测机制,其中x265作为开源编码器实现,其帧内预测模块的优化直接影响编码效率。本文将深入剖析x265帧内预测的核心技术…...
OpenClaw硬件监控:nanobot定时报告系统资源使用情况
OpenClaw硬件监控:nanobot定时报告系统资源使用情况 1. 为什么需要自动化硬件监控 去年夏天,我的开发机因为内存泄漏问题突然宕机,导致一个重要的线上演示被迫推迟。当时我就意识到,手动检查系统资源的方式既不及时也不可靠。直…...
巨有科技:银发文旅风口来了!康养旅游这样做才赚
随着老龄化社会加深与全民健康意识提升,康养旅游成为2026年文旅行业最具潜力的风口赛道,银发旅游群体持续壮大,成为文旅市场核心增量。但当下康养旅游普遍存在产品单一、服务不专业、运营不规范、适配性不足等问题,传统观光式旅游…...
从‘调不出来’到‘一次过流片’:折叠共源共栅放大器设计中那些没人告诉你的‘坑’与调试技巧
从‘调不出来’到‘一次过流片’:折叠共源共栅放大器设计中那些没人告诉你的‘坑’与调试技巧 在模拟电路设计的江湖里,折叠共源共栅(Folded Cascode)放大器就像一位身怀绝技却性格古怪的武林高手——性能强悍但极难驯服。许多工…...
Leather Dress Collection惊艳效果:Leather_Romper皮连体衣+户外场景自然光渲染
Leather Dress Collection惊艳效果:Leather_Romper皮连体衣户外场景自然光渲染 1. 项目介绍 Leather Dress Collection 是一个基于Stable Diffusion 1.5的LoRA模型集合,专门用于生成各种皮革服装风格的图像。这个系列由Stable Yogi开发,包含…...
UniApp多主题开发避坑指南:为什么SCSS+Require比Vuex方案更优雅?
UniApp多主题开发实战:SCSS动态加载方案深度解析与性能优化 在移动应用开发领域,主题切换功能已成为提升用户体验的重要环节。UniApp作为跨平台开发框架,如何实现高效、灵活的主题管理一直是开发者关注的焦点。本文将深入探讨基于SCSS变量与动…...
AI短剧的风口来了!无需编程,全程技术支持,助你快速贴牌部署私有化系统
🔥 AI短剧爆火,但你还在因为“没有技术团队”而错失风口? 2024-2025年,AI短剧无疑是内容创业最大的黑马。从AI换脸、AI配音到一键生成剧本,市场的需求呈指数级爆发。 然而,对于大多数手握流量渠道、有客户…...
