代码随想录算法训练营day24| 93.复原IP地址 78.子集 90.子集2

tristan241001 / 2024-11-13 / 原文

学习资料：https://programmercarl.com/0093.复原IP地址.html#算法公开课

分割问题可用回溯法
子集和组合题都可以用回溯法，不同点在于:组合题的目标值都在叶子节点，而子集问题要收集所有的节点

👍给定一个数字字符串，如何返回数值：
num = 0
for i in string:
num += num*10 + int(i)

学习记录：
93.复原IP地址（用了两个函数，isValid来判断ip的每个片段是否合法（十位数或者百位数的开头不能是0，只能是数字，数字范围[0,255]），backtracking递归回溯；终止条件：切三刀切成4段，这里是加入‘.’的个数达到3，且最后一段也合法，就加入结果集中；取子集s[startIndex:i+1]?????）

点击查看代码

class Solution(object):
    def isValid(self, s, start, end):
        """
        判断ip是否有效的三点：
        1.当字段不止一位数字且开头为零，如‘012’，则不行
        2.字段里包含非数字符合，如“1@2”，则不行
        3.字段数字不在[0,255]范围，如“333”，则不行
        """
        if start>end:
            return False
        if s[start]=='0' and start != end:
            return False
        num = 0
        for i in range(start, end+1):
            if not s[i].isdigit():
                return False
            num = num * 10 + int(s[i])
            if num > 255:
                return False
        return True

    def backtracking(self, s, startIndex, current_s, point_num, result):
        # 终止条件：添加的点的个数达到3，也代表把字符串分割为4段了
        if point_num == 3:
            if self.isValid(s, startIndex, len(s)-1):
                current_s += s[startIndex:]
                result.append(current_s)
            return
        for i in range(startIndex, len(s)):
            if self.isValid(s, startIndex, i):
                sub = s[startIndex:i+1]
                # 这里的递归隐藏了回溯的过程，因为用的current_s+sub+'.'和point_num+1都不会改变current_s和point_num的值，就能在递归后回溯
                self.backtracking(s, i+1, current_s+sub+'.', point_num+1, result)   # 这里给每个字符串加上‘.’
            else:
                break

    def restoreIpAddresses(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        result = []
        self.backtracking(s, 0, '', 0, result)
        return result

78.子集（数组元素互不相同；收集所有节点的值）

点击查看代码

class Solution(object):
    def backtracking(self, nums, startIndex, path, result):
        result.append(path[:]) # 收集子集时，要放在终止条件上方
        if startIndex > len(nums):
            return
        for i in range(startIndex, len(nums)):
            path.append(nums[i])           # 子集问题：要收集树的所有节点
            self.backtracking(nums, i+1, path, result)    # 不能重复选取，则代入i+1
            path.pop()

    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        result = []
        self.backtracking(nums, 0, [], result)
        return result

90.子集2（数组有重复数字，不能出现相同的结果，去重）

点击查看代码

class Solution(object):
    def backtracking(self, nums, startIndex, path, result):
        result.append(path[:])
        if startIndex > len(nums):  # 终止条件可以省略（？不懂）
            return
        for i in range(startIndex, len(nums)):  # 每次循环是代表遍历一条树枝吧？？？
            if i>startIndex and nums[i] == nums[i-1]:   # 本题去重：同一树层不能出现同一数字，而同一树枝可以
                continue
            path.append(nums[i])
            self.backtracking(nums, i+1, path, result)   # 数字不能重复取，则i+1
            path.pop()

    def subsetsWithDup(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        result = []
        nums.sort()  # 先排序，才好去重
        self.backtracking(nums, 0, [], result)
        return result

PS:今天天气还是很好诶，终于吃到了番茄炒蛋小炒，美味，清汤豌杂面也很绝
今天第一次独立写出一道题，子集2，结合前面的组合和子集题，耶
而且今天的笔试有几道题是跟哈希表和二叉树有关的，终于有点感觉了（之前被华为的吊打）