算法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(…...
React 第五十五节 Router 中 useAsyncError的使用详解
前言 useAsyncError 是 React Router v6.4 引入的一个钩子,用于处理异步操作(如数据加载)中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误:捕获在 loader 或 action 中发生的异步错误替…...

dedecms 织梦自定义表单留言增加ajax验证码功能
增加ajax功能模块,用户不点击提交按钮,只要输入框失去焦点,就会提前提示验证码是否正确。 一,模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...

基于当前项目通过npm包形式暴露公共组件
1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹,并新增内容 3.创建package文件夹...
Java - Mysql数据类型对应
Mysql数据类型java数据类型备注整型INT/INTEGERint / java.lang.Integer–BIGINTlong/java.lang.Long–––浮点型FLOATfloat/java.lang.FloatDOUBLEdouble/java.lang.Double–DECIMAL/NUMERICjava.math.BigDecimal字符串型CHARjava.lang.String固定长度字符串VARCHARjava.lang…...
【Go】3、Go语言进阶与依赖管理
前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课,做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程,它的核心机制是 Goroutine 协程、Channel 通道,并基于CSP(Communicating Sequential Processes࿰…...

C++ 求圆面积的程序(Program to find area of a circle)
给定半径r,求圆的面积。圆的面积应精确到小数点后5位。 例子: 输入:r 5 输出:78.53982 解释:由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982,因为我们只保留小数点后 5 位数字。 输…...

【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)
骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术,它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton):由层级结构的骨头组成,类似于人体骨骼蒙皮 (Mesh Skinning):将模型网格顶点绑定到骨骼上,使骨骼移动…...

ios苹果系统,js 滑动屏幕、锚定无效
现象:window.addEventListener监听touch无效,划不动屏幕,但是代码逻辑都有执行到。 scrollIntoView也无效。 原因:这是因为 iOS 的触摸事件处理机制和 touch-action: none 的设置有关。ios有太多得交互动作,从而会影响…...

Maven 概述、安装、配置、仓库、私服详解
目录 1、Maven 概述 1.1 Maven 的定义 1.2 Maven 解决的问题 1.3 Maven 的核心特性与优势 2、Maven 安装 2.1 下载 Maven 2.2 安装配置 Maven 2.3 测试安装 2.4 修改 Maven 本地仓库的默认路径 3、Maven 配置 3.1 配置本地仓库 3.2 配置 JDK 3.3 IDEA 配置本地 Ma…...

华硕a豆14 Air香氛版,美学与科技的馨香融合
在快节奏的现代生活中,我们渴望一个能激发创想、愉悦感官的工作与生活伙伴,它不仅是冰冷的科技工具,更能触动我们内心深处的细腻情感。正是在这样的期许下,华硕a豆14 Air香氛版翩然而至,它以一种前所未有的方式&#x…...