一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1106|回复: 15
收起左侧

[算法题] 组合数 DFS的两种解法哪种更好?求解~

[复制链接] |试试Instant~ |关注本帖
baojialiang 发表于 2014-1-7 10:39:10 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
关于leetcode上DFS的一道题目,给一个K,一个N,找出1 - N的所有组合数,个数为K。这题是用DFS来解的,但是目前小弟写出两个DFS解法,我不知道这两个解法 到底是哪个更加好一点。直觉告诉我第一个分支更少,会比较好,但是运行下来 两个相差无几 甚至分之多的那个解法目测更加快一点,有点晕。。求教一下,这到底可以怎么分析?一般做题的时候 哪种更加符合思维呢?

第一个解法的意思就是可以选当前的元素,或者不选。所以两个分支。
第二个解法的意思就是选当前的元素,然后依次选下一个(不选之前的元素了)。所以分支挺多的。

解法附上:

    public ArrayList<ArrayList<Integer>> combine(int n, int k) {
        ArrayList<ArrayList<Integer>> coll = new ArrayList<ArrayList<Integer>>();
        if(n > 0){
            dfs(1, n, k, new ArrayList<Integer>(), coll);
        }
        return coll;
    }


解法一:
    public void dfs(int low, int high, int count, ArrayList<Integer> list ,ArrayList<ArrayList<Integer>> coll){
        if(high - low + 1 < count){
            return;
        }
        if(count == 0){
            coll.add(new ArrayList<Integer>(list));
            return;
        }
        // this element is not selected
        dfs(low + 1, high, count, list, coll);

        // this element is selected
        list.add(low);
        dfs(low + 1, high, count - 1, list, coll);
        list.remove(list.size() - 1);
    }


解法二:
    public void dfs(int low, int high, int count, ArrayList<Integer> list ,ArrayList<ArrayList<Integer>> coll){
        if(high - low  + 1 < count){
            return;
        }
        if(count == 0){
            ArrayList<Integer> newList = new ArrayList<Integer>();
            newList.addAll(list);
            coll.add(newList);
        }
        for(int i = low; i <= high; i++){
            list.add(i);
            dfs(i + 1, high, count - 1, list, coll);
            list.remove(list.size() - 1);
        }
    }

kelvinzhong 发表于 2014-1-7 12:10:06 | 显示全部楼层
我是用第二种的,我觉得两种都一样吧?
回复 支持 反对

使用道具 举报

 楼主| baojialiang 发表于 2014-1-7 12:59:15 | 显示全部楼层

貌似递归树不太一样哦
第二个解法具体是怎么理解的呢? 我的理解就是 选择当前的元素,然后依次选择下一个,之前选过的就当是不选了。每个状态下面就当做有n个vertex需要进行遍历。

我是这么想的,这样理解对吗?
回复 支持 反对

使用道具 举报

readman 发表于 2014-1-7 13:05:06 | 显示全部楼层
第一种是题解,就是用在这题上的解法。
第二种是数字排列题的通解的变形。

第一种比较思路清晰。
但是面试我会用第二种,因为第二种记住后,可以面对各种衍生问题。 比如:指定数不重复等
回复 支持 反对

使用道具 举报

 楼主| baojialiang 发表于 2014-1-7 14:03:16 | 显示全部楼层
readman 发表于 2014-1-7 13:05
第一种是题解,就是用在这题上的解法。
第二种是数字排列题的通解的变形。

确实,相比第一个解法,总觉得第二个解法 很奇怪,递归树画的不清不楚的。还有一种题目就是求出一个数组所有的subsets,也可以用这两种解法做。
对于第二种解法,是不是就可以理解成,每到一个状态,依次遍历它当前所能选择到的元素(这些元素可以当做图论中下一个需要遍历的vertex)
这样的理解是正常的思维吗?
回复 支持 反对

使用道具 举报

readman 发表于 2014-1-7 15:24:04 | 显示全部楼层
baojialiang 发表于 2014-1-7 14:03
确实,相比第一个解法,总觉得第二个解法 很奇怪,递归树画的不清不楚的。还有一种题目就是求出一个数组所 ...

对的
第二种方法更接近于图论中的
回复 支持 反对

使用道具 举报

 楼主| baojialiang 发表于 2014-1-9 11:46:46 | 显示全部楼层
readman 发表于 2014-1-7 15:24
对的
第二种方法更接近于图论中的

嗯啊 不过像求所有subsets的问题,第二种方法的时间复杂度是多少呢?所有子集一共2^n个,
我总觉得如果用第二个方法的话,时间复杂度是n!,因为第一层有n个选择,第二层有n - 1个选择,最后一层只有1个选择,这样的话就是n!的复杂度吧。这样的分析对吗?我想了半天觉得是对的,但又觉得应该是2^n的复杂度。
回复 支持 反对

使用道具 举报

readman 发表于 2014-1-9 12:36:50 | 显示全部楼层
第二个是2^n。因为每层迭代不会都走完
回复 支持 反对

使用道具 举报

xiaoma318 发表于 2014-1-9 13:06:50 | 显示全部楼层
第二种好理解很多吧,因为combine不讲顺序,所以只能按照一定order取排列,复杂度就是组合数的复杂度,n!/((n-k)!*k!),你返回的答案有这么多个组合数,复杂度不会小于这个。下面是我的code。
public ArrayList<ArrayList<Integer>> combine(int n, int k) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
       ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
                if(k==0){
                        res.add(new ArrayList<Integer>());
                        return res;
                }
                for(int i=n;i>0;i--){
                        for(ArrayList<Integer>list:combine(i-1,k-1)){
                                list.add(i);
                                res.add(list);
                        }
                }
                return res;
    }
回复 支持 反对

使用道具 举报

 楼主| baojialiang 发表于 2014-1-9 22:51:56 | 显示全部楼层
readman 发表于 2014-1-9 12:36
第二个是2^n。因为每层迭代不会都走完

嗯 能解释下为什么是2^n吗? 在subsets这个题里,虽然我知道所有的子集个数是2^n,我也画出了递归树,确实是2^n个状态,但是怎么从递归树上面来分析时间复杂度呢?还是就是因为子集的个数是2^n,才推出复杂度是2^n?
我在下面画了递归树,假设有4个元素,1,2,3,4

                               
登录/注册后可看大图
回复 支持 反对

使用道具 举报

readman 发表于 2014-1-9 23:08:40 | 显示全部楼层
baojialiang 发表于 2014-1-9 22:51
嗯 能解释下为什么是2^n吗? 在subsets这个题里,虽然我知道所有的子集个数是2^n,我也画出了递归树,确实 ...

...你的图是个X
回复 支持 反对

使用道具 举报

 楼主| baojialiang 发表于 2014-1-9 23:27:09 | 显示全部楼层
readman 发表于 2014-1-9 23:08
...你的图是个X

不知道为啥dropbox 在这里显示不出来,右键可以打开
回复 支持 反对

使用道具 举报

readman 发表于 2014-1-9 23:30:39 | 显示全部楼层
baojialiang 发表于 2014-1-9 23:27
不知道为啥dropbox 在这里显示不出来,右键可以打开

而且你不是已经知道迭代后递归的次数是2^n了么..
回复 支持 反对

使用道具 举报

 楼主| baojialiang 发表于 2014-1-9 23:41:04 | 显示全部楼层
readman 发表于 2014-1-9 23:30
而且你不是已经知道迭代后递归的次数是2^n了么..

就是画出来递归树后 数出来是2^n个递归的次数,不太清楚怎么分析的。特别是每个节点的children个数都不一样,唉。。
回复 支持 反对

使用道具 举报

readman 发表于 2014-1-9 23:43:40 | 显示全部楼层
baojialiang 发表于 2014-1-9 23:41
就是画出来递归树后 数出来是2^n个递归的次数,不太清楚怎么分析的。特别是每个节点的children个数都不一 ...

具体个数不用看吧..看数量级
回复 支持 反对

使用道具 举报

readman 发表于 2014-1-9 23:44:20 | 显示全部楼层
baojialiang 发表于 2014-1-9 23:41
就是画出来递归树后 数出来是2^n个递归的次数,不太清楚怎么分析的。特别是每个节点的children个数都不一 ...

起码我觉得数量级不会是n! 吧...
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-6 14:22

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表