day22-数据结构力扣

发现又涨了一个粉丝心情愉悦491.递增子序列题目链接491. 非递减子序列 - 力扣LeetCode思路首先也是要求全部子集然后我们根据题目条件筛选要不递减长度大于等于2不重复提交效率低但是思路简单粗暴class Solution: def findSubsequences(self, nums: List[int]) - List[List[int]]: res [] def backtrack(start: int, path: List[int]): path_sortsorted(path) if len(path)2 and pathpath_sort and path not in res: res.append(path.copy()) # 从start开始遍历避免重复子集 for i in range(start, len(nums)): path.append(nums[i]) # 选择当前元素 backtrack(i 1, path) # 递归不能重复选自己 path.pop() # 回溯撤销选择 backtrack(0, []) return res46.全排列题目链接46. 全排列 - 力扣LeetCode思路感觉是一个典中典的题但是我没背过它的代码自己想还是想不出来。这是回溯法最经典的题型和子集、IP 复原思路同源但核心区别全排列要用完所有元素且顺序不同算不同结果。核心思路每次从所有未用过的数字里选一个加入路径用used 数组标记数字是否被使用避免重复选当路径长度 数组长度时就是一个完整排列回溯撤销选择继续尝试其他可能妙啊用一个数组把使用未使用做标记提交from typing import List class Solution: def permute(self, nums: List[int]) - List[List[int]]: res [] n len(nums) # 标记数字是否被使用 used [False] * n def backtrack(path): # 终止条件路径长度等于数组长度找到一个全排列 if len(path) n: res.append(path.copy()) return # 每次都遍历所有数字和子集不同子集是从start开始 for i in range(n): if not used[i]: # 没被使用才选 used[i] True # 标记为已使用 path.append(nums[i]) backtrack(path) # 递归 path.pop() # 回溯撤销选择 used[i] False # 取消标记 backtrack([]) return res47.全排列 II题目链接47. 全排列 II - 力扣LeetCode思路就是在上道题的基础上去重那在收集结果的时候加一下判断条件就好了只改了这一句if len(path)n and path not in res:提交class Solution: def permuteUnique(self, nums: List[int]) - List[List[int]]: res[] nlen(nums) used[False]*n def backtrack(path): if len(path)n and path not in res: res.append(path[:]) return for i in range(n): if not used[i]: path.append(nums[i]) used[i]True backtrack(path) path.pop() used[i]False backtrack([]) return res