欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

天天刷leetcode——46.全排列

程序员文章站 2022-03-27 13:03:57
全排列地址: https://leetcode-cn.com/problems/permutations/.题目描述给定一个 没有重复 数字的序列,返回其所有可能的全排列。解题思路1. 回溯算法回溯的核心就是一个多叉树的遍历过程。只需要从根遍历这个树,记录路上的数,所有路径就是全排列。回溯算法的核心架构:def traveser(track, choiceList): ''' :param track: 路径 :param choiceList: 选择列表 :...

全排列

地址: https://leetcode-cn.com/problems/permutations/.

题目描述

给定一个 没有重复 数字的序列,返回其所有可能的全排列。

解题思路

1. 回溯算法

回溯的核心就是一个多叉树的遍历过程。只需要从根遍历这个树,记录路上的数,所有路径就是全排列。

回溯算法的核心架构

def traveser(track, choiceList):
    '''
    :param track: 路径
    :param choiceList: 选择列表
    :return: res
    '''
    # if 满足结束条件:
    #     result.append(track)
    #     return 
    for i in range(len(choiceList)):
        # 排除不合法的操作
        # 做选择
        traveser(track,choiceList) # 进入下一层决策树
        track.pop(-1)   # c撤销选择

本题的代码:

    def permute(self, nums: List[int]) -> List[List[int]]:
        def backtrack(nums,track):
            # 结束条件,nums的长度等于track长度
            if len(track) == len(nums):
                res.append(track[:])
                return 
            for i in range(len(nums)):
                # 排除不合法的选择
                if nums[i] in track:
                    continue
                # 做选择
                track.append(nums[i])
                # 进入下一层决策树
                backtrack(nums,track)
                #  取消选择
                track.pop(-1)

        # 路径记录在track
        # 选择列表:nums不存在与track中的那些元素
        # 结束条件:nums中的元素都在track中出现
        res = []
        track =[]
        backtrack(nums,track)
        return res

之间

if len(track) == len(nums):
   res.append(track)
   return 

结果却是[[],[],[],[],[],[]],看了leetcode上有人的解释:track变量所指向的对象在递归的过程中只有一份,深度优先遍历完成之后,因为回到了根节点,因此track这个变量回到根节点以后都是空。python中方法变量的传递为值传递,这些地址被添加到res变量,单实际上指向的上同一块内存地址,因此每次都是空列表对象。这个时候,只需要把track换成track[:],做一次值拷贝就行了
总结:空间复杂度全排列个数为N!每个全排列占空间N就是O(NN!)。时间复杂度O(NN!)
天天刷leetcode——46.全排列

2. 直接递归

递归结束条件:当列表内只有一个元素,全排列就是自己
递归过程:以取一个数,然后递归其他数的方式求出所有的全排列。
比如:
[1,3,4,4,5,6]取[1],然后全排列[3,4,5,6]。

def permute(self,nums:List[int]):
	if len(nums) <= 1:
		return [nums]
	res = []
	for idx,num in enumerate(nums):
		res_num = nums[:idx] + nums[idx+1:]
		for j in self.permuate(res_nums):
			res.append([num]+j)
	return res

天天刷leetcode——46.全排列

references

[1] leetcode 46 全排列: https://leetcode-cn.com/problems/permutations/submissions/

本文地址:https://blog.csdn.net/qq_30516823/article/details/107659523