77. Combinations「建议收藏」

77. Combinations「建议收藏」Giventwointegers n and k,returnallpossiblecombinationsof k numbersoutof1… n.Forexample,If n =4and k =2,asolutionis:[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4],]

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用

Given two integers n and k, return all possible combinations of k numbers out of 1 … n.

For example,
If n = 4 and k = 2, a solution is:

[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]


 
题意:给定n和k,求1-n中任意k个数的组合。
这个题我们给出2种解法
第一种:递归
对于任意的n和k,
1.我们先求出从1到n-1中任意k个数的组合
2.然后求,1到n-1中任意k-1个数的组合,每个组合加n,
最后将组合合并到一个集合即可
具体代码:

class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> list = new ArrayList<>();
        if(n<k)
            return list;
        if(n==k){
            List<Integer> list1 = new ArrayList<>();
            for(int i=1;i<=n;i++)
                list1.add(i);
            list.add(list1);
            return list;
        }
        if(k == 1){
            for(int i=0;i<n;i++){
                List<Integer> list1 = new ArrayList<>();
                list1.add(i+1);
                list.add(list1);
            }
            return list;
        }
        List<List<Integer>> list2 = combine(n-1,k-1);
        for(List<Integer> l : list2){
            l.add(n);
        }
        list = combine(n-1,k);
        list.addAll(list2);
        return list;
    }
}
				

第二种解法,我们使用回溯的思想

class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> list = new ArrayList<>();
          if(n<k)
            return list;
        combine(list,new ArrayList<Integer>(),k,n,1);
        return list;
    }
    public void combine(List<List<Integer>> list,List<Integer> tempList,int k,int n,int start){
        if(tempList.size() == k){
            list.add(new ArrayList<Integer>(tempList));
        }else{
            for(int i=start;i<=n;i++){
                tempList.add(i);
                combine(list,tempList,k,n,i+1);
                tempList.remove(tempList.size()-1);
            }
        }
    }
}

上述2种解法中,递归解法在LeetCode上超越了90%左右,而使用回溯的解法只超越了40%多,显然递归要好一些。对此,我觉得可能是使用递归的过程中计算的都是我们需要求的组合,但是在回溯中会多次出现碰到“死胡同”这样的情况,导致了2种解法在时间空间上存在差异。举个例子:

 我们要求n=9,k=9的组合,显然只有一种组合满足题意,但是当我们使用回溯算法时,tempList分别加入1,2,3,4,5,6,7,8,9之后就不需要再计算了,但事实上,我们仍旧还计算了加入tempList中的第一个元素为2,3,4,5,6,7,8,9的情况,而这些情况显然已经不符合题意了,我觉得这个过程做的无用功是导致这种解法不优的原因。
既然如此,我们在原回溯解法上稍作优化,在回溯方法的第一行加上一个判断条件

if(tempList.size()+n-start+1 < k)
            return;

假设之后所有元素都加入tempList中都比k小的时候,我们不需要再计算了。

这样一来,运行结果在LeetCode上超越了85%左右,与递归解法相差小了很多;
由此可见,有时候一行代码足以改变一种算法的优劣程度



版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请联系我们举报,一经查实,本站将立刻删除。

发布者:全栈程序员-站长,转载请注明出处:https://javaforall.net/185263.html原文链接:https://javaforall.net

(0)
全栈程序员-站长的头像全栈程序员-站长


相关推荐

  • 充分不必要条件和必要不充分条件的意思_怎么区分充分必要条件

    充分不必要条件和必要不充分条件的意思_怎么区分充分必要条件转载:https://www.zhihu.com/question/30469121充分条件:只要有A,就一定能达成B,A是B的充分条件。充分不必要条件:有A,一定能达到B;就算没有A,也有可

    2022年8月6日
    3
  • 理解希尔排序的排序过程是_希尔排序原理

    理解希尔排序的排序过程是_希尔排序原理1,有关插入排序(1)插入排序的基本方法是:每步将一个待排序的元素,按其排序码大小插入到前面已经排好序的一组元素的适当位置上去,直到元素全部插入为止。(2)可以选择不同的方法在已经排好序的有序数据表中寻找插入位置,依据查找方法的不同,有多种插入排序方法。下面是常用的三种。1>直接插入排序2>折半插入排序3>希尔排序(3)直接插入排序基本思想:当插入第i(i>1)个元素时,前

    2022年10月20日
    0
  • 看完这篇还不会SQL优化,算我输。。。

    前言 本文主要针对的是关系型数据数据库MySql。键值类数据库可以参考: https://www.jianshu.com/p/098a870d83e4 先简单梳理下Mysql的基本…

    2021年6月22日
    108
  • leetcode 792_leetcode5421编码

    leetcode 792_leetcode5421编码给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中,返回 true ;否则,返回 false 。单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。示例 1:输入:board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word = “ABCCED”输出:true示例 2:输

    2022年8月9日
    3
  • python命名规则标识符_python中有效的标识符

    python命名规则标识符_python中有效的标识符标识符规则1、由大小写字母、数字和下划线组成,只能以字母或者下划线开头。2、不能高阔除下划线以外的其他热河字符,如%……%¥#@3、不能包含换行符、空格和制表符等空白字符。4、不能使用Python中的关键字和约定俗成的名称,如print5、Python区分大小写。…

    2022年9月9日
    0
  • ubuntu16.04.3安装教程_Ubuntu16下安装QQ

    ubuntu16.04.3安装教程_Ubuntu16下安装QQUbuntu16.04.1安装NginxNginx(“enginex”)是一个高性能的HTTP和反向代理服务器,也是一个IMAP/POP3/SMTP代理服务器。Nginx是由IgorSysoev为俄罗斯访问量第二的Rambler.ru站点开发的,第一个公开版本0.1.0发布于2004年10月4日。其将源代码以类BSD许可证的形式发布,因它的稳定性、丰富的功能集

    2022年9月16日
    0

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注全栈程序员社区公众号