题目简介

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 ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。

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

初见思路

93. (待复盘)

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()

90. (如何去重与重排序？)

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

重点难点

今日收获