上周一道算法题(五十八)

最近项目上线，周末还要上课，上周就没写，这周先把上周的补上，然后下周做两道就行。当然，如果遇上'Hard'级别的我也不做，嘿嘿。。。

题目：给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。eg：n = 4, k = 2，输出[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]].

思路：这题做了好久，还是小伙伴说了用DFS算法以后，做了好久，其实就是从1开始遍历，以上面的n=4，k=2为例，如下表：

k=1	k=0
n从1遍历	2
	3
	4
n从2遍历	3
	4
n从3遍历	4

当k=0的时候将结果记录，全部遍历完返回即可，下面看代码：

class Solution(object):
    def combine(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: List[List[int]]
        """
        # 自定义的dfs
        def dfs(begin, end, k, temp, result):
            > if k: #如果k不等于0就遍历，遍历的范围是begin至end
                for i in range(begin,end):
                    if (end - i + 1 < k): break #剪枝
                    temp.append(i)
                    dfs(i + 1, end, k - 1, temp, result)
                    del temp[-1] #k不等于0需要删掉末尾的数继续完成遍历
            else:#k=0时记录
                one = []
                for i in temp:
                    one.append(i)
                result.append(one)#将深拷贝的结果记录下来
        #定义结果
        result = []
        #调用方法，参数分别是：遍历的起点/终点/k/单个数组/数组集合
        dfs(1, n+1, k, [], result)
        #返回结果
        return result

效率还行，但总觉得那个深拷贝的地方可以简化，以后有时间再优化。都说ptyhon强大，然后让大伙看下python的强大之处：

class Solution(object):
    def combine(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: List[List[int]]
        """
        from itertools import combinations
        return list(combinations(xrange(1, n + 1), k))

好吧，python自身就带了这个算法，只要把参数传进去，就ok了,另外xrange比range性能好。。。

版权声明：本文为 Crazy Steven 原创出品，欢迎转载，转载时请注明出处!