资讯专栏INFORMATION COLUMN

leetcode77. Combinations

garfileo / 2690人阅读

摘要:再在前一种情况下继续下一轮的遍历,并将结果添加到队列末尾。思路二递归其实,通过递归的方法我们也可以在前一轮的基础上进行下一轮的计算。

题目要求
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],
]

有整数从1到n,问从中任选两个数有多少排列组合的结果(顺序无关)

思路一:利用链表(超时问题)

这题其实是动态编码的一个题目,可以通过链表实现队列存储前一种情况。再在前一种情况下继续下一轮的遍历,并将结果添加到队列末尾。代码如下:

    public List> combine(int n, int k) {
            List> result = new LinkedList>();
            if(k==0){
                return result;
            }
            for(int i = 0 ; i+k<=n ; i++){
                result.add(Arrays.asList(i+1));
            }
            while(result.get(0).size() != k){
                List currentList = result.remove(0);
                for(int i = currentList.get(currentList.size()-1) + 1 ; i<=n ; i++){
                    List temp = new ArrayList(currentList);
                    temp.add(i);
                    result.add(temp);
                }
            }
            return result;
     }

但是在这里存在超时问题,归根结底在于每一次都要创建新的数组用来保存临时结果,既占用内存又影响效率。

思路二:递归

其实,通过递归的方法我们也可以在前一轮的基础上进行下一轮的计算。递归代码如下:

     public List> combine2(int n, int k){
         List> result = new ArrayList>();
         if(k==0) return result;
         combine2(result, new ArrayList(), 1, n, k);
         return result;
     }

    public void combine2(List> currentResult, List list, int start, int n, int k){
         if(k==0){
             currentResult.add(new ArrayList(list));
             return;
         }
         while(start+k-1<=n){
             list.add(start++);
             combine2(currentResult, list, start, n, k-1);
             list.remove(list.size()-1);
         }
     }


想要了解更多开发技术,面试教程以及互联网公司内推,欢迎关注我的微信公众号!将会不定期的发放福利哦~

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/67304.html

相关文章

  • Leetcode 相似题只有题号不含代码。

    找出string里的单词。 186. Reverse Words in a String II, 434. Number of Segments in a String combination类型题 77. Combinations 39. Combination Sum 40. Combination Sum II 216. Combination Sum III 494. Target S...

    StonePanda 评论0 收藏0
  • leetcode-93-Restore IP Addresses

    摘要:题目描述题目理解将一段字符广度搜索截取,分别有种组合形式,添加限制条件,过滤掉不适合的组合元素。长度,大小,首字母应用如果进行字符串的子元素组合穷举,可以应用。所有的循环,利用到前一个状态,都可以理解为动态规划的一种分支 题目描述:Given a string containing only digits, restore it by returning all possible va...

    wmui 评论0 收藏0
  • leetcode78. Subsets

    摘要:题目要求类似的题目有可以参考这篇博客可以参考这篇博客思路一递归还是利用递归的方式,在前一种情况的基础上遍历下一轮的组合情况。 题目要求 Given a set of distinct integers, nums, return all possible subsets. Note: The solution set must not contain duplicate subset...

    Rocko 评论0 收藏0
  • [LeetCode - Backtracking] Combinations

    摘要:本题与类似,都是用回溯法。求中个数的不同组合,很明显我们需要注意的就是每个数字只能出现一次,这点与不同。 CombinationsGiven 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 solu...

    fizz 评论0 收藏0
  • [Leetcode] Letter Combinations of a Phone Number 电

    摘要:最新更新请见深度优先搜索复杂度时间空间递归栈空间思路首先建一个表,来映射号码和字母的关系。然后对号码进行深度优先搜索,对于每一位,从表中找出数字对应的字母,这些字母就是本轮搜索的几种可能。 Letter Combinations of a Phone Number 最新更新请见:https://yanjia.me/zh/2019/01/... Given a digit string...

    fxp 评论0 收藏0

发表评论

0条评论

garfileo

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<