专栏首页健程之道力扣77——组合

力扣77——组合

原题

给定两个整数 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/

本文分享自微信公众号 - 健程之道(JianJianCoder),作者:健健壮

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-12-26

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 力扣74——搜索二维矩阵

    编写一个高效的算法来判断 m x n 矩阵中,是否存在一个目标值。该矩阵具有如下特性:

    健程之道
  • 力扣221——最大正方形

    在一个由 0 和 1 组成的二维矩阵内,找到只包含 1 的最大正方形,并返回其面积。

    健程之道
  • 力扣227——227. 基本计算器 II

    字符串表达式仅包含非负整数,+, - ,*,/ 四种运算符和空格 。整数除法仅保留整数部分。

    健程之道
  • 7.2 Sqoop2安装

    版权声明:本文为王小雷原创文章,未经博主允许不得转载 https://blog.csdn.n...

    王小雷
  • 安全漏洞公告

    1 IBM WebSphere Portal WEB内容管理程序信息泄露漏洞 IBM WebSphere Portal WEB内容管理程序信息泄露漏洞发布时...

    安恒信息
  • Python2和Python3中urllib库的区别

    在Python中,我们通常使用urllib中的urlencode方法将字典编码,用于提交数据给url等操作,但是在Python2和Python3中urllib模...

    周小董
  • 回溯法(一)——n皇后问题

    问题描述 在一个n*n的棋盘上放置皇后,要求:一个皇后的同一行、同一列、同一条对角线上不允许出现其他皇后。请给出所有的放置方案。 ? 算法思路 思路很简单,...

    大闲人柴毛毛
  • 数据帮你挑选餐厅

    大数据文摘
  • [PHP]MySQL的wait_timeout与pdo对象

    Warning: Error while sending QUERY packet 或者 MySQL server has gone away

    陶士涵
  • 【踩坑】angularJS 1.X版本中 ng-bind 指令多空格展示

    做项目的时候遇到的问题 1、问题描述   用户在表单某个值输入多个空格,例如:A     B,保存至服务器   在列表查询页面中使用bg-bind的指令单向绑定...

    SmileSmith

扫码关注云+社区

领取腾讯云代金券

玩转腾讯云 有奖征文活动