LeetCode刷题实战77：组合
程序IT圈
共 4650字，需浏览 10分钟
·
2020-10-28 08:01
算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选 ！
今天和大家聊的问题叫做 组合，我们先来看题面：
https://leetcode-cn.com/problems/combinations/
Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.
You may return the answer in any order.
题意
输入: n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
解题
递归
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
def dfs(start, cur):
# 如果当前已经拿到了K个数的组合，直接加入答案
# 注意要做深拷贝，否则在之后的回溯过程当中变动也会影响结果
if len(cur) == k:
ret.append(cur[:])
return
# 从start+1的位置开始遍历
for i in range(start+1, n):
cur.append(i+1)
dfs(i, cur)
# 回溯
cur.pop()
ret = []
dfs(-1, [])
return ret
迭代
的组合都已经获取完了。如果n+1的位置还有滑动框，并且它的右侧还可以移动，那么我们需要将它往右移动一个，到n+2的位置。这个时候剩下的局面就是
，为了获取这些组合，我们需要把这m个滑动框全部再移动到直尺的最左侧，重新开始移动。class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
def comb(window, m, ret):
ret.append(window[:-1])
# 如果第m位的滑动框不超过直尺的范围并且m右侧的滑动框
while window[m] < min(n - k + m + 1, window[m+1] - 1):
# 向右滑动一位
window[m] += 1
# 如果m左侧还有滑动框，递归
if m > 0:
# 把左侧的滑动框全部移动到最左侧
window[:m] = range(1, m+1)
comb(window, m-1, ret)
else:
# 否则记录答案
ret.append(window[:-1])
ret = []
window = list(range(1, k+1))
# 额外多放一个滑动框作为标兵
window.append(n+1)
comb(window, k-1, ret)
return ret
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
# 构造滑动框
window = list(range(1, k + 1)) + [n + 1]
ret, j = [], 0
while j < k:
# 添加答案
ret.append(window[:k])
j = 0
# 从最左侧的滑动框开始判断
# 如果滑动框与它右侧滑动框挨着，那么就将它移动到最左侧
# 因为它右侧的滑动框一定会向右移动
while j < k and window[j + 1] == window[j] + 1:
window[j] = j + 1
j += 1
# 连续挨着最右侧的滑动框向右移动一格
window[j] += 1
return ret
总结
上期推文：
评论