这是基于代码随想录的每日打卡
93. 复原 IP 地址
有效 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"]
回溯法
class Solution:
def __init__(self):
self.res=[]
self.path=[]
# startIndex代表当前遍历到的字符下标
def traversal(self,s,startIndex):
# 递归终止
if startIndex==len(s):
if len(self.path)==4:
self.res.append('.'.join(self.path))
return
for i in range(startIndex,len(s)):
if self.isValid(s[startIndex:i+1]):
self.path.append(s[startIndex:i+1])
self.traversal(s,i+1)
self.path.pop()
else:
# 当前区间的字符串不合法，当前层的后面叶子节点全部都剪掉
break
def isValid(self,s):
# 判断字符串是否合法
if len(s)!=1 and s[0]=='0':
return False
elif int(s)>255 or int(s)<0:
return False
else:
return True
def restoreIpAddresses(self, s: str) -> List[str]:
self.traversal(s,0)
return self.res
运行结果
78. 子集
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1：
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2：
输入：nums = [0]
输出：[[],[0]]
回溯法
class Solution:
def __init__(self):
self.res=[]
self.path=[]
def traversal(self,nums,startIndex):
# 每次回溯收割每一层的结果
self.res.append(self.path[:])
# 递归终止
if startIndex==len(nums):
return
for i in range(startIndex,len(nums)):
self.path.append(nums[i])
self.traversal(nums,i+1)
self.path.pop()
def subsets(self, nums: List[int]) -> List[List[int]]:
self.traversal(nums,0)
return self.res
运行结果
90. 子集 II
给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的
子集（幂集）。
解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
示例 1：
输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
示例 2：
输入：nums = [0]
输出：[[],[0]]
回溯法
class Solution:
def __init__(self):
self.res=[]
self.path=[]
def traversal(self,nums,startIndex):
# 收割结果
self.res.append(self.path[:])
# 递归终止
if startIndex==len(nums):
return
for i in range(startIndex,len(nums)):
if i>startIndex and nums[i]==nums[i-1]:
continue
self.path.append(nums[i])
self.traversal(nums,i+1)
self.path.pop()
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
nums.sort()
self.traversal(nums,0)
return self.res
运行结果
