python 输入字符串生成所有有效的IP地址(LeetCode 93号题)

这题的官方难度是Medium,点赞1296,反对505,通过率35.4%。从各项指标来说看起来有些中规中矩,实际上也的确如此。这道题的解法和立意都有些显得新意不足,但总体来说题目的质量还是可以的,值得一做。

题意

给定一个由数字组成的字符串,我们希望通过这个字符串得到所有有效ip地址的组合。对于一个有效的ip地址而言,它应该有4个数字组成,每一个数字的范围在0到255之间。

一个字符串可能可以转化成多个ip地址,我们需要存储下来所有可以成立的情况。

样例

Input: "25525511135"
Output: ["255.255.11.135", "255.255.111.35"]

题解

这道题的题意蛮新颖的,将字符串和ip地址结合在了一起,但是题目的内核说实话有些老生常谈了,都是那种将一个大局面转化成若干个小局面之和的情况。

我们之前做的全排列问题、八皇后问题等等都是这种,拿八皇后问题举例,看起来是我们要在棋盘上放置皇后。但实际上我们最终想要的结果是放置好了八个皇后之后的局面,这个局面是由放置了每一个皇后之后的小局面组合在一起构成的。所以本质上也可以看成是小局面组装成大局面的问题。

说了这么多,其实只为了说明一点,就是遇到这些大局面拆分小局面的问题,我们可以率先考虑搜索算法。搜索算法除了可以理解成在一个搜索空间或者是一棵搜索树当中寻找到解之外,也可以理解成可以用来寻找一些小局面的组合,让它们组合起来可以构成我们想要的大局面。

套用到这道题上来,很显然最后我们想要的大局面是合法的IP地址,而构成这个大局面的小局面则是构成IP地址的每一个数字。

这些都搞明白了之后,代码就很好写了:

class Solution:
  def restoreIpAddresses(self, s: str) -> List[str]:
    n = len(s)
    if n < 4 or n > 12:
      return []

    ret = []

    def dfs(cur, ips):
      # 如果递归结束,并且ips当中刚好存了4个ip
      # 则生成答案
      if cur >= n:
        if len(ips) == 4:
          ret.append('.'.join(ips[:]))
        return

      # 遍历下一个ip是几位
      for i in range(cur, min(cur+3, n)):
        # 如果超过1位但是第一位是0,那么非法
        if s[cur] == '0' and i > cur:
          return
        # ip必须小于等于255
        num = int(s[cur: i+1])
        if num > 255:
          return

        # 回溯
        ips.append(s[cur: i+1])
        dfs(i+1, ips)
        ips.pop()

    dfs(0, [])
    return ret

总结

有些新意但是思路中规中矩的搜索问题,熟悉dfs和回溯的话不会很难。

今天的文章到这里就结束了,如果喜欢本文的话,请来一波素质三连,给我一点支持吧(关注、转发、点赞)。

以上就是python 输入字符串生成所有有效的IP地址(LeetCode 93号题)的详细内容,更多关于python 生成IP地址的资料请关注我们其它相关文章!

时间: 2020-10-14

基于Python把网站域名解析成ip地址

起因 因为一些事情,需要将域名解析为ip地址,想到Python作为万能语言,就用Python来实现这个功能 代码 import socket url = 'shiyixirui.cn' res = socket.getaddrinfo(url, None) print(res) ip = res[0][4][0] print(ip) 结果 以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们.

Python django框架应用中实现获取访问者ip地址示例

本文实例讲述了Python django框架应用中实现获取访问者ip地址.分享给大家供大家参考,具体如下: 在django官方文档中有一段对request.META的解释: HttpRequest.META A standard Python dictionary containing all available HTTP headers. Available headers depend on the client and server, but here are some examples:

Python中IP地址处理IPy模块的方法

安装 先下载源码,地址:ps://pypi.python.org/pypi/IPy/">https://pypi.python.org/pypi/IPy/ ,然后解压后使用命令python setup.py install安装. 使用 1.显示IP类型 >>> IP('192.168.1.1').version() 4 >>> IP('::1').version() 6 类似如上所示,通过version方法可以的判断输入的IP是IPv4还是IPv6 .

python实现ip地址的包含关系判断

python的IPy模块虽然可以实现一些ip地址的判断,但是不是很完美,有些场景根本判断不出来,还会抛出异常,比如一个地址范围和一个ip/掩码,这种不同类型就无法判断. 对此通过自己写函数来实现ip地址的判断,实现的思路很简单,先把ip地址转换为一个十进制的范围数,然后来判断是否有包含关系. #下面函数可以将ip转换为十进制数 def iptoint(self,ip): try: h=[] s = ip.split('.') for temp in s: a=bin(int(temp))[2:]

Python实现通过解析域名获取ip地址的方法分析

本文实例讲述了Python实现通过解析域名获取ip地址的方法.分享给大家供大家参考,具体如下: 从网上查找的一些资料,特此做个笔记 案例1: def getIP(domain): myaddr = socket.getaddrinfo(domain, 'http') print(myaddr[0][4][0]) 执行函数 getIP("www.google.com") 案例2: def get_ip_list(domain): # 获取域名解析出的IP列表 ip_list = [] t

Python如何把十进制数转换成ip地址

需要把ip地址转换为10进制数,然后也可以把10进制数转化为ip地址,计算机ping这个十进制数可以ping通对应的ip地址,说明已经实现功能 代码如下 # 引用正则来三等分字符串 import re # 转换成二进制数 bi = "{0:b}".format(18223104) # 补齐32位 bi = "0"*(32-len(bi))+bi # 8个一组算出每8个数字的十进制,然后再加","分隔 ret_ip_string = '.'.joi

基于python实现查询ip地址来源

从http://freeapi.ipip.net和http://ip-api.com/json/这两个网站提供的免费调用接口查询IP地址归属地. 接口调用方法是在url后面直接加上IP地址. url = 'http://freeapi.ipip.net/218.192.3.42' #中文免费 url2 = 'http://ip-api.com/json/218.192.3.42' #外国网站 ip.py: import sys import requests def main(argv): ur

python如何判断IP地址合法性

互联网上的每台计算机都有独一无二的编号,称为IP地址,每个合法的IP地址由"."分开的4个数字组成,并且IP地址细分类型的话,可以分为"A" "B" "C" "D" "E"类,我们常常使用的是C类IP地址所以第一个数字组成开头不能含有"0",因为那是A类IP地址专属的,好奇的朋友可以去查查哦. 现在用户输入一个字符串(不含有空格)判断是否合法. import os,s

python实现ip地址查询经纬度定位详解

1.此api已经关闭 https://api.map.baidu.com/highacciploc/v1?qcip=220.181.38.113&ak=你申请的AK&extensions=1&coord=bd09ll 2.现在改成 API首页:http://lbsyun.baidu.com/index.php?title=webapi/ip-api 使用方式:https://api.map.baidu.com/location/ip?ak=请输入您的AK&coor=bd09

Python将主机名转换为IP地址的方法

关于主机名转IP地址只记住两点即可: 1.英特网协议一直都是用4字节的IP将包转发给目的地: 2.至于主机名是如何转换成IP地址的,这是操作系统关心的事情: import socket hostname = 'www.baidu.com' addr = socket.gethostbyname(hostname) print 'The address of', hostname, 'is', addr 输出: The address of www.baidu.com is 115.239.211

Python正则表达式匹配和提取IP地址

Linux No.1 IPv4 下面是IPv4的IP正则匹配实例: 简单的匹配给定的字符串是否是ip地址 import re if re.match(r"^(?:[0-9]{1,3}\.){3}[0-9]{1,3}$", "236.168.192.1"): print "IP vaild" else: print "IP invaild" 精确的匹配给定的字符串是否是IP地址 import re if re.match(r&q

python正则表达式匹配IP代码实例

这篇文章主要介绍了python正则表达式匹配IP代码实例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 import re re.search(r'([1]\d\d|2[0-4]\d|25[0-5])','192') #re.search(r'([01]\d\d)','1XX') #[01] \d \d # 1 0-9 0-9 #re.search(r'(2[0-4]\d)','2XX') #2 [0-4] \d #2 0-4 0-9 #re.

C#正则表达式分解和转换IP地址实例(C#正则表达式大全 c#正则表达式语法)

只能输入数字:"^[0-9]*$". 只能输入n位的数字:"^\d{n}$". 只能输入至少n位的数字:"^\d{n,}$". 只能输入m~n位的数字:."^\d{m,n}$" 只能输入零和非零开头的数字:"^(0|[1-9][0-9]*)$". 只能输入有两位小数的正实数:"^[0-9]+(.[0-9]{2})?$". 只能输入有1~3位小数的正实数:"^[0-9]+(.[0

Python 正则表达式匹配数字及字符串中的纯数字

Python 正则表达式匹配数字 电话号码:\d{3}-\d{8}|\d{4}-\d{7} QQ号:[1-9][0-9]{4,} 中国邮政编码:[1-9]\d{5}(?!\d) 身份证:\d{15}|\d{18} ip地址:\d+\.\d+\.\d+\.\d+ [1-9]\d*      正整数 -[1-9]\d* 负整数 -?[1-9]\d* 整数 [1-9]\d*|0 非负整数 -[1-9]\d*|0 非正整数 [1-9]\d*\.\d*|0\.\d*[1-9]\d*$ 正浮点数 -([1-

解决Python正则表达式匹配反斜杠''\''问题

在学习Python正则式的过程中,有一个问题一直困扰我,如何去匹配一个反斜杠(即"\")? 一.引入 在学习了Python特殊字符和原始字符串之后,我觉得答案应该是这样的: 1)普通字符串:'\\' 2)原始字符串:r'\' 但事实上在提取诸如"3\8"反斜杠之前的数字时,我屡次碰壁,始终得不到结果.最终发现自己理解错了,原来原始字符串和"正则转义"没有一点关系:下面详细谈一谈. 二.字符串转义 反斜杠,在Python中比较特殊,就是它可以用来构

Python使用django获取用户IP地址的方法

本文实例讲述了Python使用django获取用户IP地址的方法.分享给大家供大家参考.具体如下: 函数实现: def get_client_ip(request): try: real_ip = request.META['HTTP_X_FORWARDED_FOR'] regip = real_ip.split(",")[0] except: try: regip = request.META['REMOTE_ADDR'] except: regip = "" r

Python正则表达式匹配中文用法示例

本文实例讲述了Python正则表达式匹配中文用法.分享给大家供大家参考,具体如下: #!/usr/bin/python #-*- coding:cp936-*-#思路,将str转换成unicode,方可用正则表达式,前提是,要知道文件的编码,本例中是gbk import cPickle as mypickle import re import sys if (__name__=='__main__'): fid1=file('demo.txt','r');#demo.txt写入字符如:我们 p=

Python 正则表达式匹配字符串中的http链接方法

利用Python正则表达式匹配字符串中的http链接.主要难点是用正则表示出http 链接的模式. import re pattern = re.compile(r'http[s]?://(?:[a-zA-Z]|[0-9]|[$-_@.&+]|[!*\(\),]|(?:%[0-9a-fA-F][0-9a-fA-F]))+') # 匹配模式 string = 'Its after 12 noon, do you know where your rooftops are? http://tinyur

Python正则表达式匹配数字和小数的方法

1.正则匹配数字,\为转义字符,d+为匹配一次或多次 如下所示:返回的结果为列表 2.正则匹配小数 如下所示,返回的结果125.6为字符串 总结 以上所述是小编给大家介绍的Python正则表达式匹配数字和小数的方法,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的.在此也非常感谢大家对我们网站的支持! 如果你觉得本文对你有帮助,欢迎转载,烦请注明出处,谢谢!

Python正则表达式匹配日期与时间的方法

下面给大家介绍下Python正则表达式匹配日期与时间 #!/usr/bin/env python # -*- coding: utf-8 -*- __author__ = 'Randy' import re from datetime import datetime test_date = '他的生日是2016-12-12 14:34,是个可爱的小宝贝.二宝的生日是2016-12-21 11:34,好可爱的.' test_datetime = '他的生日是2016-12-12 14:34,是个可