投简历找工作哪个网站好,违法网站开发,wordpress上传插件卡死,品牌商城网站建设公司难度
中等
题目
有效 IP 地址 正好由四个整数#xff08;每个整数位于 0 到 255 之间组成#xff0c;且不能含有前导 0#xff09;#xff0c;整数之间用 ‘.’ 分隔。
例如#xff1a;“0.1.2.201” 和 “192.168.1.1” 是 有效 IP 地址#xff0c;但是 “0.011.255…难度
中等
题目
有效 IP 地址 正好由四个整数每个整数位于 0 到 255 之间组成且不能含有前导 0整数之间用 ‘.’ 分隔。
例如“0.1.2.201” 和 “192.168.1.1” 是 有效 IP 地址但是 “0.011.255.245”、“192.168.1.312” 和 “192.1681.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 仅由数字组成
思路
IP 地址是 4 段所以将给出的字符串截成 4 段采用回溯算法纵向遍历递归的深度是 4横向遍历截取每一段从最左端开始截取每截取一段要判断是否有效即 必须是 [0,255] 中的整数并且每段如果不能是 01001。
代码
class Solution:def restoreIpAddresses(self, s):self.s sself.length len(self.s)self.result []self.backtrack(0, [])print(self.result)return self.resultdef isipaddr(self, string):# 如果是 01 012 这种的也是不符合的if len(string) 1 and string.startswith(0):return False# 如果数字超过了255 或者小于0也不符合if 0 int(string) 255:return Truereturn Falsedef backtrack(self, start, tmp):# ip地址要分为4段所以当tmp的长度为4时# start length 并且已经扫完了整个字符串就可以终止递归if len(tmp) 4 and start self.length:self.result.append(..join(tmp[:]))return# 开始for i in range(start, self.length):tmpstr self.s[start:i 1]if self.isipaddr(tmpstr):tmp.append(tmpstr)self.backtrack(i 1, tmp)tmp.pop()if __name__ __main__:s 25525511135s 0000s 101023obj Solution()obj.restoreIpAddresses(s)
