【力扣hot100】刷题笔记Day17

前言

• 今天竟然不用开组会！天大的好消息，安心刷题了

46. 全排列 - 力扣（LeetCode）

• 回溯（排列）

  • 

  • class Solution:
        def permute(self, nums: List[int]) -> List[List[int]]:
            # 回溯
            def backtrack():
                if len(path) == len(nums):
                    res.append(path[:])  # 如果path长度达到要求，收集结果，注意python要拷贝res
                    return 
                for i in range(len(nums)):
                    if used[i] == 0:  # 遍历所有没用过的
                        used[i] = 1
                        path.append(nums[i])
                        backtrack()
                        path.pop()  # 撤销
                        used[i] = 0  # 撤销
            # 可变对象在函数中可以直接改不需要作为参数，也不需要写self，只有赋值需要
            # 比如：递归里self.res= max(self.res，l+r)需要用self或递归里nonlocal res声明
            n = len(nums)
            used = [0] * n
            path = []
            res = []
            backtrack()
            return res
    

• 回溯（交换填充）

  • 

  • class Solution:
        def permute(self, nums: List[int]) -> List[List[int]]:
            def backtrack(first = 0):
                # 所有数都填完了
                if first == n:  
                    res.append(nums[:])
                for i in range(first, n):
                    # 动态维护数组
                    nums[first], nums[i] = nums[i], nums[first]
                    # 继续递归填下一个数
                    backtrack(first + 1)
                    # 撤销操作
                    nums[first], nums[i] = nums[i], nums[first]
            
            n = len(nums)
            res = []
            backtrack()
            return res
    

 78. 子集 - 力扣（LeetCode）

• 回溯（组合）

  • class Solution:
        def subsets(self, nums: List[int]) -> List[List[int]]:
            def backtrack(start=0):
                res.append(path[:])  # 每到一个节点就传一次答案
                # if start == n: return  # 下面的for循环隐含这个终止条件
                for i in range(start, n):
                    path.append(nums[i])
                    backtrack(i+1)  # 注意这里传入的是i+1
                    path.pop()
            n = len(nums)
            res = []
            path = []
            backtrack(0)
            return res
    

17. 电话号码的字母组合 - 力扣（LeetCode） 

• 回溯（不同集合的组合）

  • class Solution:
        def letterCombinations(self, digits: str) -> List[str]:
            def backtrack(index = 0):
                if index == len(digits):
                    res.append("".join(path))  # 不用传复制因为已经新建字符串了
                    return
                s = mp[int(digits[index])]  # 取出对应数字的字符串
                for c in s:
                    path.append(c)
                    backtrack(index+1)
                    path.pop()
            if len(digits) == 0:
                return []
            mp = ['', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']  # 下标号码映射字符串
            path = []
            res = []
            backtrack()
            return res
    

39. 组合总和 - 力扣（LeetCode） 

• 回溯（排序剪枝）

  • class Solution:
        def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
            path = []
            res = []
            n = len(candidates)
            def backtrack(start, target):
                if target < 0: return    # 剪枝返回上一层，后面更大的数就没必要减了
                if target == 0:
                    res.append(path[:])
                    return
                for i in range(start, n):
                    path.append(candidates[i])
                    backtrack(i, target-candidates[i])  # 传i而不是i+1说明当前数可以重复选
                    path.pop()
            candidates.sort()  # 剪枝，排序后大的数在后面选择优先级低
            backtrack(0, target)
            return res
    

 22. 括号生成 - 力扣（LeetCode）

• 回溯（组合）

  • 这个题解结合官解就能看懂了，主要在于括号合法性判断上

  • class Solution:
        def generateParenthesis(self, n: int) -> List[str]:
            if n <= 0: return n
            res = []
     
            def backtrack(path, left, right):
                # 两种情况需要剪枝
                # 1.左括号多于n了：((((
                # 2.右括号多于左括号：())
                if left > n or right > left: return
                if len(path) == 2 * n:  # 因为括号都是成对出现的
                    res.append(path)
                    return
                backtrack(path + '(', left + 1, right)  # 生成一个加一个
                backtrack(path + ')', left, right + 1)
            backtrack('', 0, 0)
     
            return res
    

后言

• 今天就到这吧，还有其他事情，感觉回溯还不熟练，脑子里模拟不太出来，待会去看看代码随想录再熟悉熟悉