当前位置: 首页 > 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;…...

React Native 导航系统实战(React Navigation)

导航系统实战&#xff08;React Navigation&#xff09; React Navigation 是 React Native 应用中最常用的导航库之一&#xff0c;它提供了多种导航模式&#xff0c;如堆栈导航&#xff08;Stack Navigator&#xff09;、标签导航&#xff08;Tab Navigator&#xff09;和抽屉…...

Zustand 状态管理库:极简而强大的解决方案

Zustand 是一个轻量级、快速和可扩展的状态管理库&#xff0c;特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...

剑指offer20_链表中环的入口节点

链表中环的入口节点 给定一个链表&#xff0c;若其中包含环&#xff0c;则输出环的入口节点。 若其中不包含环&#xff0c;则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...

【论文笔记】若干矿井粉尘检测算法概述

总的来说&#xff0c;传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度&#xff0c;通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...

2025盘古石杯决赛【手机取证】

前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来&#xff0c;实在找不到&#xff0c;希望有大佬教一下我。 还有就会议时间&#xff0c;我感觉不是图片时间&#xff0c;因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...

12.找到字符串中所有字母异位词

&#x1f9e0; 题目解析 题目描述&#xff1a; 给定两个字符串 s 和 p&#xff0c;找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义&#xff1a; 若两个字符串包含的字符种类和出现次数完全相同&#xff0c;顺序无所谓&#xff0c;则互为…...

HTML前端开发:JavaScript 常用事件详解

作为前端开发的核心&#xff0c;JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例&#xff1a; 1. onclick - 点击事件 当元素被单击时触发&#xff08;左键点击&#xff09; button.onclick function() {alert("按钮被点击了&#xff01;&…...

JVM虚拟机:内存结构、垃圾回收、性能优化

1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...

【从零学习JVM|第三篇】类的生命周期(高频面试题)

前言&#xff1a; 在Java编程中&#xff0c;类的生命周期是指类从被加载到内存中开始&#xff0c;到被卸载出内存为止的整个过程。了解类的生命周期对于理解Java程序的运行机制以及性能优化非常重要。本文会深入探寻类的生命周期&#xff0c;让读者对此有深刻印象。 目录 ​…...

基于IDIG-GAN的小样本电机轴承故障诊断

目录 🔍 核心问题 一、IDIG-GAN模型原理 1. 整体架构 2. 核心创新点 (1) ​梯度归一化(Gradient Normalization)​​ (2) ​判别器梯度间隙正则化(Discriminator Gradient Gap Regularization)​​ (3) ​自注意力机制(Self-Attention)​​ 3. 完整损失函数 二…...