三亚旅游网站建设,海外网站cdn加速,中山营销型网站建设,制作企业网站页面html46. 全排列
回溯算法。可以手绘一个二叉树#xff0c;考虑所有可能的情况。 每次选择一个元素#xff0c;下次就选择未被选择的数#xff0c;这样到达终止条件后就将当前路径添加到结果中。 完后撤销上次的选择#xff0c;尝试下一个选择。
class Solution:def permute(s…46. 全排列
回溯算法。可以手绘一个二叉树考虑所有可能的情况。 每次选择一个元素下次就选择未被选择的数这样到达终止条件后就将当前路径添加到结果中。 完后撤销上次的选择尝试下一个选择。
class Solution:def permute(self, nums: List[int]) - List[List[int]]:res [] # 存放所有符合条件结果的集合path [] # 存放当前符合条件的结果# 回溯函数def backtrack(nums):# 终止条件if len(path) len(nums): res.append(path[:]) # 保存副本return # 遍历所有的元素for index in range(len(nums)):# 只要不在path里的if nums[index] not in path:# 添加path.append(nums[index])# 递归尝试继续添加看看结果backtrack(nums)# 回溯不添加path.pop()backtrack(nums)return res
47. 全排列 II
与上一题的区别在于含有重复元素并且要求结果不能重复。 比方说[1,1,2]那么第一条路径选择1继续选择1选择2 第二条路径从第二个1开始如果再选择第一个1那么就重复了所以跳过第一个1选择2这个时候再选择1.
class Solution:def permuteUnique(self, nums: List[int]) - List[List[int]]:res []path []nums.sort() # 排序used [False] * len(nums) # 初始化标记数组def backtrack():if len(path) len(nums):res.append(path[:]) # 添加到结果中returnfor i in range(len(nums)):# 跳过已经使用过的数字或者重复的数字if used[i] or (i 0 and nums[i] nums[i-1] and not used[i-1]):continuepath.append(nums[i])used[i] Truebacktrack() # 递归调用path.pop() # 回溯used[i] False # 回溯backtrack()return res 这段代码i 0 and nums[i] nums[i-1] and not used[i-1]用于避免在递归过程中生成重复的排列。它的工作原理如下 i 0确保当前元素nums[i]不是序列的第一个元素因为我们只需要检查当前元素与前一个元素是否相同而第一个元素前面没有元素可以比较。nums[i] nums[i-1]检查当前元素nums[i]是否与前一个元素nums[i-1]相同。如果它们相同那么有可能产生重复的排列因为相同的数字在不同的位置被选中。not used[i-1]检查前一个相同的元素nums[i-1]在当前的递归路径中是否没有被使用。如果used[i-1]是False即not used[i-1]是True这意味着前一个相同的元素尚未被加入到当前的排列中。在这种情况下我们跳过当前元素nums[i]的选择以避免产生重复的排列。 结合这三个条件这段代码的目的是在nums已经排序的前提下只有当当前元素与前一个元素相同并且前一个相同的元素没有在当前排列递归路径中使用时才跳过当前元素的选择。这样做是为了确保每种元素值的排列在结果集中只出现一次即使这个元素值在原始数组中出现多次。 例如对于数组[1,1,2]第一个1和第二个1是相同的。在排列[1, _, _]的第二个位置上如果第一个1已经被使用我们还可以选择第二个1但是如果第一个1没有被使用意味着我们是从第二个1开始构建排列的那么我们就不应该再次选择第二个1因为这会导致重复的排列。 22. 括号生成
隐式的回溯。因为字符串是不可变类型所以每次递归传入一个新的就行这样原始的字符串是不变的。
class Solution:def generateParenthesis(self, n: int) - List[str]:res [] # 总体结果temp # 当前结果字符串left, right 0,0 # 左右括号计数def generate(temp, left, right):# 终止条件if len(temp) 2*n:res.append(temp)return # 回溯# 当左括号数量不够时递归传入新的字符串实现隐式回溯if left n:generate(temp(, left1, right)if right left:generate(temp), left, right1)generate(temp, left, right)return res 使用path (或path )的方式来“回溯”而不是显式地向path添加括号然后再移除是一种更简洁且有效的方法来处理字符串构建问题中的回溯。这种方法的优势在于每次递归调用时创建了一个新的字符串因此不需要在每一层递归结束时撤销上一步的操作。这样每一次递归调用都是基于当前路径的一个全新拷贝反映了在那一点上做出的所有选择。 在这种方法下path变量在每次递归调用时都保持不变因为字符串在Python中是不可变的。当你通过path (或path )传递给下一层递归时实际上是创建了一个包含了当前选择的新字符串。这样当递归函数返回时它返回到了拥有之前状态的path上从而实现了自然的回溯无需手动撤销选择。 这种隐式回溯的做法不仅适用于字符串操作在处理数组或列表时如果采用类似的不修改原数组或列表而是通过传递新的数组或列表副本的方式也可以达到隐式回溯的效果。但是要注意对于数组或列表这种做法可能会带来额外的空间消耗。在处理字符串时由于字符串的不可变性这种做法既自然又高效。 17. 电话号码的字母组合
规则是每个数字对应的字母不能组合只能和其余的数字的字母组合。 每条路径都是选择一个数字的某一个字母这样形成的路径长度就等于数字数即终止条件 回溯主体依次选择一个数字的字母们然后挨个选择后续数字的字母。 详细步骤 建立映射表首先建立一个映射表将每个数字映射到相应的字母。回溯函数实现一个回溯函数用于生成所有可能的字母组合。 递归终止条件当生成的组合长度等于输入数字字符串的长度时将该组合添加到结果列表中。遍历当前数字对应的所有字母对于当前数字遍历它映射到的所有字母然后将当前字母添加到当前路径组合中并递归地继续处理下一个数字。回溯递归调用返回后撤销上一步的选择尝试下一个可能的字母。 开始回溯从输入的第一个数字开始调用回溯函数生成所有可能的字母组合。 下面是具体的代码实现
class Solution:def letterCombinations(self, digits: str) - List[str]:# 如果输入为空则直接返回空列表if not digits:return []# 建立数字到字母的映射表digit_to_letters {2: abc, 3: def, 4: ghi, 5: jkl,6: mno, 7: pqrs, 8: tuv, 9: wxyz}# 结果列表res []# 回溯函数def backtrack(index, path):# 如果当前路径的长度等于输入数字的长度添加到结果列表if len(path) len(digits):res.append(path)return# 获取当前数字对应的所有可能字母possible_letters digit_to_letters[digits[index]]# 遍历所有可能字母for letter in possible_letters:# 回溯考虑当前字母backtrack(index 1, path letter)# 从第一个数字开始回溯backtrack(0, )return res在这段代码中backtrack函数负责生成所有可能的字母组合。它使用index来跟踪当前处理到的数字位置并使用path来存储当前生成的字母组合。每次递归调用都会向path中添加一个新的字母直到生成了一个完整的字母组合然后将其添加到结果列表中。通过递归地遍历每个数字映射到的所有可能字母这段代码能够生成并返回所有可能的字母组合。
40. 组合总和 II
每个元素只能使用一次。 需要注意的是要先排序同时判断每个元素是不是在每次路径选择时被重复选择。
class Solution:def combinationSum2(self, candidates: List[int], target: int) - List[List[int]]:candidates.sort() # 排序res []def backtrack(start, path, target):if target 0:res.append(path[:]) # 找到一个组合添加到结果列表中returnfor i in range(start, len(candidates)):# 跳过同一树层使用过的元素避免重复组合if i start and candidates[i] candidates[i - 1]:continueif candidates[i] target:break # 由于candidates已排序当前数字大于target则后面的数字都不可能符合条件可以直接结束循环# 递归调用不再需要used数组backtrack(i 1, path [candidates[i]], target - candidates[i])backtrack(0, [], target)return res 理解这个条件的关键在于区分递归中的“深度”递归调用的层次与“同一层上的遍历”。这个条件实际上是用来处理在同一层递归上的重复元素而不是在不同的递归深度上。让我来详细解释一下 在回溯算法中start参数的作用是控制在当前递归层次上我们从candidates数组的哪个位置开始遍历。每次递归调用backtrack时我们都将start设置为i 1这表示在下一层递归中我们将从candidates数组中start位置的元素开始遍历从而保证了每个元素在每个组合中只被使用一次。 当我们说“同一层上的遍历”时我们是指在当前递归深度中对candidates数组的遍历。而if i start and candidates[i] candidates[i - 1]:这个条件的目的是为了确保在这种同一层的遍历中如果当前元素和前一个元素相同即出现重复我们将跳过当前元素从而避免产生重复的组合。 i start确保了我们不在递归的最开始判断这个条件因为在每层递归的开始i start。只有当我们在同一层的后续遍历中即已经至少选择了一个元素加入到当前组合中这个条件才会被评估。candidates[i] candidates[i - 1]是检查当前元素是否和前一个元素相同。 在这种情况下i start并不意味着我们已经移动到了下一层递归而是在当前递归层次深度的遍历中我们已经向前移动了至少一步。这个条件帮助我们仅在当前层次而不是在开始新的递归层次时跳过重复元素。 总之这个条件确保我们只在同一层递归中遇到连续重复元素时跳过它们从而避免在结果集中出现重复的组合而不是阻止在递归的不同层次中重新选择先前已经考虑过的元素。 90. 子集 II
遇见含有重复元素的必须先重排然后每次都要考虑同一层递归中的重复元素不能选择。 正确的逻辑是在同一层的递归中如果当前元素和它之前的元素相同那么就跳过当前元素以避免生成重复的子集。但是你的代码中跳过重复元素的条件写错了位置应该是在同一次递归调用的循环中而不是基于index和当前i的比较。
class Solution:def subsetsWithDup(self, nums: List[int]) - List[List[int]]:res []path []nums.sort() # 对nums排序以方便处理重复元素def back(start, path):res.append(path[:]) # 添加当前路径到结果列表for i in range(start, len(nums)):# 跳过当前层的重复元素if i start and nums[i] nums[i-1]:continue# 递归调用考虑包含当前元素的子集back(i 1, path [nums[i]])back(0, [])return res改动点说明 修改了back函数的参数名从index变为start这样可能更清晰地表示这个参数的作用即表示递归时遍历的起始位置。for i in range(start, len(nums)):保证了每次递归只考虑当前元素之后的元素避免重复生成子集。if i start and nums[i] nums[i-1]:这个条件确保了跳过那些在当前递归层次中已经考虑过的、重复的元素。注意这里的逻辑是i start而不是i index。这是因为我们希望跳过的是同一递归层次上的重复元素而start正是这一层递归开始考虑元素的索引。 通过这种方式即使nums中包含重复元素也能够正确生成所有不重复的子集。 79. 单词搜索
尝试从每个格子出发在上下左右搜索看是否能找到可行路径。如果不能找到就继续下一个格子继续找。
class Solution:def exist(self, board: List[List[str]], word: str) - bool:# 获取网格的行数和列数rows, cols len(board), len(board[0])# 定义回溯函数def backtrack(row, col, index):# 终止条件如果当前字符索引等于单词长度说明已经找到匹配的单词if index len(word):return True# 检查边界条件以及当前格子字符是否匹配单词中对应的字符if row 0 or row rows or col 0 or col cols or board[row][col] ! word[index]:return False# 先暂时标记这个格子防止再次访问board[row][col] ## 检查当前格子的上下左右四个方向for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]:# 对于每个方向递归地调用回溯函数if backtrack(row dx, col dy, index 1):# 如果找到一条正确的路径则直接返回Truereturn True# 如果当前路径不通撤销之前的标记回溯到上一状态board[row][col] word[index]return False# 从网格的每个格子出发尝试匹配wordfor i in range(rows):for j in range(cols):# 以网格的(i, j)格子作为起点尝试匹配wordif backtrack(i, j, 0): # 0代表从word的第一个字符开始匹配return True# 如果所有格子都无法匹配整个word则返回Falsereturn False
这个代码实现的核心思想是利用回溯算法搜索网格中的路径以匹配给定的单词word。算法从网格的每一个格子开始尝试对于每个起点都尝试在网格中向四个方向扩展路径以匹配word中的下一个字符。每当一个字符匹配成功算法就递归地继续向前匹配下一个字符直到所有字符都成功匹配或者无法继续匹配为止。
在搜索过程中为了避免同一个格子被重复使用在访问一个格子之后会暂时将其标记为已访问状态这里用字符’#标记。如果从当前格子出发无法完成匹配或者已经成功找到匹配的路径就将格子恢复为原来的字符以便其他路径的搜索可以正常使用该格子。这种标记和恢复原状的操作是回溯算法的典型特征它使得算法可以探索所有可能的路径寻找解决方案。
