给定两个整数 n 和 k,返回 1 … n 中所有可能的 k 个数的组合。
示例 1: 来源:力扣(LeetCode) 链接:
解题思路
虽然是中等题,但是使用python内置函数,就简单了。
组合,没有重复的情况(不放回抽样组合) 使用 itertools.combinations
方法,
def combine(self, n: int, k: int) -> List[List[int]]:
result = []
for i in itertools.combinations(list(range(1, n+1)), k):
result.append(list(i))
return result
# [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]] 6
其它方法:
组合,有重复的情况(放回抽样组合) 使用 itertools.combinations_with_replacement
方法,
def combine(self, n: int, k: int) -> List[List[int]]:
result = []
for i in itertools.combinations_with_replacement(list(range(1, n+1)), k):
result.append(list(i))
return result
# [[1, 1], [1, 2], [1, 3], [1, 4], [2, 2], [2, 3], [2, 4], [3, 3], [3, 4], [4, 4]] 10
- 排列 (不放回抽样排列)使用 `itertools.permutations` 方法,
1
2
3
4
5
6
def combine(self, n: int, k: int) -> List[List[int]]:
result = []
for i in itertools.permutations(list(range(1, n+1)), k):
result.append(list(i))
return result
# [[1, 2], [1, 3], [1, 4], [2, 1], [2, 3], [2, 4], [3, 1], [3, 2], [3, 4], [4, 1], [4, 2], [4, 3]] 12
- 笛卡尔积 (有放回抽样排列) 使用 `itertools.product` 方法,
1
2
3
4
5
6
def combine(self, n: int, k: int) -> List[List[int]]:
result = []
for i in itertools.product(list(range(1, n+1)), repeat = k):
result.append(list(i))
return result
# [[1, 1], [1, 2], [1, 3], [1, 4], [2, 1], [2, 2], [2, 3], [2, 4], [3, 1], [3, 2], [3, 3], [3, 4], [4, 1], [4, 2], [4, 3], [4, 4]] 16
`combinations`和`permutations`返回的是对象地址, 需要将iterator 转换成list 即可
题解1:
执行用时:48 ms, 在所有 Python3 提交中击败了95.61%的用户
内存消耗:14.8 MB, 在所有 Python3 提交中击败了98.26%的用户
import itertools
from typing import List
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
result = []
for i in itertools.combinations(list(range(1, n+1)), k):
result.append(list(i))
return result