leetcode-77-组合
题目描述
给定两个整数 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本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-09-08，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录