企业官网建设流程全解析

目录

491. 非递减子序列

题目描述

解题思路

46. 全排列

题目描述

解题思路

47. 全排列 II

题目描述

解题思路

回溯法小结

491. 非递减子序列

题目描述

• 给你一个整数数组nums，找出并返回所有该数组中不同的递增子序列，递增子序列中至少有两个元素。你可以按任意顺序返回答案。

• 数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。

• 例如数组[4,6,4,7],他的非递减子序列为[4,6],[4,4],[4,7],[6,7]

解题思路

• 本题有两个大误区：

  • 题目中要求的递减子序列，不能对序列进行排序，所以不能用求前面子集和组合的方法对其进行排序的去重方法，栗如：[4,6,4,7]，按照前面求的方法先对其进行排序，然后进行树层去重，即下标为0的4包括的子序列包括了下标为2的子序列，所以不对第二个4进行递归。
  • 此题不是需要连续的子序列，那么下标更小的自然会囊括下标较大的相同元素的序列，若为连续的子序列，那么针对上面的例子，结果就是[4,6],[4,7],此时就不会有树层去重，因为每个相同元素他的后序子序列可能不同

• 那么该如何对此题进行去重呢？

  • 用集合去重，将遍历过的元素放入集合中，为什么此时不需要进行删除操作呢？
  • 因为就像[4,6,4,7]的栗子，4的子序列由第一个4来代替，如果删除了那么又会重复进行第二个4的子序列，没有达到树层去重

class Solution: def findSubsequences(self, nums: List[int]) -> List[List[int]]: if len(nums) < 2: return [] self.path = [] self.res = [] self.backtracking(nums,0) return self.res def backtracking(self,nums,start): if len(self.path) > 1: self.res.append(self.path[:]) if start >= len(nums): return uset = set() for i in range(start,len(nums)): if self.path and nums[i] < self.path[-1] or nums[i] in uset: continue uset.add(nums[i]) self.path.append(nums[i]) self.backtracking(nums,i+1) self.path.pop()

46. 全排列

题目描述

• 给定一个不含重复数字的数组nums，返回其所有可能的全排列。你可以按任意顺序返回答案。

• 例如：**输入：nums =[1,2,3],输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

解题思路

• 针对排列问题，是不需要start，因为排列的元素在不同位置是不一样的排列结果，比如[1,2,3],其中[1,2,3]和[3,2,1]就是不同的排列结果，但是是相同的组合结果，排列和元素的顺序有关，所以不能用start来限制元素，因为start以前的元素也包含在结果中
• 那么本题的逻辑就很简单，用used来表示数组中排列所使用过的元素，当当前used未使用时就将其加入，而使用过的说明在path数组中则跳过

class Solution: def permute(self, nums: List[int]) -> List[List[int]]: self.path = [] self.res = [] self.used = [False] * len(nums) self.backtracking(nums) return self.res def backtracking(self,nums): if len(self.path) == len(nums): self.res.append(self.path[:]) return for i in range(len(nums)): if self.used[i] == False: self.used[i] = True self.path.append(nums[i]) self.backtracking(nums) self.path.pop() self.used[i] = False

47. 全排列 II

题目描述

• 给定一个可包含重复数字的序列nums，按任意顺序返回所有不重复的全排列。

• **输入：nums =[1,1,2]，输出：[[1,1,2],[1,2,1], [2,1,1]]

解题思路

• 不使用排序时，用used来表示当前使用的元素，用uset集合来表示树层元素的去重
• 关键的是，在当前层的集合当中，比如说[1,1,2]的1的第二层，剩余元素是[1,2],就在剩余元素中进行去重，即将添加到集合中的逻辑写入if中
• 如果非要写在外面，那么此时顺序尤其重要，要先判断当前元素是否使用过，对使用过的元素continue，不能把使用过的元素加入到当前层的集合中，相当于上述例子中将第一个1加入到集合中，第二个1被集合去重去掉，如此，输出无结果

class Solution: def permuteUnique(self, nums: List[int]) -> List[List[int]]: self.path = [] self.res = [] self.used = [False] * len(nums) self.backtracking(nums) return self.res def backtracking(self,nums): if len(self.path) == len(nums): self.res.append(self.path[:]) return uset = set() for i in range(len(nums)): # if self.used[i] == True: # continue if nums[i] in uset: continue # uset.add(nums[i]) if self.used[i] == False: self.used[i] = True self.path.append(nums[i]) self.backtracking(nums) self.path.pop() self.used[i] = False uset.add(nums[i])

• 如果使用排序，那么此时就和前面一样，树层去重，判断i > 0 and nums[i] == nums[i - 1] and used[i - 1] == False，并且当当前元素使用过时，即used[i] == True也进行continue

回溯法小结

• 回溯的搜索过程：回溯是递归的副产品，回溯法的解题过程就是模拟一个树的过程
• 什么时候用start：组合问题时需要用到start，排列问题时不需要用到start
• 如何去重？树枝去重vs数层去重：去掉同一层的重复，保留同一树枝的重复
  • 树层去重：同一for循环中，相同数字保留一个，其他全部跳过，避免出现一模一样的组合
  • 树枝去重：往下递归的树枝上，不选重复的数字，回溯法中一般不能进行树枝去重
• 去重的两种方法：
  • 排序+used数组
  • 不排序+每层set去重