leetcode-77-组合

题目描述

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

示例


  • 解题思路

    虽然是中等题,但是使用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
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
文章作者: Spaceack
文章链接: http://spaceack.com/2020/09/08/2020-09-08-leetcode-77-%E7%BB%84%E5%90%88/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 丸子家的小云吞
支付宝打赏
微信打赏