算法leetcode|93. 复原 IP 地址(多语言实现)
文章目录
- 93. 复原 IP 地址:
- 样例 1:
- 样例 2:
- 样例 3:
- 提示:
- 分析:
- 题解:
- rust:
- go:
- c++:
- python:
- java:
93. 复原 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 仅由数字组成
分析:
- 面对这道算法题目,二当家的再次陷入了沉思。
- ip地址大家都是知道的,ipv4是由4段组成,每段的取值范围都是 [0,255]。
- 给出一个ip地址我们都可以判断出是否合法有效,但是现在相当于是反向构建合法有效的ip地址,所以我们就是看字符串有多少种合法ipv4的拆分可能。
- 按照顺序,4段中的每段都可以是1位到3位10进制数,但是不可以有前导0,取值范围是 [0,255]。
- 去尝试所有的可能,看是否恰好拆分成4段有效值,即正好所有的字符都使用了,并且拆分成了4段有效值。
- 祭出深度优先,非常强大的递归套娃大法,更准确地说是回溯算法。
- 注:回溯算法一般需要一个数据结构存储一个临时状态,需要在回溯时还原状态。
题解:
rust:
impl Solution {pub fn restore_ip_addresses(s: String) -> Vec<String> {fn dfs(s: &str, ans: &mut Vec<String>, segments: &mut Vec<String>, seg_start: usize) {// 如果找到了 4 段 IP 地址并且遍历完了字符串,那么就是一种答案if 4 == segments.len() {if seg_start == s.len() {ans.push(segments.join("."));}return;}// 一般情况,枚举每一种可能性并递归for seg_end in seg_start + 1..=s.len() {let segment = &s[seg_start..seg_end];if (segment.starts_with('0') && (seg_end - seg_start) > 1) || segment.parse::<usize>().unwrap() > 0xFF {// 有前导零 或者 地址范围大于255break;}segments.push(segment.to_string());dfs(s, ans, segments, seg_end);segments.pop();}}let mut ans = Vec::new();dfs(s.as_str(), &mut ans, &mut Vec::new(), 0);return ans;}
}
go:
func restoreIpAddresses(s string) []string {var ans []stringvar dfs func([]string, int)dfs = func(segments []string, segStart int) {// 如果找到了 4 段 IP 地址并且遍历完了字符串,那么就是一种答案if 4 == len(segments) {if segStart == len(s) {ans = append(ans, strings.Join(segments, "."))}return}// 一般情况,枚举每一种可能性并递归for segEnd := segStart + 1; segEnd <= len(s); segEnd++ {segment := s[segStart:segEnd]addr, _ := strconv.ParseInt(segment, 10, 0)if (segment[0] == '0' && (segEnd-segStart) > 1) || addr > 0xFF {// 有前导零 或者 地址范围大于255break}dfs(append(segments, segment), segEnd)}}dfs([]string{}, 0)return ans
}
c++:
class Solution {
private:void dfs(const string& s, vector<string>& ans, string segments[], int segIdx, int segStart) {// 如果找到了 4 段 IP 地址并且遍历完了字符串,那么就是一种答案if (4 == segIdx) {if (segStart == s.size()) {string addr;for (int i = 0; i < 4; ++i) {addr += segments[i];if (i != 3) {addr += '.';}}ans.emplace_back(addr);}return;}// 一般情况,枚举每一种可能性并递归for (int segEnd = segStart + 1; segEnd <= s.size(); ++segEnd) {string segment = s.substr(segStart, segEnd - segStart);if ((segment[0] == '0' && (segEnd - segStart) > 1) || stoi(segment) > 0xFF) {// 有前导零 或者 地址范围大于255break;}segments[segIdx] = segment;dfs(s, ans, segments, segIdx + 1, segEnd);}}
public:vector<string> restoreIpAddresses(string s) {vector<string> ans;string segments[4];dfs(s, ans, segments, 0, 0);return ans;}
};
python:
class Solution:def restoreIpAddresses(self, s: str) -> List[str]:ans = list()def dfs(segments: List[str], seg_start: int):# 如果找到了 4 段 IP 地址并且遍历完了字符串,那么就是一种答案if 4 == len(segments):if seg_start == len(s):ans.append(".".join(segments))return# 一般情况,枚举每一种可能性并递归for seg_end in range(seg_start + 1, len(s) + 1):segment = s[seg_start:seg_end]if (segment[0] == '0' and (seg_end - seg_start) > 1) or int(segment) > 0xFF:# 有前导零 或者 地址范围大于255breaksegments.append(segment)dfs(segments, seg_end)segments.pop()dfs(list(), 0)return ans
java:
class Solution {public List<String> restoreIpAddresses(String s) {final List<String> ans = new ArrayList<>();dfs(s, ans, new String[4], 0, 0);return ans;}private void dfs(String s, List<String> ans, String[] segments, int segIdx, int segStart) {// 如果找到了 4 段 IP 地址并且遍历完了字符串,那么就是一种答案if (4 == segIdx) {if (segStart == s.length()) {ans.add(String.join(".", segments));}return;}// 一般情况,枚举每一种可能性并递归for (int segEnd = segStart + 1; segEnd <= s.length(); ++segEnd) {String segment = s.substring(segStart, segEnd);if ((segment.charAt(0) == '0' && (segEnd - segStart) > 1) || Integer.parseInt(segment) > 0xFF) {// 有前导零 或者 地址范围大于255break;}segments[segIdx] = segment;dfs(s, ans, segments, segIdx + 1, segEnd);}}
}
非常感谢你阅读本文~
欢迎【点赞】【收藏】【评论】三连走一波~
放弃不难,但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子:https://le-yi.blog.csdn.net/ 博客原创~
相关文章:
算法leetcode|93. 复原 IP 地址(多语言实现)
文章目录 93. 复原 IP 地址:样例 1:样例 2:样例 3:提示: 分析:题解:rust:go:c:python:java: 93. 复原 IP 地址: 有效 IP …...
TOGAF—架构(Architecture)项目管理
一、简介 1.1概述 架构(Architecture)项目在本质上通常是复杂的。他们需要适当的项目管理来保持正轨并兑现承诺。本指南适用于负责规划和管理架构(Architecture)项目的人员。我们解释了如何用事实上的方法和标准(如PRINCE2或PMBOK)来补充TOGAF架构开发方法(ADM),以加…...
MVVM前端设计模式的发展与应用
在MVC模式中,随着代码量越来越大,主要用来处理各种逻辑和数据转化的Controller首当其冲,变得非常庞大,MVC的简写变成了Massive-View-Controller(意为沉重的Controller) 我曾经接手老项目,sprin…...
redis:二、缓存击穿的定义、解决方案(互斥锁、逻辑过期)的优缺点和适用场景、面试回答模板和缓存雪崩
缓存击穿的定义 缓存击穿是一种现象,具体就是某一个数据过期时,恰好有大量的并发请求过来,这些并发的请求可能会瞬间把DB压垮。典型场景就是双十一等抢购活动中,首页广告页面的数据过期,此时刚好大量用户进行请求&…...
php的Url 安全的base64编码解码类
/*** Url安全的Base64编码方法* author JerryLi* version 20231217*/ final class UrlSafeB64Fun{/*** 编码* param string $sData 原始字符串* return string*/static public function encode(string $sData): string{$aTmp base64_encode($sData);return strtr($aTmp, [>…...
安全CDN有什么作用,安全CDN工作原理是什么?
一、CDN的应用场景 CDN技术可以应用于各种类型的网站和应用程序,特别是对于以下几种场景,CDN的作用尤为明显: 1. 高流量网站:对于流量较大的网站,CDN可以将网站的内容分发到全球各地的节点上,从而分担服务…...
Mysql高可用|索引|事务 | 调优
前言 「作者主页」:雪碧有白泡泡 「个人网站」:雪碧的个人网站 文章目录 前言sql语句的执行顺序关键词连接名字解释sql语句 面试坑点存储引擎MYSQL存储引擎 SQL优化索引索引失效索引的数据结构面试坑点 锁事务四大特性事务的隔离级别MVCC 读写分离面试坑…...
电机驱动开发
最近在搞电机驱动程序,感觉很简单,实际操作却发现里面还有很多猫腻(细节)。 电机在嵌入式设备中非常常见,例如云台的转动,都是靠电机来驱动的。 电机常见分步进电机、直流电机,相对来说步进电机…...
基于PaddleNLP的深度学习对文本自动添加标点符号(一)
前言 目前以深度学习对文本自动添加标点符号研究很少,已知的开源项目并不多,详细的介绍就更少了,但对文本自动添加标点符号又在古文识别语音识别上有重大应用。 基于此,本文开始讲解基于PaddleNLP的深度学习对文本自动添加标点符号…...
“Java已死、前端已凉”?尊嘟假嘟?
一、为什么会出现“Java已死、前端已凉”的言论 “Java已死、前端已凉”的言论出现,主要是由于以下几个原因: 技术更新迅速:随着互联网技术的发展,新的编程语言和技术不断涌现。Java和前端技术作为广泛应用的技术,面临…...
双向无线功率传输系统MATLAB仿真
微❤关注“电气仔推送”获得资料(专享优惠) 模型简介: 初级侧转换器通过双向 AC/DC 转换器从电网获取电力,并由直流线电压 Vin 供电,而拾波侧被视为连接到 EV,并由连接到任一存储的单独直流源 Vout 表示或…...
火山引擎DataLeap:助你实现从数据研发1.0到数据研发3.0的跨越
更多技术交流、求职机会,欢迎关注字节跳动数据平台微信公众号,回复【1】进入官方交流群 近日,火山引擎开发者社区 Meetup 第 12 期暨超话数据专场在深圳举办,本次活动主题为“数智化转型背景下的火山引擎大数据技术揭秘 ”&#x…...
DevOps 和人工智能 – 天作之合
如今,人工智能和机器学习无处不在,所以它们开始在 DevOps 领域崭露头角也毫不令人意外。人工智能和机器学习正在通过自动化任务改变 DevOps,并使各企业的软件开发生命周期更高效、更深刻和更安全。我们在 DevOps 趋势中简要讨论过这一问题&am…...
基于主动安全的AIGC数据安全建设
面对AIGC带来的数据安全新问题,是不是就应该一刀切禁止AIGC的研究利用呢?答案是否定的。要发展AIGC,也要主动积极地对AIGC的数据安全进行建设。让AIGC更加安全、可靠的为用户服务。为达到此目的,应该从三个方面来开展AIGC的数据安…...
Java 程序的命令行解释器
前几天我写了一个简单的词法分析器项目:https://github.com/MarchLiu/oliva/tree/main/lora-data-generator 。 通过词法分析快速生成 lora 训练集。在这个过程中,我需要通过命令行参数给这个 java 程序传递一些参数。 这个工作让我想起了一些不好的回忆…...
从事开发近20年,经历过各种技术的转变和进步
1、jsp、javabean、servlet、jdbc。 2、Struts1、hibernate、spring。 3、webwork、ibatis、spring 4、Struts2、mybatis、spring 5、spring mvc ,spring全家桶 6、dubbo,disconf 微服务,soa 7、springboot 全家桶 8、docker 9、dock…...
unet v2学习笔记
unet v2介绍: UNet v2开源!比UNet显存占用更少、参数更少,猛涨20个mIoU 代码:https://github.com/yaoppeng/U-Net_v2 模型96m。 实际测试,1060显卡,256*256,需要13ms。 速度慢于rvm人脸分割…...
MQ入门—centos 7安装RabbitMQ 安装
三:RabbitMQ 安装 1.环境准备 Linux 的 CentOS 7.x 版本。Xftp 传输安装包到 Linux。Xshell 连接 Linux,进行解压安装。 RabbitMQ安装包 链接:https://pan.baidu.com/s/1ZYVI4YZlvMrj458jakla9A 提取码:dyto xshell安装包 链接&…...
虾皮Shopee商品详情API:电商实时数据获取的关键
随着互联网的普及和电子商务的快速发展,电商行业已经成为全球范围内最具影响力和前景的产业之一。在电商行业中,商品详情API接口是实现快速、准确获取商品信息的关键技术之一。本文将介绍获得虾皮Shopee根据ID取商品详情 API在电商行业里的重要性&#x…...
VUE中的8种常规通信方式
文章目录 1.props传递数据(父向子)2.$emit触发自定义事件(子向父)3.ref(父子)4.EventBus(兄弟组件)5.parent或root(兄弟组件,有共同祖辈)6.attrs和listeners(…...
vscode里如何用git
打开vs终端执行如下: 1 初始化 Git 仓库(如果尚未初始化) git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...
2025年能源电力系统与流体力学国际会议 (EPSFD 2025)
2025年能源电力系统与流体力学国际会议(EPSFD 2025)将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会,EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...
【机器视觉】单目测距——运动结构恢复
ps:图是随便找的,为了凑个封面 前言 在前面对光流法进行进一步改进,希望将2D光流推广至3D场景流时,发现2D转3D过程中存在尺度歧义问题,需要补全摄像头拍摄图像中缺失的深度信息,否则解空间不收敛…...
定时器任务——若依源码分析
分析util包下面的工具类schedule utils: ScheduleUtils 是若依中用于与 Quartz 框架交互的工具类,封装了定时任务的 创建、更新、暂停、删除等核心逻辑。 createScheduleJob createScheduleJob 用于将任务注册到 Quartz,先构建任务的 JobD…...
Neo4j 集群管理:原理、技术与最佳实践深度解析
Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...
Spring AI 入门:Java 开发者的生成式 AI 实践之路
一、Spring AI 简介 在人工智能技术快速迭代的今天,Spring AI 作为 Spring 生态系统的新生力量,正在成为 Java 开发者拥抱生成式 AI 的最佳选择。该框架通过模块化设计实现了与主流 AI 服务(如 OpenAI、Anthropic)的无缝对接&…...
CMake 从 GitHub 下载第三方库并使用
有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...
管理学院权限管理系统开发总结
文章目录 🎓 管理学院权限管理系统开发总结 - 现代化Web应用实践之路📝 项目概述🏗️ 技术架构设计后端技术栈前端技术栈 💡 核心功能特性1. 用户管理模块2. 权限管理系统3. 统计报表功能4. 用户体验优化 🗄️ 数据库设…...
Java + Spring Boot + Mybatis 实现批量插入
在 Java 中使用 Spring Boot 和 MyBatis 实现批量插入可以通过以下步骤完成。这里提供两种常用方法:使用 MyBatis 的 <foreach> 标签和批处理模式(ExecutorType.BATCH)。 方法一:使用 XML 的 <foreach> 标签ÿ…...
MFC 抛体运动模拟:常见问题解决与界面美化
在 MFC 中开发抛体运动模拟程序时,我们常遇到 轨迹残留、无效刷新、视觉单调、物理逻辑瑕疵 等问题。本文将针对这些痛点,详细解析原因并提供解决方案,同时兼顾界面美化,让模拟效果更专业、更高效。 问题一:历史轨迹与小球残影残留 现象 小球运动后,历史位置的 “残影”…...
