8000 add Permutations · jiaxinhuang/python-test-code@b3d3396 · GitHub
[go: up one dir, main page]
Skip to content

Commit b3d3396

Browse files
jiaxinhuangjiaxinhuang
committed
add Permutations
1 parent 35d516f commit b3d3396

File tree

4 files changed

+129
-0
lines changed

4 files changed

+129
-0
lines changed

‎leetcode/Permutations.md

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
# 题目说明
2+
3+
这题给定一个无重复元素的数组，求出其全排列。这里使用DFS的方法，进行递归遍历，实现代码如下：
4+
5+
```python
6+
class Solution(object):
7+
def permute(self, nums):
8+
"""
9+
:type nums: List[int]
10+
:rtype: List[List[int]]
11+
"""
12+
res = []
13+
self.dfs(nums, [], res)
14+
return res
15+
16+
def dfs(self, nums, path, res):
17+
if not nums:
18+
res.append(path)
19+
for i in range(len(nums)):
20+
self.dfs(nums[:i]+nums[i+1:], path+[nums[i]], res)
21+
```
22+
23+
另一种思路是直接使用数学直观上的每个位置遍历组合，实现代码如下：
24+
25+
```python
26+
class Solution(object):
27+
def permute(self, nums):
28+
"""
29+
:type nums: List[int]
30+
:rtype: List[List[int]]
31+
"""
32+
perms = [[]]
33+
for n in nums:
34+
new_perms = []
35+
for perm in perms:
36+
for i in xrange(len(perm)+1):
37+
new_perms.append(perm[:i]+[n]+perm[i:])
38+
perms = new_perms
39+
print perms
40+
return perms
41+
```
42+

‎leetcode/Permutations.py

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
#-*- coding:utf-8 -*-
2+
'''
3+
Created on 2017年5月25日
4+
5+
@author: huangjiaxin
6+
'''
7+
class Solution(object):
8+
def permute(self, nums):
9+
"""
10+
:type nums: List[int]
11+
:rtype: List[List[int]]
12+
"""
13+
perms = [[]]
14+
for n in nums:
15+
new_perms = []
16+
for perm in perms:
17+
for i in xrange(len(perm)+1):
18+
new_perms.append(perm[:i]+[n]+perm[i:])
19+
perms = new_perms
20+
print perms
21+
return perms
22+
23+
def dfs(self, nums, path, res):
24+
if not nums:
25+
res.append(path)
26+
for i in range(len(nums)):
27+
self.dfs(nums[:i]+nums[i+1:], path+[nums[i]], res)
28+
29+
30+
if __name__ == '__main__':
31+
nums = [1,2,3]
32+
print Solution().permute(nums)

‎leetcode/Permutations2.md

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
# 题目说明
2+
3+
这题的情况基本与前一题一样，这里存在重复元素的情况，所以只需要在执行前一版代码是添加一个条件判断即可，实现代码如下：
4+
5+
```python
6+
class Solution(object):
7+
def permuteUnique(self, nums):
8+
"""
9+
:type nums: List[int]
10+
:rtype: List[List[int]]
11+
"""
12+
nums.sort()
13+
res = []
14+
self.dfs(nums, [], res)
15+
return res
16+
17+
def dfs(self, nums, path, res):
18+
if not nums:
19+
res.append(path)
20+
for i in range(len(nums)):
21+
if i > 0 and nums[i] == nums[i-1]:
22+
continue
23+
else:
24+
self.dfs(nums[:i]+nums[i+1:], path+[nums[i]], res)
25+
```
26+

‎leetcode/Permutations2.py

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
#-*- coding:utf-8 -*-
2+
'''
3+
Created on 2017年5月25日
4+
5+
@author: huangjiaxin
6+
'''
7+
class Solution(object):
8+
def permuteUnique(self, nums):
9+
"""
10+
:type nums: List[int]
11+
:rtype: List[List[int]]
12+
"""
13+
nums.sort()
14+
res = []
15+
self.dfs(nums, [], res)
16+
return res
17+
18+
def dfs(self, nums, path, res):
19+
if not nums:
20+
res.append(path)
21+
for i in range(len(nums)):
22+
if i > 0 and nums[i] == nums[i-1]:
23+
continue
24+
else:
25+
self.dfs(nums[:i]+nums[i+1:], path+[nums[i]], res)
26+
27+
if __name__ == '__main__':
28+
nums = [1]
29+
print Solution().permuteUnique(nums)

0 commit comments

Comments
 (0)
0