频道栏目
首页 > 考试 > 其他 > 正文
LeetCode-77.Combinations
2017-06-28 10:17:54         来源:lemon2631的博客  
收藏   我要投稿

题目描述

LeetCode-77.Combinations,给定两个整数n和k,求1.2.3.4……n中所有可能出现的k个数的组合。如果n=4,k=2,则答案为[ [2,4],[3,4],[2,3],[1,2],[1,3],[1,4] ]。

解题思路

采用递归的方式解决,上面地答案简单整理一下可以看成是1,2;1,3;1,4;2,3;2,4;3,4;对于每个位置的数利用递归函数求解包含与他右边距离为1地数地解,然后求解距离为2,然后依次递增,直到当前数+step(间隔)+remain(剩余地数字个数)-2大于n,则跳出当前地循环。

代码

public class Solution {
    List> result=new ArrayList>();
    //这里是无法List> result=new ArrayList>(); 简单地理解可以是左边地List>变量可以添加LinkedList变量,而右边地变量ArrayList>变量却不能添加。
    List tem=new ArrayList();
     public List> combine(int n, int k) {

            if(k<=0 || n<=0 || k>n)
                return result;
            for(int i=1;i<=n-k+1;i++){
                combineCore(i,k,n);
            }
            return result;
        }
        //weizhi   shengyugeshu     step
        private void combineCore(int point,int remain,int n){
            if(remain==1){
                tem.add(point);
                result.add(new ArrayList(tem));
                tem.remove(tem.size()-1);
                return;
            }
            for(int step=1;point+step+remain-2<=n;step++){
                tem.add(point);
                combineCore(point+step,remain-1,n);
                tem.remove(tem.size()-1);
            }
        }
}
点击复制链接 与好友分享!回本站首页
上一篇:------区间DP hdu 5115 - Dire Wolf
下一篇:Leetcode 148 - Sort List(分治法)
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站