Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
给出一串不重复的数,输出所有排列数

思路一:DFS+保存路径
写法一

 1 #46
 2 #Runtime: 56 ms
 3 #Memory Usage: 13.4 MB
 4 
 5 class Solution(object):
 6     
 7     def permute(self, nums):
 8         """
 9         :type nums: List[int]
10         :rtype: List[List[int]]
11         """
12         vis = [0] * len(nums)
13         self.res = []
14         self.dfs(nums, vis, [])
15         return self.res   
16 
17     def dfs(self, nums, vis, s):
18         if len(s) == len(nums):
19             self.res.append(list(s))
20             return
21         else:
22             for i in range(len(nums)):
23                 if vis[i] == 0:
24                     vis[i] = 1
25                     s.append(nums[i])
26                     self.dfs(nums, vis, s)
27                     s.pop()
28                     vis[i] = 0


写法二(更快更短)

 1 #46
 2 #Runtime: 16 ms (Beats 95.78%)
 3 #Memory: 13.5 MB (Beats 34.30%)
 4 
 5 class Solution(object):
 6     
 7     def permute(self, nums):
 8         """
 9         :type nums: List[int]
10         :rtype: List[List[int]]
11         """
12         self.ans = []
13         self.vis = [0] * len(nums)
14         def dfs(t, k):
15             if k == len(nums):
16                 self.ans.append(t[:])
17                 return
18             for i in range(len(nums)):
19                 if not self.vis[i]:
20                     t.append(nums[i])
21                     self.vis[i] = 1
22                     dfs(t, k + 1)
23                     self.vis[i] = 0
24                     t.pop()
25         dfs([], 0)
26         return self.ans

思路二:Python的生成排列的函数

 1 #46
 2 #Runtime: 20 ms
 3 #Memory Usage: 13.7 MB
 4 
 5 class Solution(object):
 6     def permute(self, nums):
 7         """
 8         :type nums: List[int]
 9         :rtype: List[List[int]]
10         """
11         return permutations(nums)


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理