题目简介
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 中的任何数字。你可以按 任何 顺序返回答案。
78. 子集
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
90. 子集 II
给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
初见思路
- (待复盘)
class Solution:
def restoreIpAddresses(self, s: str) -> List[str]:
if len(s) > 12: # edge case
return list()
self.result = list()
self.comb = list()
self.split_cnt = 0
self.back_track(s,0)
return self.result
def back_track(self,s,index) -> None:
# print(self.comb)
if self.split_cnt == 3:
if self.is_valid_ip(s, index, len(s)-1):
self.result.append(s)
return
for i in range(index,len(s)):
if self.is_valid_ip(s,index,i):
s = s[0:i+1] + '.' + s[i+1:]
self.split_cnt += 1
self.back_track(s, i+2)
self.split_cnt -= 1
s = s[0:i+1] + s[i+2:]
else:
break
def is_valid_ip(self,s,start,end) -> bool:
if start > end:
return False
if s[start] == '0' and start!=end:
return False
num = 0
for i in range(start,end+1):
if s[i] > '9' or s[i] < '0':
return False
num = num * 10 + int(s[i])
if num > 255:
return False
return True
78、90本质是同一道题的两种变式，要学会举一反三
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
if len(nums) == 1:
return [[],[nums[0]]]
self.ans = []
self.path = list()
self.back_tracking(nums,0)
return self.ans
def back_tracking(self,nums,index) -> None:
self.ans.append(self.path[:])
if index == len(nums):
return
for i in range(index,len(nums)):
self.path.append(nums[i])
self.back_tracking(nums, i+1)
self.path.pop()
- (如何去重与重排序？)
class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
if len(nums) == 1:
return [[],[nums[0]]]
nums.sort()
self.ans = []
self.path = list()
self.visited = [False]*len(nums)
self.back_tracking(nums,0)
return self.ans
def back_tracking(self,nums,index) -> None:
self.ans.append(self.path[:])
if index == len(nums):
return
for i in range(index,len(nums)):
if i > index and nums[i] == nums[i-1] and not self.visited[i-1]:
continue
self.path.append(nums[i])
self.visited[i] = True
self.back_tracking(nums, i+1)
self.visited[i] = False
self.path.pop()
复盘思路
https://programmercarl.com/0093.%E5%A4%8D%E5%8E%9FIP%E5%9C%B0%E5%9D%80.html
https://programmercarl.com/0078.%E5%AD%90%E9%9B%86.html
https://programmercarl.com/0090.%E5%AD%90%E9%9B%86II.html
