代码随想录算法训练营第二十八天| 93.复原IP地址、78.子集 、90.子集II

代码随想录算法训练营第二十八天| 93.复原IP地址、78.子集 、90.子集II

题目

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 中的任何数字。你可以按 任何 顺序返回答案。

class Solution:def restoreIpAddresses(self, s: str) -> List[str]: res = []pointNum = 0self.backstracking(s, 0, 0, "", res)return resdef backstracking(self, s, pointNum, starIndex, curPath, res):if pointNum == 3:if self.isValid(s, starIndex, len(s)-1):curPath += s[starIndex:]res.append(curPath)returnfor i in range(starIndex, len(s)):if self.isValid(s, starIndex, i):sub = s[starIndex: i+1]self.backstracking(s, pointNum+1, i+1, curPath+sub+'.', res)def isValid(self, s, starIndex, endIndex):if starIndex > endIndex:return Falseif starIndex < endIndex and s[starIndex] == '0':return Falsesum_ = 0for i in range(starIndex, endIndex+1):if not s[i].isdigit():return Falsesum_ = sum_ * 10 + int(s[i])if sum_ > 255:return Falsereturn True

题目

78.子集

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

class Solution:def subsets(self, nums: List[int]) -> List[List[int]]:res = []used = [False] * len(nums)self.backtracking(0, [], nums, res)return resdef backtracking(self, startIndex, curPath, nums, res):res.append(curPath[:])for i in range(startIndex, len(nums)):curPath.append(nums[i])self.backtracking(i+1, curPath, nums, res)curPath.pop()

题目

90.子集II

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

class Solution:def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:res = []nums.sort()self.backstracking(nums, 0, [], res)return resdef backstracking(self, nums, startIndex, curPath, res):if curPath not in res:res.append(curPath[:])for i in range(startIndex, len(nums)):curPath.append(nums[i])self.backstracking(nums, i+1, curPath, res)curPath.pop()