首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >力扣77——组合

力扣77——组合

作者头像
健程之道
发布2019-12-31 12:55:41
3180
发布2019-12-31 12:55:41
举报
文章被收录于专栏:健程之道健程之道

原题

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

示例:

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

原题url:https://leetcode-cn.com/problems/combinations/

解题

递归获取

一开始的想法就是遍历递归获取,利用一个 stack 存储中间结果,不断进行出栈入栈,这样肯定就能拿全。

让我们来看看代码:

class Solution {
    public List<List<Integer>> combine(int n, int k) {
        if (k == 0) {
            return new LinkedList<>();
        }
        if (n == 0) {
            return new LinkedList<>();
        }

        List<List<Integer>> result = new LinkedList<>();
        Stack<Integer> stack = new Stack<>();
        dfs(n, k, 1, stack, result);

        return result;
    }

    public void dfs(int n, int remain, int index, Stack<Integer> stack, List<List<Integer>> result) {
        for (int i = index; i <= n; i++) {
                        // 加入stack中
            stack.push(i);
                        // 是否加到k个数
            if (remain - 1 == 0) {
                result.add(new LinkedList<>(stack));
            } else {
                dfs(n, remain - 1, i + 1, stack, result);
            }
                        // 将数从stack中拿出
            stack.pop();
        }
    }
}

提交OK,执行用时:73 ms,内存消耗:44 MB。是否还可以优化呢?

剪枝

今天看到了一个词剪枝,其实这个词是回溯剪枝回溯大家都懂,剪枝其实就是一种优化,减少回溯中不需要的情况。

从上面的代码可以看出,在回溯中的遍历,并不需要一直遍历到 n。比如:从 7 个数中取 4 个数,开始的时候遍历到 4 就足够了,因为从 5 开始凑不齐 4 个数,之后的遍历也是同样如此。

明知失败的事不需要一直进行到最后,和快速失败有些类似,接下来看看优化后的代码:

class Solution {
    public List<List<Integer>> combine(int n, int k) {
        if (k == 0) {
            return new LinkedList<>();
        }
        if (n == 0) {
            return new LinkedList<>();
        }

        List<List<Integer>> result = new LinkedList<>();
        Stack<Integer> stack = new Stack<>();
        dfs(n, k, 1, stack, result);

        return result;
    }

    public void dfs(int n, int remain, int index, Stack<Integer> stack, List<List<Integer>> result) {
            // 当剩余没有遍历的数,比还需要遍遍历的数少时,也可以不用继续了。
        for (int i = index; i <= n && (n - i + 1 >= remain); i++) {
                        // 加入stack中
            stack.push(i);
                        // 是否加到k个数
            if (remain - 1 == 0) {
                result.add(new LinkedList<>(stack));
            } else {
                dfs(n, remain - 1, i + 1, stack, result);
            }
            stack.pop();
        }
    }
}

代码更改极少,我们看看结果:执行用时:5 ms,内存消耗:40.7 MB

看似很小的变化,但效果却很好,看来这些细节确实是需要注意的。

总结

以上就是这道题目我的解答过程了,不知道大家是否理解了。这道题主要教会了需要剪枝,找到边界情况,边界找的更细,那么需要执行的时间也可能会越少。

有兴趣的话可以访问我的博客或者关注我的公众号,说不定会有意外的惊喜。

https://death00.github.io/

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2019-12-26,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 健程之道 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 原题
  • 解题
    • 递归获取
      • 剪枝
      • 总结
      领券
      问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档