leetcode算法题求--全排列的求解

电玩女神 2022-12-12 02:14 125阅读 0赞

### 全排列（中等难度） ###

*  题目描述
 *   *  暴力法（调用itertool库）
     *   *  迭代法

# 题目描述 #

输入: [1,2,3]
    输出:
    [
      [1,2,3],
      [1,3,2],
      [2,1,3],
      [2,3,1],
      [3,1,2],
      [3,2,1]
    ]

## 暴力法（调用itertool库） ##

class Solution(object):
        def permute(self, nums):
            """
            :type nums: List[int]
            :rtype: List[List[int]]
            """
            return list(itertools.permutations(nums,len(nums)))
    permutations就是将nums数组中的元素，进行全排列 permutations(p[,r]);返回p中任意取r个元素做排列的元组的迭代器

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tpbmdKYW1lc2JvbmQ_size_16_color_FFFFFF_t_70_pic_center]

### 迭代法 ###

[官方文档][Link 1]

class Solution:
        def permute(self, nums):
            """
            :type nums: List[int]
            :rtype: List[List[int]]
            """
            def backtrack(first = 0):
                # 所有数都填完了
                if first == n:  
                    res.append(nums[:])
                for i in range(first, n):
                    # 动态维护数组
                    nums[first], nums[i] = nums[i], nums[first]
                    # 继续递归填下一个数
                    backtrack(first + 1)
                    # 撤销操作
                    nums[first], nums[i] = nums[i], nums[first]
            
            n = len(nums)
            res = []
            backtrack()
            return res

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tpbmdKYW1lc2JvbmQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/cf8e5db0b7e344ab935fc90e5d88bf0e.png
[Link 1]: https://leetcode-cn.com/problems/permutations/solution/quan-pai-lie-by-leetcode-solution-2/