动态设计网站,图书网站建设方案,票务网站模板,万网网站搬家1 问题
给定一个不含重复数字的数组 nums #xff0c;返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
示例 1#xff1a;
输入#xff1a;nums [1,2,3] 输出#xff1a;[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2#xff1a;
输入#x…1 问题
给定一个不含重复数字的数组 nums 返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
示例 1
输入nums [1,2,3] 输出[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2
输入nums [0,1] 输出[[0,1],[1,0]]
示例 3
输入nums [1] 输出[[1]]
2 答案
自己写的回溯算法得出答案不对
class Solution:def permute(self, nums: List[int]) - List[List[int]]:def dfs(start, size, path, res):if len(path) size:res.append(path)for index in range(start, size): # 这样写循环导致只能按顺序生成列dfs(index1, size, path[nums[index]], res)res []path []size len(nums)dfs(0, size, path, res)return res官方解回溯算法
class Solution:def permute(self, nums: List[int]) - List[List[int]]:def dfs(path, size, depth, used, res):if depth size:res.append(path)for i in range(size):if used[i] False:used[i] Truedfs(path[nums[i]], size, depth1, used, res)used[i] False # 深度优先遍历结束之后要把used[i]变为False以便后面遍历这个很关键path, res [], []used [False for _ in range(len(nums))]dfs(path, len(nums), 0, used, res)return res也可以这样写拷贝path并使用pop()。因为变量 path 所指向的列表 在深度优先遍历的过程中只有一份 深度优先遍历完成以后回到了根结点成为空列表。
class Solution:def permute(self, nums: List[int]) - List[List[int]]:def dfs(nums, size, depth, path, used, res):if depth size:res.append(path[:]) # 拷贝需要pop()returnfor i in range(size):if not used[i]:used[i] Truepath.append(nums[i])dfs(nums, size, depth 1, path, used, res)used[i] Falsepath.pop()size len(nums)used [False for _ in range(size)]res []dfs(nums, size, 0, [], used, res)return res3 知识点
回溯法 采用试错的思想它尝试分步的去解决一个问题。在分步解决问题的过程中当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候它将取消上一步甚至是上几步的计算再通过其它的可能的分步解答再次尝试寻找问题的答案。回溯法通常用最简单的递归方法来实现在反复重复上述的步骤后可能出现两种情况
找到一个可能存在的正确的答案在尝试了所有可能的分步方法后宣告该问题没有答案。
深度优先搜索 算法英语Depth-First-SearchDFS 是一种用于遍历或搜索树或图的算法。这个算法会 尽可能深 的搜索树的分支。当结点 v 的所在边都己被探寻过搜索将 回溯 到发现结点 v 的那条边的起始结点。这一过程一直进行到已发现从源结点可达的所有结点为止。如果还存在未被发现的结点则选择其中一个作为源结点并重复以上过程整个进程反复进行直到所有结点都被访问为止。
