剑指 Offer II 087. 复原 IP


comments: true
edit_url: https://github.com/doocs/leetcode/edit/main/lcof2/%E5%89%91%E6%8C%87%20Offer%20II%20087.%20%E5%A4%8D%E5%8E%9F%20IP/README.md

剑指 Offer II 087. 复原 IP

题目描述

给定一个只包含数字的字符串 s ,用以表示一个 IP 地址,返回所有可能从 s 获得的 有效 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 地址。

 

示例 1:

输入:s = "25525511135"
输出:["255.255.11.135","255.255.111.35"]

示例 2:

输入:s = "0000"
输出:["0.0.0.0"]

示例 3:

输入:s = "1111"
输出:["1.1.1.1"]

示例 4:

输入:s = "010010"
输出:["0.10.0.10","0.100.1.0"]

示例 5:

输入:s = "10203040"
输出:["10.20.30.40","102.0.30.40","10.203.0.40"]

 

提示:

  • 0 <= s.length <= 3000
  • s 仅由数字组成

 

注意:本题与主站 93 题相同:https://leetcode.cn/problems/restore-ip-addresses/ 

解法

方法一:DFS

我们定义一个函数 d f s ( i ) dfs(i) dfs(i),表示从字符串 s s s 的第 i i i 位开始,搜索能够组成的 IP 地址列表。

函数 d f s ( i ) dfs(i) dfs(i) 的执行步骤如下:

如果 i i i 大于等于字符串 s s s 的长度,说明已经完成了四段 IP 地址的拼接,判断是否满足四段 IP 地址的要求,如果满足则将当前 I P IP IP 加入答案。

如果 i i i 小于字符串 s s s 的长度,此时还需要拼接 I P IP IP 地址的一段,此时需要确定这一段 I P IP IP 地址的值。如果该值大于 255 255 255,或者当前位置 i i i 0 0 0 i i i 之后的若干位的数值大于 0 0 0,则说明不满足要求,直接返回。否则,将其加入 I P IP IP 地址列表,并继续搜索下一段 I P IP IP 地址。

时间复杂度 O ( n × 3 4 ) O(n \times 3^4) O(n×34),空间复杂度 O ( n ) O(n) O(n)。其中 n n n 为字符串 s s s 的长度。

Python3
class Solution:def restoreIpAddresses(self, s: str) -> List[str]:def check(p):if p[0]=="0":return p=="0"return 0<int(p)<=255n=len(s)res=[]path=[]def dfs(i,j,times): # 枚举边界,以及已经分割添加的个数if times>=3 and len(s[i:])>3:returnif times==4 and not s[i:]:  #保证正好切分四个res.append(".".join(path[:]))return     for j in range(i,n):if check(s[i:j+1]) and times<4:path.append(s[i:j+1])dfs(j+1,j+1,times+1)path.pop()dfs(0,0,0)return res
Java
class Solution {private int n;private String s;private List<String> ans = new ArrayList<>();private List<String> t = new ArrayList<>();public List<String> restoreIpAddresses(String s) {n = s.length();this.s = s;dfs(0);return ans;}private void dfs(int i) {if (i >= n && t.size() == 4) {ans.add(String.join(".", t));return;}if (i >= n || t.size() >= 4) {return;}int x = 0;for (int j = i; j < Math.min(i + 3, n); ++j) {x = x * 10 + s.charAt(j) - '0';if (x > 255 || (s.charAt(i) == '0' && i != j)) {break;}t.add(s.substring(i, j + 1));dfs(j + 1);t.remove(t.size() - 1);}}
}
C++
class Solution {
public:vector<string> restoreIpAddresses(string s) {int n = s.size();vector<string> ans;vector<string> t;function<void(int)> dfs = [&](int i) {if (i >= n && t.size() == 4) {ans.push_back(t[0] + "." + t[1] + "." + t[2] + "." + t[3]);return;}if (i >= n || t.size() >= 4) {return;}int x = 0;for (int j = i; j < min(n, i + 3); ++j) {x = x * 10 + s[j] - '0';if (x > 255 || (j > i && s[i] == '0')) {break;}t.push_back(s.substr(i, j - i + 1));dfs(j + 1);t.pop_back();}};dfs(0);return ans;}
};
Go
func restoreIpAddresses(s string) (ans []string) {n := len(s)t := []string{}var dfs func(int)dfs = func(i int) {if i >= n && len(t) == 4 {ans = append(ans, strings.Join(t, "."))return}if i >= n || len(t) == 4 {return}x := 0for j := i; j < i+3 && j < n; j++ {x = x*10 + int(s[j]-'0')if x > 255 || (j > i && s[i] == '0') {break}t = append(t, s[i:j+1])dfs(j + 1)t = t[:len(t)-1]}}dfs(0)return
}
TypeScript
function restoreIpAddresses(s: string): string[] {const n = s.length;const ans: string[] = [];const t: string[] = [];const dfs = (i: number): void => {if (i >= n && t.length === 4) {ans.push(t.join('.'));return;}if (i >= n || t.length === 4) {return;}let x = 0;for (let j = i; j < i + 3 && j < n; ++j) {x = x * 10 + s[j].charCodeAt(0) - '0'.charCodeAt(0);if (x > 255 || (j > i && s[i] === '0')) {break;}t.push(x.toString());dfs(j + 1);t.pop();}};dfs(0);return ans;
}
C#
public class Solution {private IList<string> ans = new List<string>();private IList<string> t = new List<string>();private int n;private string s;public IList<string> RestoreIpAddresses(string s) {n = s.Length;this.s = s;dfs(0);return ans;}private void dfs(int i) {if (i >= n && t.Count == 4) {ans.Add(string.Join(".", t));return;}if (i >= n || t.Count == 4) {return;}int x = 0;for (int j = i; j < i + 3 && j < n; ++j) {x = x * 10 + (s[j] - '0');if (x > 255 || (j > i && s[i] == '0')) {break;}t.Add(x.ToString());dfs(j + 1);t.RemoveAt(t.Count - 1);}}
}
Swift
class Solution {private var n: Int = 0private var s: String = ""private var ans: [String] = []private var t: [String] = []func restoreIpAddresses(_ s: String) -> [String] {n = s.countself.s = sdfs(0)return ans}private func dfs(_ i: Int) {if i >= n && t.count == 4 {ans.append(t.joined(separator: "."))return}if i >= n || t.count >= 4 {return}var x = 0let chars = Array(s)for j in i..<min(i + 3, n) {x = x * 10 + Int(chars[j].wholeNumberValue!)if x > 255 || (chars[i] == "0" && i != j) {break}t.append(String(chars[i...j]))dfs(j + 1)t.removeLast()}}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/34993.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

How to install cangjie on Linux mint 22.1

概述 仓颉编程语言是一款面向全场景智能的新一代编程语言&#xff0c;主打原生智能化、天生全场景、高性能、强安全。主要应用于鸿蒙原生应用及服务应用等场景中&#xff0c;为开发者提供良好的编程体验。 今天&#xff0c;我们介绍一下仓颉语言在Linux mint 22.1上的安装。 …

杰理可视化SDK-手机三方通话控制

杰理可视化SDK-手机三方通话控制 手机三方通话功能杰理SDK三方通话控制SDK三方通话状态获取SDK三方通话处理 手机三方通话功能是手机常用的功能之一。本篇文章简单介绍了杰理可视化SDK在蓝牙耳机应用中&#xff0c;当手机存在三方通话来电或正在进行三方通话时&#xff0c;蓝牙…

【二分算法】-- 寻找旋转排序数组中的最小值

文章目录 1. 题目2. 题目解析3. 代码 1. 题目 在线oj 2. 题目解析 解法一&#xff1a;暴力查找最小值 时间复杂度&#xff1a;0(N) 解法二&#xff1a;二分查找算法 【二段性】&#xff1a; A~B&#xff1a;nums[i] > nums[i 1] C~D&#xff1a;nums[i] < nums[i…

音视频入门基础:RTCP专题(1)——RTCP官方文档下载

一、引言 实时传输控制协议&#xff08;Real-time Transport Control Protocol或RTP Control Protocol或简写RTCP&#xff09;是实时传输协议&#xff08;RTP&#xff09;的一个姐妹协议。RTCP由《RFC 3550》定义&#xff08;取代废弃的《RFC 1889》&#xff09;。RTP使用一个…

OrioleDB: 新一代PostgreSQL存储引擎

PostgreSQL 12 引入了可插拔式的表存储方法接口&#xff0c;允许为不同的表选择不同的存储机制&#xff0c;例如用于 OLTP 操作的堆表&#xff08;HEAP、默认&#xff09;、用于 OLAP 操作的列式表&#xff08;Citus&#xff09;&#xff0c;以及用于超快速搜索处理的内存表。 …

1.5 Spring Boot项目打包和运行

本文介绍了如何使用Spring Boot进行项目打包和运行。首先&#xff0c;讲解了如何将Spring Boot项目打包为可执行的JAR包&#xff0c;并直接运行&#xff0c;无需部署到外部Web服务器。接着&#xff0c;介绍了如何将项目打包为WAR包&#xff0c;以便部署到Web容器中&#xff0c;…

2.7 滑动窗口专题:串联所有单词的子串

LeetCode 30. 串联所有单词的子串算法对比分析 1. 题目链接 LeetCode 30. 串联所有单词的子串 2. 题目描述 给定一个字符串 s 和一个字符串数组 words&#xff0c;words 中所有单词长度相同。要求找到 s 中所有起始索引&#xff0c;使得从该位置开始的连续子串包含 words 中所…

vue中,watch里,this为undefined的两种解决办法

提示&#xff1a;vue中&#xff0c;watch里&#xff0c;this为undefined的两种解决办法 文章目录 [TOC](文章目录) 前言一、问题二、方法1——使用function函数代替箭头函数()>{}三、方法2——使用that总结 前言 ‌‌‌‌‌尽量使用方法1——使用function函数代替箭头函数()…

uniapp移动端图片比较器组件,仿英伟达官网rtx光追图片比较器功能

组件下载地址&#xff1a;https://ext.dcloud.net.cn/plugin?id22609 已测试h5和微信小程序&#xff0c;理论支持全平台 亮点&#xff1a; 简单易用 使用js计算而不是resize属性&#xff0c;定制化程度更高 组件挂在后可播放指示线动画&#xff0c;提示用户可以拖拽比较图片…

SDL3 游戏开发 Windows 环境搭建

SDL3 游戏开发 Windows 环境搭建 一、准备工作1.1 必备工具与库安装1.1.1 CMake1.1.2 MinGW-w641.1.3 Ninja1.1.4 Git1.1.5 SDL3 及扩展库1.1.6 VSCode 及插件 二、配置VSCode项目并验证环境2.1 创建测试源文件2.2 编写CMakeLists.txt文件和CMakePresets.json2.2.1 使用VSCode的…

【sql靶场】第13、14、17关-post提交报错注入保姆级教程

目录 【sql靶场】第13、14、17关-post提交报错注入保姆级教程 1.知识回顾 1.报错注入深解 2.报错注入格式 3.使用的函数 4.URL 5.核心组成部分 6.数据编码规范 7.请求方法 2.第十三关 1.测试闭合 2.列数测试 3.测试回显 4.爆出数据库名 5.爆出表名 6.爆出字段 …

esxi,vcenter6.0安装指导

前言 esxi6.0安装和esxi6.7步骤基本一样&#xff0c;可参考vmware esxi vcenter6.7安装教程&#xff08;dell&#xff09; 环境依赖以及安装包 esxi6.0安装包vcenter6.0安装不同于6.7&#xff0c;6.5通过导入ova模版安装&#xff0c;需要安装在windows server 2008或者windo…

BigFoot Decursive lua

BigFoot Decursive lua 一键驱散脚本 国际化 ogg语音提示 初始化

2024山东大学计算机复试上机真题

2024山东大学计算机复试上机真题 2024山东大学计算机复试机试真题 历年山东大学计算机复试上机真题 历年山东大学计算机复试机试真题 在线评测&#xff1a;传动门&#xff1a;pgcode.cn 最长递减子序列 题目描述 输入数字 n&#xff0c;和 n 个整数&#xff0c;输出该数字…

【AI News | 20250316】每日AI进展

AI Repos 1、ReActMCP 将网络搜索能力集成到AI助手中的一个MCP服务&#xff1a;ReActMCP Web Search&#xff0c;相当于给AI装了个搜索引擎&#xff0c;可以实时查找最新的内容。它基于Exa API执行基本和高级网络搜索&#xff0c;高级搜索比如限制搜索的网站范围、指定日期范围…

【大模型实战篇】使用GPTQ量化QwQ-32B微调后的推理模型

1. 量化背景 之所以做量化&#xff0c;就是希望在现有的硬件条件下&#xff0c;提升性能。量化能将模型权重从高精度&#xff08;如FP32&#xff09;转换为低精度&#xff08;如INT8/FP16&#xff09;&#xff0c;内存占用可减少50%~75%。低精度运算&#xff08;如INT8&#xf…

Unity 笔记:在EditorWindow中绘制 Sorting Layer

在Unity开发过程中&#xff0c;可能会对旧资源进行批量修改&#xff0c;一个个手动修改费人费事&#xff0c;所以催生出了一堆批量工具。 分享一下在此过程中绘制 Sorting Layer 面板的代码脚本。 示意图&#xff1a; 在 EditorGUI 和 EditorGUILayer 中内置了 SortingLayerF…

idea更新git代码报错No Git Roots

idea更新git代码报错&#xff1a; No Git Roots None of configured Git roots are under Git. The configured directory must have ".git directory in it.但是本地项目里是存在.git文件的&#xff0c;就是突然间不能更新代码了 然后尝试重新拉新项目代码提示: Git i…

失败的面试经历(ʘ̥∧ʘ̥)

一.面向对象的三大特性 1.封装&#xff1a;将对象内部的属性私有化&#xff0c;外部对象不能够直接访问&#xff0c;但是可以提供一些可以使外部对象操作内部属性的方法。 2.继承&#xff1a;类与类之间会有一些相似之处&#xff0c;但也会有一些异处&#xff0c;使得他们与众…

qt加载VeloView工程

接上一篇点云软件配置与编译&#xff0c;使用qt加载需要先完成编译。编译完成后到编译目录下lidarview-superbuild\common-superbuild\lidarview\build 找到CmakeCache.txt&#xff0c;如下是我的编译目录。 使用QT6.5.3加载了CmakeCache.txt&#xff0c;QT5.14还加载不了cmake…