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地址的资料请关注我们其它相关文章！

赞 (0)

相关推荐

  • 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地址的方法分析

    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 django框架应用中实现获取访问者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地址来源

    从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地址的包含关系判断

    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地址查询经纬度定位详解

    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地址合法性

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

  • 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地址

    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地址

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

随机推荐