上海网站设计工作室,制作ppt用什么软件,中企动力是国企性质吗,在百度做推广送网站好吗131. 分割回文串 思想#xff1a;回溯三步骤#xff01;① 传入参数 ② 回溯结束条件 ③ 单层搜索逻辑#xff01;抽象成回溯树#xff0c;树枝上是每次从头部穷举切分出的子串#xff0c;节点上是待切分的剩余字符串【从头开始每次往后加一】 class Solution:def partiti…131. 分割回文串 思想回溯三步骤① 传入参数 ② 回溯结束条件 ③ 单层搜索逻辑抽象成回溯树树枝上是每次从头部穷举切分出的子串节点上是待切分的剩余字符串【从头开始每次往后加一】 class Solution:def partition(self, s: str) - List[List[str]]:result []self.backtrack(s,0,[],result)return resultdef backtrack(self, s, start, temp_list, result):# 结束条件当start遍历到s的长度的时候说明子串都满足条件if start len(s):# [:]这个很重要不小心的会丢失了数据result.append(temp_list[:])return for i in range(start,len(s)):# 如果满足子串是回文串继续递归否则在原基础往后移动if self.huiwenchuan(s, start, i):# 当前节点 i 1temp_list.append(s[start:i 1])self.backtrack(s, i 1, temp_list, result)# 回溯操作temp_list.pop()# 判断回文子串def huiwenchuan(self, s, start1, end1):start start1end end1while start end:if s[start] ! s[end]:return Falsestart 1end - 1return True
78. 子集
思路组合问题和分割问题就是收集回溯树叶子节点而子集就是找树的所有节点需要考虑是否有序其实子集也是一种组合问题因为它的集合是无序的子集{1,2} 和 子集{2,1}是一样的。那么既然是无序取过的元素不会重复取写回溯算法的时候for就要从startIndex开始而不是从0开始 class Solution:def subsets(self, nums: List[int]) - List[List[int]]:result []result.append([])self.backtrack(nums, [], 0, result)return resultdef backtrack(self, nums, temp_list, start_index, result):if len(temp_list) 1:result.append(temp_list[:])# 取树上的节点了 不需要return i 1 会自动结束for i in range(start_index, len(nums)):temp_list.append(nums[i])self.backtrack(nums, temp_list, i 1, result)temp_list.pop()90. 子集 II
思路和78.子集 (opens new window)区别就是集合里有重复元素了而且求取的子集要去重。简单一点就排序后进行获取子集或者树层去重或树枝去重 class Solution:def subsetsWithDup(self, nums: List[int]) - List[List[int]]:result []result.append([])nums.sort() # 为什么加了这个就能通过对子集进行排序的时候会发现有重复的子集了self.backtrack(nums, [], 0, result)return resultdef backtrack(self, nums, temp_list, start_index, result):# 关键是去重if len(temp_list) 1:if temp_list not in result:result.append(temp_list[:])# 取树上的节点了 不需要returnfor i in range(start_index, len(nums)):temp_list.append(nums[i])self.backtrack(nums, temp_list, i 1, result)temp_list.pop()class Solution:def subsetsWithDup(self, nums):result []path []nums.sort() # 去重需要排序self.backtracking(nums, 0, path, result)return resultdef backtracking(self, nums, startIndex, path, result):result.append(path[:]) # 收集子集uset set()for i in range(startIndex, len(nums)):if nums[i] in uset:continueuset.add(nums[i])path.append(nums[i])self.backtracking(nums, i 1, path, result)path.pop()
class Solution:def subsetsWithDup(self, nums):result []path []used [False] * len(nums)nums.sort() # 去重需要排序self.backtracking(nums, 0, used, path, result)return resultdef backtracking(self, nums, startIndex, used, path, result):result.append(path[:]) # 收集子集for i in range(startIndex, len(nums)):# used[i - 1] True说明同一树枝 nums[i - 1] 使用过# used[i - 1] False说明同一树层 nums[i - 1] 使用过# 而我们要对同一树层使用过的元素进行跳过if i 0 and nums[i] nums[i - 1] and not used[i - 1]:continuepath.append(nums[i])used[i] Trueself.backtracking(nums, i 1, used, path, result)used[i] Falsepath.pop()
