复原 IP 地址(回溯+剪枝)
2023-09-11 14:15:14 时间
力扣地址:力扣
有效 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 仅由数字组成
示例代码:
class Solution(object):
def restore_ip_address(self, s):
res = []
def back_tracing(start, tmp):
if len(tmp) > 4:
return
if start == len(s) and len(tmp) == 4:
res.append('.'.join(tmp))
for i in range(start, len(s)):
# if int(s[start: i+1]) > 255 or s[start] == '0' and len(s[start: i+1]) >= 2: # 等价下述写法
if int(s[start: i+1]) > 255 or (s[start] == '0' and len(s[start: i+1]) >= 2):
return
tmp.append(s[start: i+1])
back_tracing(i+1, tmp)
tmp.pop()
back_tracing(0, [])
return res
s = "25525511135"
s = "0000"
obj = Solution()
res = obj.restore_ip_address(s)
print(res)
思路解析: 【回溯+剪枝】
- 步骤1:先想清楚这种字符串如何取出数字,以便可以通过递归取出所有可能的数字
- 步骤2:在字符串里,截取不同长度的字符,需要s[start:i+1]来取,因为不像纯数字列表,每种情况直接可以拿到[1, 23, 4]
- 步骤3:何时添加到结果?start到终点位置,且也找到了4个数,即添加结果
- 步骤4:剪枝操作:
1.当截取的字符转换为数字后的值大于255,且出现为'06'这样的不合法情况
2.当取的数大于4的时候,不符合IP的格式,直接返回
相关文章
- [Windows 驱动开发] 驱动中获取函数地址
- Windows PE 重定位表编程(枚举重定位地址)
- ubuntu Server 设置主机静态 ip地址
- 计算机网络安全基础知识1:渗透测试,网络连接的核心TCP/IP体系结构,公网,内网,ip地址和端口
- ip2region - 准确率99.9%的ip地址定位库
- 数据结构地址
- 伪造http的ip地址,突破ip限制的投票程序
- 国内外DNS服务器地址列表
- java 获取ip地址和网络接口
- H3C IP 地址格式和表示方法
- Mac帧的源Mac地址在转发过程为什么也会发生变化
- K8s 组件 APIServer 、etcd 等对应的 Pod IP 地址 (监听的 IP 地址) 问题
- Qt 中的二进制兼容策略(简而言之就是地址不能变,剩下的就是让地址不变的技巧)
- 前端技术:vue(Vue项目中-axios设置默认请求地址和请求头)
- 华为eNSP配置Easy-IP(出接口地址方式,多对一)
- GNSS说第(三)讲---最新的GNSS观测数据及精密星历等产品的下载方式及地址
- IPv4地址枯竭,但中国IPv6地址使用率只有0.5%
- TCP/IP具体解释学习笔记——地址解析协议ARP
- google全球ip地址库