LeetCode解题报告(46,47)--排列

46. Permutations

原题如下:

Given a collection of distinct numbers, return all possible permutations. For example, [1,2,3] have the following permutations: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].

题目要求列出给定的不重复数字的所有排列结果。解题方法有两种。下面分别讲述。

方法一

第一种方法每次取一个数字,将数字插入现有的排列中形成新的排列,然后重复上面的过程直到所有数字都被取完。

实现代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
def permute(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
result = [[]]
for num in nums:
new_result = []
for seq in result:
for i in xrange(len(seq)+1):
new_result.append(seq[:i]+[num]+seq[i:])
result = new_result
return result

方法二

第二种方法采用回溯法。将当前数字与后面的数字逐一交换,当与某一数字交换后,然后移动到下一个数字重复上面的操作。实现具体代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
def permute(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
result = []
self.helper(nums,0,result)
return result

def helper(self, nums, begin, result):
n = len(nums)
if begin == n:
tmp = nums[:]
result.append(tmp)
return

for i in xrange(begin,n):
nums[begin],nums[i] = nums[i], nums[begin]
self.helper(nums,begin+1,result)
nums[begin],nums[i] = nums[i], nums[begin]

47. Permutations II

原题如下:

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example, [1,1,2] have the following unique permutations: [1,1,2], [1,2,1], and [2,1,1].

这道题目的要求与上一道一样,只是在上面的基础上添加了存在重复数字的约束条件。 上面提到回溯法在这里不适用了(即使判定交换的元素是否相等),比如说对于[1,2,3,3]就不正确了。

采用方法一的直接插入法,从后往前插,遇到与当前要插入数字相同的数字时就终止当前排列的插入,进行下一个排列的插入。实现的具体代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
def permuteUnique(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
result = [[]]
for num in nums:
new_result = []
for seq in result:
n = len(seq)
for i in xrange(n,-1,-1):
if i < n and seq[i] == num:
break
new_result.append(seq[:i]+[num]+seq[i:])
result = new_result
return result