算法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(…...
overleaf 加载pdf格式的矢量图时,visio 图片保存为pdf格式,如何确保pdf页面大小和图片一致
Overleaf支持多种矢量图形格式,其中一些常见的包括: PDF(Portable Document Format): PDF是一种常见的矢量图形格式,Overleaf可以直接加载和显示PDF文件。许多绘图工具和LaTeX生成的图形都可以导出为PDF格式…...
西南科技大学数字电子技术实验四(基本触发器逻辑功能测试及FPGA的实现)预习报告
一、计算/设计过程 说明:本实验是验证性实验,计算预测验证结果。是设计性实验一定要从系统指标计算出元件参数过程,越详细越好。用公式输入法完成相关公式内容,不得贴手写图片。(注意:从抽象公式直接得出结果,不得分,页数可根据内容调整) (1)D触发器 特征方程: Q…...
“新程序员”必须学会的8个GPT提问技术 | 抢免费注册DevChat名额
ChatGPT 等大语言模型给人带来惊喜也给人带来了焦虑。惊喜在于它给各种工作带来的提效是肉眼可见的,焦虑在于很多人都担心会被 AI 替代,可能工程师们对此最深有感触。很多工程师已经开始用 GPT 来处理一些手头的开发工作,可能是写脚本&#x…...
Flink系列之:大状态与 Checkpoint 调优
Flink系列之:大状态与 Checkpoint 调优 一、概述二、监控状态和 Checkpoints三、Checkpoint 调优四、RocksDB 调优五、增量 Checkpoint六、RocksDB 或 JVM 堆中的计时器七、RocksDB 内存调优八、容量规划九、压缩十、Task 本地恢复十一、主要(分布式存储…...
七轴开源协作机械臂myArm视觉跟踪技术!
引言 ArUco标记是一种基于二维码的标记,可以被用于高效的场景识别和位置跟踪。这些标记的简单性和高效性使其成为机器视觉领域的理想选择,特别是在需要实时和高精度跟踪的场景中。结合机器学习和先进的图像处理技术,使用ArUco标记的机械臂系统…...
etcd初探
官方网站 https://etcd.io/ etcd是什么 etcd is a strongly consistent, distributed key-value store that provides a reliable way to store data that needs to be accessed by a distributed system or cluster of machines. It gracefully handles leader elections du…...
微信小程序如何实现WXML和js文件之间的数据交互
在微信小程序中,WXML负责页面结构的描述,而js文件则负责页面的逻辑处理和数据交互。要实现WXML和js文件之间的数据交互,可以通过以下几种方法: JS传输数据到WXML 数据绑定:在WXML中使用{{}}语法将js文件中的数据绑定…...
计算机网络基础——以太网类型,常见标准和架构
一、标准以太网 标准以太网(10Mbit/s)通常只定位在网络的接入层,新一代多媒体、影像和数据库产品很容易将10Mbit/s运行的以太网的带宽吞没。10Mbit/s 的以太网可以实现100m距离的连接。 二、快速以太网 数据传输速率为100Mbps 的快速以太网…...
HarmonyOS(二)—— 初识ArkTS开发语言(下)之ArkTS声明式语法和组件化基础
前言: 通过前面ArkTS开发语言(上)之TypeScript入门以及ArkTS开发语言(中)之ArkTS的由来和演进俩文我们知道了ArkTS的由来以及演进,知道了ArkTS具备了声明式语法和组件化特性,今天,搭…...
VUE篇之日历组件
1.简单日历组件展示 思路:根据当前月的第一天是星期几,来显示日期 <template><div class"wrap"><el-button click"preMonth">上个月</el-button><el-tag>当前年份{{ curYear }}</el-tag><e…...
幼儿园主题网络图设计原理/奉化seo页面优化外包
输入框自动填充密码即使是type是text也别填充,尝试了 https://developer.mozilla.org/zh-CN/docs/Web/Security/Securing_your_site/Turning_off_form_autocompletion 中设置随机字符但是也没有奏效,然后使用 new-password 奏效 转载于:https://www.cnbl…...
老网站删除做新站会影响收录吗/赣州网站建设
MongoDB 3.0 新增特性一览引言在历经版本号修改(2.8版本直接跳到3.0版本)和11个rc版本之后,MongoDB3.0于2015年3月3日正式发布。可以毫不夸张的说,该版本的新增特性标志着MongoDB这款典型的NoSQL数据库已经进入了一个全新的发展阶…...
网页优化与网站优/南昌seo快速排名
element-ui_dropdown-下拉菜单目录文章目录1、效果展示2、下拉菜单相关组件2.1、el-dropdown 下拉菜单2.2、el-dropdown-menu 下拉列表3.3、el-dropdown-item 下拉菜单项3、头像组件_el-avatar4、实现***后记*** :内容1、效果展示 应用场景:登录后用户展…...
网上找装修设计师/产品seo基础优化
CSS既是一个美妙的创新也是一个不可错过的机会。它通过把表现和结构分离来改进网页设计的过程。但是,CSS有也许多限制。曾写过CSS的人都知道,做一个最简单的网站时,CSS会有很多重复的地方,导致很多覆盖问题,覆盖应用多…...
黄山做网站公司/com域名注册
一、写在前面作为一名测试,有时候经常会遇到需要录屏记录自己操作,方便后续开发同学定位。以前都是用ScreenToGif来录屏制作成动态图,偶尔的机会看到python也能实现。那就赶紧学习下。二、效果展示三、知识串讲这次要讲的东西可能比较多了&am…...
厦门电商网站开发/营销软件有哪些
豪情豪情 豪情的blog是 http://jikey.cnblogs.com 欢迎加入js学习团队:3643843 运行代码 也没什么技术含量, 主要是return false,阻止打开链接,也可以用 event.preventDefault(); 转载于:https://www.cnblogs.com/jikey/archive/2010/05/28/1…...