leetcode-77-组合

2020-09-08 约 614 字预计阅读 2 分钟

题目描述

给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。

示例

示例 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


输入: n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/robot-return-to-origin

解题思路

虽然是中等题，但是使用python内置函数，就简单了。

组合,没有重复的情况（不放回抽样组合）使用 itertools.combinations 方法，

1
2
3
4
5
6


    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 方法，

1
2
3
4
5
6


    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
7


    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%的用户

1
2
3
4
5
6
7
8
9


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

目录

leetcode-77-组合

题目描述

示例