极客算法

46. 全排列(Permutations)

2020-09-10

46. Permutations

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

示例:

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

DFS

O(N!)

排列组合, DFS必背程序之一

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        res = []
        visited = set()
        self.helper(nums, [], visited, res)
        return res
        
    def helper(self, nums: List[int], ans: List[int], visited: set, res:List[int]) -> None:
        
        if len(ans) == len(nums):
            res.append(ans.copy())
            return
        
        for i in range(len(nums)):
            if nums[i] in visited:
                continue
                
            ans.append(nums[i])
            visited.add(nums[i])
            
            self.helper(nums, ans, visited, res)
            
            ans.pop()
            visited.remove(nums[i])

为啥学算法?

  1. 面试需要:这点很实际,也许算法并不能帮你拿到Offer,但是若算法题做不出来,极有可能错失良机
  2. 技能迁移:我认为程序开发主要依赖语言+算法+平台Framework+协议. 入行新的领域,可能要学新的语言,新的平台框架,新的协议。但是算法是可以迁移的。
  3. 内功修炼:操作系统,计算机网络,编译原理,开源框架,处处存在算法。修好算法,可以事半功倍。
  4. 屠龙神技:”面试造火箭,工作拧螺丝”。也许世界上龙很少出现,但是一旦出现,唯有身怀神技的猎手才有机会

–End–


相关推荐

评论

内容: