当前位置: 首页 > news >正文

算法leetcode|93. 复原 IP 地址(多语言实现)


文章目录

  • 93. 复原 IP 地址:
    • 样例 1:
    • 样例 2:
    • 样例 3:
    • 提示:
  • 分析:
  • 题解:
    • rust:
    • go:
    • c++:
    • python:
    • java:


93. 复原 IP 地址:

有效 IP 地址 正好由四个整数(每个整数位于 0255 之间组成,且不能含有前导 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 地址&#xff1a;样例 1&#xff1a;样例 2&#xff1a;样例 3&#xff1a;提示&#xff1a; 分析&#xff1a;题解&#xff1a;rust&#xff1a;go&#xff1a;c&#xff1a;python&#xff1a;java&#xff1a; 93. 复原 IP 地址&#xff1a; 有效 IP …...

TOGAF—架构(Architecture)项目管理

一、简介 1.1概述 架构(Architecture)项目在本质上通常是复杂的。他们需要适当的项目管理来保持正轨并兑现承诺。本指南适用于负责规划和管理架构(Architecture)项目的人员。我们解释了如何用事实上的方法和标准(如PRINCE2或PMBOK)来补充TOGAF架构开发方法(ADM),以加…...

MVVM前端设计模式的发展与应用

在MVC模式中&#xff0c;随着代码量越来越大&#xff0c;主要用来处理各种逻辑和数据转化的Controller首当其冲&#xff0c;变得非常庞大&#xff0c;MVC的简写变成了Massive-View-Controller&#xff08;意为沉重的Controller&#xff09; 我曾经接手老项目&#xff0c;sprin…...

redis:二、缓存击穿的定义、解决方案(互斥锁、逻辑过期)的优缺点和适用场景、面试回答模板和缓存雪崩

缓存击穿的定义 缓存击穿是一种现象&#xff0c;具体就是某一个数据过期时&#xff0c;恰好有大量的并发请求过来&#xff0c;这些并发的请求可能会瞬间把DB压垮。典型场景就是双十一等抢购活动中&#xff0c;首页广告页面的数据过期&#xff0c;此时刚好大量用户进行请求&…...

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技术可以应用于各种类型的网站和应用程序&#xff0c;特别是对于以下几种场景&#xff0c;CDN的作用尤为明显&#xff1a; 1. 高流量网站&#xff1a;对于流量较大的网站&#xff0c;CDN可以将网站的内容分发到全球各地的节点上&#xff0c;从而分担服务…...

Mysql高可用|索引|事务 | 调优

前言 「作者主页」&#xff1a;雪碧有白泡泡 「个人网站」&#xff1a;雪碧的个人网站 文章目录 前言sql语句的执行顺序关键词连接名字解释sql语句 面试坑点存储引擎MYSQL存储引擎 SQL优化索引索引失效索引的数据结构面试坑点 锁事务四大特性事务的隔离级别MVCC 读写分离面试坑…...

电机驱动开发

最近在搞电机驱动程序&#xff0c;感觉很简单&#xff0c;实际操作却发现里面还有很多猫腻&#xff08;细节&#xff09;。 电机在嵌入式设备中非常常见&#xff0c;例如云台的转动&#xff0c;都是靠电机来驱动的。 电机常见分步进电机、直流电机&#xff0c;相对来说步进电机…...

基于PaddleNLP的深度学习对文本自动添加标点符号(一)

前言 目前以深度学习对文本自动添加标点符号研究很少&#xff0c;已知的开源项目并不多&#xff0c;详细的介绍就更少了&#xff0c;但对文本自动添加标点符号又在古文识别语音识别上有重大应用。 基于此&#xff0c;本文开始讲解基于PaddleNLP的深度学习对文本自动添加标点符号…...

“Java已死、前端已凉”?尊嘟假嘟?

一、为什么会出现“Java已死、前端已凉”的言论 “Java已死、前端已凉”的言论出现&#xff0c;主要是由于以下几个原因&#xff1a; 技术更新迅速&#xff1a;随着互联网技术的发展&#xff0c;新的编程语言和技术不断涌现。Java和前端技术作为广泛应用的技术&#xff0c;面临…...

双向无线功率传输系统MATLAB仿真

微❤关注“电气仔推送”获得资料&#xff08;专享优惠&#xff09; 模型简介&#xff1a; 初级侧转换器通过双向 AC/DC 转换器从电网获取电力&#xff0c;并由直流线电压 Vin 供电&#xff0c;而拾波侧被视为连接到 EV&#xff0c;并由连接到任一存储的单独直流源 Vout 表示或…...

火山引擎DataLeap:助你实现从数据研发1.0到数据研发3.0的跨越

更多技术交流、求职机会&#xff0c;欢迎关注字节跳动数据平台微信公众号&#xff0c;回复【1】进入官方交流群 近日&#xff0c;火山引擎开发者社区 Meetup 第 12 期暨超话数据专场在深圳举办&#xff0c;本次活动主题为“数智化转型背景下的火山引擎大数据技术揭秘 ”&#x…...

DevOps 和人工智能 – 天作之合

如今&#xff0c;人工智能和机器学习无处不在&#xff0c;所以它们开始在 DevOps 领域崭露头角也毫不令人意外。人工智能和机器学习正在通过自动化任务改变 DevOps&#xff0c;并使各企业的软件开发生命周期更高效、更深刻和更安全。我们在 DevOps 趋势中简要讨论过这一问题&am…...

基于主动安全的AIGC数据安全建设

面对AIGC带来的数据安全新问题&#xff0c;是不是就应该一刀切禁止AIGC的研究利用呢&#xff1f;答案是否定的。要发展AIGC&#xff0c;也要主动积极地对AIGC的数据安全进行建设。让AIGC更加安全、可靠的为用户服务。为达到此目的&#xff0c;应该从三个方面来开展AIGC的数据安…...

Java 程序的命令行解释器

前几天我写了一个简单的词法分析器项目&#xff1a;https://github.com/MarchLiu/oliva/tree/main/lora-data-generator 。 通过词法分析快速生成 lora 训练集。在这个过程中&#xff0c;我需要通过命令行参数给这个 java 程序传递一些参数。 这个工作让我想起了一些不好的回忆…...

从事开发近20年,经历过各种技术的转变和进步

1、jsp、javabean、servlet、jdbc。 2、Struts1、hibernate、spring。 3、webwork、ibatis、spring 4、Struts2、mybatis、spring 5、spring mvc &#xff0c;spring全家桶 6、dubbo&#xff0c;disconf 微服务&#xff0c;soa 7、springboot 全家桶 8、docker 9、dock…...

unet v2学习笔记

unet v2介绍&#xff1a; UNet v2开源&#xff01;比UNet显存占用更少、参数更少&#xff0c;猛涨20个mIoU 代码&#xff1a;https://github.com/yaoppeng/U-Net_v2 模型96m。 实际测试&#xff0c;1060显卡&#xff0c;256*256&#xff0c;需要13ms。 速度慢于rvm人脸分割…...

MQ入门—centos 7安装RabbitMQ 安装

三&#xff1a;RabbitMQ 安装 1.环境准备 Linux 的 CentOS 7.x 版本。Xftp 传输安装包到 Linux。Xshell 连接 Linux&#xff0c;进行解压安装。 RabbitMQ安装包 链接&#xff1a;https://pan.baidu.com/s/1ZYVI4YZlvMrj458jakla9A 提取码&#xff1a;dyto xshell安装包 链接&…...

虾皮Shopee商品详情API:电商实时数据获取的关键

随着互联网的普及和电子商务的快速发展&#xff0c;电商行业已经成为全球范围内最具影响力和前景的产业之一。在电商行业中&#xff0c;商品详情API接口是实现快速、准确获取商品信息的关键技术之一。本文将介绍获得虾皮Shopee根据ID取商品详情 API在电商行业里的重要性&#x…...

VUE中的8种常规通信方式

文章目录 1.props传递数据(父向子)2.$emit触发自定义事件&#xff08;子向父&#xff09;3.ref&#xff08;父子&#xff09;4.EventBus&#xff08;兄弟组件&#xff09;5.parent或root&#xff08;兄弟组件&#xff0c;有共同祖辈&#xff09;6.attrs和listeners&#xff08;…...

overleaf 加载pdf格式的矢量图时,visio 图片保存为pdf格式,如何确保pdf页面大小和图片一致

Overleaf支持多种矢量图形格式&#xff0c;其中一些常见的包括&#xff1a; PDF&#xff08;Portable Document Format&#xff09;&#xff1a; PDF是一种常见的矢量图形格式&#xff0c;Overleaf可以直接加载和显示PDF文件。许多绘图工具和LaTeX生成的图形都可以导出为PDF格式…...

西南科技大学数字电子技术实验四(基本触发器逻辑功能测试及FPGA的实现)预习报告

一、计算/设计过程 说明:本实验是验证性实验,计算预测验证结果。是设计性实验一定要从系统指标计算出元件参数过程,越详细越好。用公式输入法完成相关公式内容,不得贴手写图片。(注意:从抽象公式直接得出结果,不得分,页数可根据内容调整) (1)D触发器 特征方程: Q…...

“新程序员”必须学会的8个GPT提问技术 | 抢免费注册DevChat名额

ChatGPT 等大语言模型给人带来惊喜也给人带来了焦虑。惊喜在于它给各种工作带来的提效是肉眼可见的&#xff0c;焦虑在于很多人都担心会被 AI 替代&#xff0c;可能工程师们对此最深有感触。很多工程师已经开始用 GPT 来处理一些手头的开发工作&#xff0c;可能是写脚本&#x…...

Flink系列之:大状态与 Checkpoint 调优

Flink系列之&#xff1a;大状态与 Checkpoint 调优 一、概述二、监控状态和 Checkpoints三、Checkpoint 调优四、RocksDB 调优五、增量 Checkpoint六、RocksDB 或 JVM 堆中的计时器七、RocksDB 内存调优八、容量规划九、压缩十、Task 本地恢复十一、主要&#xff08;分布式存储…...

七轴开源协作机械臂myArm视觉跟踪技术!

引言 ArUco标记是一种基于二维码的标记&#xff0c;可以被用于高效的场景识别和位置跟踪。这些标记的简单性和高效性使其成为机器视觉领域的理想选择&#xff0c;特别是在需要实时和高精度跟踪的场景中。结合机器学习和先进的图像处理技术&#xff0c;使用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文件之间的数据交互

在微信小程序中&#xff0c;WXML负责页面结构的描述&#xff0c;而js文件则负责页面的逻辑处理和数据交互。要实现WXML和js文件之间的数据交互&#xff0c;可以通过以下几种方法&#xff1a; JS传输数据到WXML 数据绑定&#xff1a;在WXML中使用{{}}语法将js文件中的数据绑定…...

计算机网络基础——以太网类型,常见标准和架构

一、标准以太网 标准以太网&#xff08;10Mbit/s&#xff09;通常只定位在网络的接入层&#xff0c;新一代多媒体、影像和数据库产品很容易将10Mbit/s运行的以太网的带宽吞没。10Mbit/s 的以太网可以实现100m距离的连接。 二、快速以太网 数据传输速率为100Mbps 的快速以太网…...

HarmonyOS(二)—— 初识ArkTS开发语言(下)之ArkTS声明式语法和组件化基础

前言&#xff1a; 通过前面ArkTS开发语言&#xff08;上&#xff09;之TypeScript入门以及ArkTS开发语言&#xff08;中&#xff09;之ArkTS的由来和演进俩文我们知道了ArkTS的由来以及演进&#xff0c;知道了ArkTS具备了声明式语法和组件化特性&#xff0c;今天&#xff0c;搭…...

VUE篇之日历组件

1.简单日历组件展示 思路&#xff1a;根据当前月的第一天是星期几&#xff0c;来显示日期 <template><div class"wrap"><el-button click"preMonth">上个月</el-button><el-tag>当前年份{{ curYear }}</el-tag><e…...

幼儿园主题网络图设计原理/奉化seo页面优化外包

输入框自动填充密码即使是type是text也别填充&#xff0c;尝试了 https://developer.mozilla.org/zh-CN/docs/Web/Security/Securing_your_site/Turning_off_form_autocompletion 中设置随机字符但是也没有奏效&#xff0c;然后使用 new-password 奏效 转载于:https://www.cnbl…...

老网站删除做新站会影响收录吗/赣州网站建设

MongoDB 3.0 新增特性一览引言在历经版本号修改&#xff08;2.8版本直接跳到3.0版本&#xff09;和11个rc版本之后&#xff0c;MongoDB3.0于2015年3月3日正式发布。可以毫不夸张的说&#xff0c;该版本的新增特性标志着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、实现***后记*** &#xff1a;内容1、效果展示 应用场景&#xff1a;登录后用户展…...

网上找装修设计师/产品seo基础优化

CSS既是一个美妙的创新也是一个不可错过的机会。它通过把表现和结构分离来改进网页设计的过程。但是&#xff0c;CSS有也许多限制。曾写过CSS的人都知道&#xff0c;做一个最简单的网站时&#xff0c;CSS会有很多重复的地方&#xff0c;导致很多覆盖问题&#xff0c;覆盖应用多…...

黄山做网站公司/com域名注册

一、写在前面作为一名测试&#xff0c;有时候经常会遇到需要录屏记录自己操作&#xff0c;方便后续开发同学定位。以前都是用ScreenToGif来录屏制作成动态图&#xff0c;偶尔的机会看到python也能实现。那就赶紧学习下。二、效果展示三、知识串讲这次要讲的东西可能比较多了&am…...

厦门电商网站开发/营销软件有哪些

豪情豪情 豪情的blog是 http://jikey.cnblogs.com 欢迎加入js学习团队&#xff1a;3643843 运行代码 也没什么技术含量&#xff0c; 主要是return false,阻止打开链接&#xff0c;也可以用 event.preventDefault(); 转载于:https://www.cnblogs.com/jikey/archive/2010/05/28/1…...