【力扣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