今天群里有个朋友出了个题, 是一家公司的面试题, 题目如下(补充: 对于 ip0 开头的也是无效的, 如分割后 001.1.1.1 这种是不可以的):
分析: 这里我们举一个最简单的例子 1.1.1.12.2.2.2 首先能想到的解决方法肯定是使用循环了, 我们可以写 2 个循环嵌套 (有点像冒泡排序) 从第 0 个位置截取 1 个, 从第 0 个位置截取 2 个直到从第 n-1 截取到 n 个为止(n 为字符串总长度)
如从第 1 个截取 1 个我们截取出来的就是 1, 第 1 个截取 2 个我们截取出来的就是 1., 第 1 个截取 3 个我们截取出来的就是 1.1 截取出来后我们可以通过 split 方法用. 拆分, 然后进行验证每个元素是否合法, 如果合法我们则继续往后遍历
但是这里使用循环就有个问题了, 比如我们截取出来 1.1.1.1, 我们判断合法, 那么循环下次截取的时候就是 1.1.1.12 了, 很显然这个并不是我们希望的结果我们更希望当有一个合法的 ip 出现后, 我们从它后面的位置重新开始查找合法的 ip 如后面几次的遍历就是 "2","2.","2.2" 这样的顺序找所以这里就想到了使用递归的方式来控制搜索的起始点和结束点
递归解决思路: 写递归第一件事就是确定结束条件, 因为递归写不好很容易死循环或者栈溢出, 这里我们可以很方便的算出结束条件就是起始位置是字符串长度 - 1 的位置, 结束的位置是字符长度的位置然后我们将参数一开始的默认值设置成开始位置 0, 结束位置 1(因为我们要将所有的情况都走一遍)当当前截取的内容条件不满足, 我们就将结束位置 + 1 再进行截取, 直到有满足条件的 ip 出现 (我们保存合法的 ip 以及当前起始位置和结束位置存到一个列表里) 我们则修改起始位置为当前结束位置 + 1 的位置, 结束位置为当前结束位置加 2 的位置, 或者一直到结束位置到最后一个位置, 我们再将起始位置设置成当前起始位置 + 1, 结束位置为起始位置加 2, 再进行递归, 直到递归结束
最后我们就可以获得一个类似这样的数据, 上面是 ip, 下面是当前 ip 对应的位置当然你会发现一些重复的数据, 因为确实会有重复的计算出现 (这里如果不需要找出全部值的话可以优化) 在这里我们搜索最终结果的时候只需要按着顺序看位置是不是连续到最后的, 如下面的第一个 [0, 7], 第二个[7, 14] 是连续到最后的, 所以结果就是 1.1.1.1 和 2.2.2.2 了
- ips: [1.1.1.1, 2.2.2.2, 1.1.1.12, 1.1.12.2, 1.12.2.2, 12.2.2.2, 2.2.2.2, 2.2.2.2]
- ips_pos: [[0, 7], [7, 14], [0, 8], [2, 10], [4, 12], [6, 14], [7, 14], [7, 14]]
附上本汪写的代码(有更好的方法欢迎一起讨论 ^_^)
- str = "1.1.1.10050.2.1.1101.2.2.2"
- ips = [] # 记录的 ip
- ips_pos = [] # 当前 ip 的起始位置
- def showIP(str, start, end):
- # 结束条件
- if (start == len(str)-1 and end == len(str) ):
- return
- sp = str[start:end].split(".")
- if (len(sp) == 4):
- #是否数字都满足所有转换规则
- flag = True
- # 是否所有数字都在范围内 1~255
- try:
- for i in range(0, 4):
- if(sp[i].startswith("0")):
- flag=False
- break
- now = int(sp[i])
- if (not (0 <now < 256)):
- flag = False
- break
- if (flag):
- ips.append(str[start:end]) # 保存 ip
- ips_pos.append([start,end]) # 保存 ip 的位置
- #递归计算
- if(end + 1> len(str)):
- showIP(str, start+1 , start +2)
- else:
- showIP(str, end , end + 1)
- except Exception as e:
- pass
- #递归计算
- if (end + 1> len(str)):
- showIP(str, start + 1, start + 2)
- else:
- showIP(str, start, end + 1)
- # 获取最后的结果
- def getResult(str,ips,pos):
- length=len(str) #长度
- result=[] #最终的结果
- #之前的起始和结束为止
- preStart=0
- preEnd=0
- #所有的起始和结束位置是否全部连续
- flag=True
- for i, item in enumerate(ips_pos):
- #第一次则保存为之前的值
- if(i==0):
- preStart=item[0]
- preEnd=item[1]
- result.append(ips[i])
- continue
- #之前结束的值等于现在开始的值则表示连续
- if(preEnd==item[0]):
- result.append(ips[i])
- preStart=item[0]
- preEnd=item[1]
- if(item[1]==length and flag):
- print("最终结果:",result)
- return
- #不连续
- else:
- flag=False
- #新的开始则设置为连续值
- if(item[0]==0):
- flag=True
- #清空结果重置之前的值
- result.clear()
- preStart = item[0]
- preEnd = item[1]
- result.append(ips[i])
- print("无结果")
- showIP(str, 0, 1)
- getResult(str,ips,ips_pos)
- # 运行结果:
- # 最终结果: [1.1.1.100, 50.2.1.1, 101.2.2.2]
当然递归如果直接满足条件是不是可以直接显示结果, 不在进行递归查找, 这里大家可以自己修改下看看哈当然也可以将多种情况都全部显示出来, 如 1.1.1.123.2.2.2 可以有 2 种结果 1.1.1.1 和 23.2.2.2 以及 1.1.1.12 和 3.2.2.2 大家都可以通过修改上面的代码实现哦
来源: http://www.bubuko.com/infodetail-2542379.html