刷题

简介: 1

theme: channing-cyan

Offer 驾到,掘友接招!我正在参与2022春招打卡活动,点击查看活动详情

一、题目描述:

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

你可以按 任何顺序 返回答案。

示例 1:

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

输入:n = 1, k = 1 输出:[[1]]

提示:

1 <= n <= 20 1 <= k <= n

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/combinations

二、思路分析:

本题这是回溯法的经典题目。直接的解法当然是使用for循环,思路简单但效率相对没有优势,可以使用回溯搜索法,具体步骤如下

定义成全局变量便不必再当作参数传入函数

剪枝,判断当前长度和数组剩余长度能否构成一个k个数的组合

for 循环里 i 从 start 到 n。

比如,n = 5,k = 4,temp.size( ) == 1,此时代表我们还需要(4 - 1 = 3)个数字,

如果 i = 4 的话,以后最多把 4 和 5 加入到 temp 中,而此时 temp.size() 才等于 1 + 2 = 3,

不够 4 个,所以 i 没必要等于 4,i 循环到 3 就足够了。

所以 for 循环的结束条件可以改成, i <= n - ( k - temp.size ( ) ) + 1,因为我们最后取到了 n,所以还要加 1。

public List<List<Integer>> combine(int n, int k) {
    List<List<Integer>> ans = new ArrayList<>();
    getAns(1,n, k, new ArrayList<Integer>(), ans);
    return ans;
}
​
private void getAns(int start, int n, int k, ArrayList<Integer> temp, List<List<Integer>> ans) { 
    if(temp.size() == k){
        ans.add(new ArrayList<Integer>(temp));
        return;
    }
    for (int i = start; i <= n - (k -temp.size()) + 1; i++) {
        temp.add(i);
        getAns(i+1, n, k, temp, ans);
        temp.remove(temp.size() - 1);
    }
}

四、总结:

image.png

回溯法和递归一样,开始学习的时候会觉得有些绕,所以一定要多加练习,逐渐体会回溯的过程,理清代码的组成结构,一定会有所进步!

掘友们,解题不易,留下个赞或评论再走吧!谢啦~ 💐

相关文章
|
6月前
刷题(二)
刷题(二)
25 1
|
6月前
刷题(一)
刷题(一)
33 0
|
6月前
|
Serverless C语言
【C刷题】day7
【C刷题】day7
44 0
|
12月前
|
编译器 数据安全/隐私保护 C++
【C刷题】day4
【C刷题】day4
66 0
【C刷题】day4
|
12月前
|
C语言
【C刷题】day5
【C刷题】day5
44 0
【C刷题】day5
|
12月前
|
C语言
【C刷题】day6
【C刷题】day6
66 0
|
12月前
|
C语言
【C刷题】day1
【C刷题】day1
110 0
|
12月前
【C刷题】day2
【C刷题】day2
58 0
|
12月前
|
编译器 C语言
【C刷题】day3
【C刷题】day3
53 0
|
前端开发
牛客刷题Day3
牛客刷题Day3
93 0