Skip to main content

46. 全排列[medium]

46. 全排列[medium]​

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

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

示例:

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

通过次数135,082 提交次数177,420

Second Try​

2020-06-06

学习了一波经典的backtrack回溯写法，写起来规范了许多，至少把套路功法跟上了，靠自己摸索写出来总有点不是业界正规军的感觉。

class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """

        if not nums:
            return []
        
        def dfs(seq, sets, nums, len_n, rv):
            if len(seq) == len_n:
                rv.append(seq + []) # 内存地址不同，创建了新列表
                return 
            for idx, x in enumerate(nums):
                if idx in sets:  # 用来判断是否已被使用
                    continue
                seq.append(x)
                sets.add(idx)
                dfs(seq, sets, nums, len_n, rv)
                seq.pop()
                sets.remove(idx)

        rv = []
        dfs([], set(), nums, len(nums), rv)
        return rv
  • 执行用时 :16 ms, 在所有 Python 提交中击败了96.16%的用户
  • 内存消耗 :12.7 MB, 在所有 Python 提交中击败了7.69%的用户
  • python列表加空列表，可以实现列表复制的功能
In [60]: a = [1, 2, 3, 4]

In [61]: id(a)
Out[61]: 4592438088

In [62]: b = a + []

In [63]: b
Out[63]: [1, 2, 3, 4]

In [64]: id(b)
Out[64]: 4592393416

In [65]: c = a

In [66]: id(c)
Out[66]: 4592438088

First Try​

直接用递归DFS方法，但是使用列表的话无法实现递归之间的隔离，于是改成了字符串。然后为了处理负数的问题，字符串里用上了间隔符。但是得分还是挺低的，还得系统学下套路才行，靠自己摸索效率比较低。

class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        if not nums:
            return []
        col = []

        def backtrack(idv, nums):
            if len(nums) == 1:
                idv = idv + str(nums[0])
                col.append([int(i) for i in idv.split("|")])
                return
            for i in range(len(nums)):
                left = (nums + nums)[i+1: len(nums)+i]
                tmp = idv + str(nums[i]) + "|" 
                # print(nums[i], left, tmp)
                backtrack(tmp, left)
        
        backtrack("", nums)
        return col
  • 执行用时 :32 ms, 在所有 Python 提交中击败了22.72%的用户
  • 内存消耗 :13.1 MB, 在所有 Python 提交中击败了7.69%的用户

backtrack回溯公式​

看来重点在撤销选择上面，每次使用新变量，或者是旧变量但是每次使用完会复归原样降低空间使用率？。

result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return
    
    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择