Blog

leetcode39组合总和

leetcode39 Combination Sum

Posted by BY on May 7, 2019

前言

新的一年，好好学习。

正文

问题来源

本问题来自leetcode上的39题。

问题描述

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明：
所有数字（包括 target）都是正整数。
解集不能包含重复的组合。

示例 1：

输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
  [7],
  [2,2,3]
]

示例 2：

输入: candidates = [2,3,5], target = 8,
所求解集为:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

分析：

回溯法，水题。
要注意的是要去重（根据添加到单条结果中元素下标来去重）

func combinationSum(candidates []int, target int) [][]int {
    tmp := make([]int, 0)
    res := make([][]int, 0)
    dfs(candidates, tmp, &res, target, 0)
    return res
}

func dfs(candidates []int, tmp []int, res *[][]int, target int, index int) {
    if target < 0 {
        return 
    } else if target == 0 {
        t := append([]int{}, tmp...)
        *res = append(*res, t)
    }
    for i := index; i < len(candidates); i++ {
        dfs(candidates, append(tmp, candidates[i]), res, target - candidates[i], i)
    }
}

效率打败了百分之五十多的人。需要思考优化的地方。

非递归版本

class Solution(object):
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        candidates, res, stack, lenth=sorted(set(candidates)), [], [(0, [], target)], len(candidates)
        while stack:
            i, temp, tar=stack.pop()
            while i<lenth and tar>0:
                if candidates[i]==tar: res+=temp+[candidates[i]],
                stack+=(i, temp+[candidates[i]], tar-candidates[i]),
                i+=1
        return res

要注意的是if和接下来的一样中的’,’，这个不能少。Python中定义[]并不确定列表内存入的数据是什么类型，默认的list a与list b做+=操作会将list b中的元素加到list a中；若想将list b作为元素加入到list a中需要该操作末尾加上’,’逗号。 而+=(element1,element)这种不加逗号的会默认是将多个元素分别加入list列表中，若想加入tuple，则也是需要加上’,’。

总结：

勤思考。
Python中逗号的三个用法 1.逗号在参数传递中的使用：
这种情况不多说,没有什么不解的地方 就是形参或者实参传递的时候参数之间的逗号
例如def abc(a,b)或者abc(1,2)

2.逗号在类型转化中的使用(主要是元组的转换)，例如:

>>> a=11
>>> b=(a)
>>> b
11
>>> b=(a,)
>>> b
(11,)
>>> b=(a,22)
>>> b
(11, 22)
>>> b=(a,22,)
>>> b
(11, 22)

a = [1,2,3]
b = [5,6,7]
c = a + b
d = a + b,
a += b,
print(c)
print(d)
print(a)
输出
[1, 2, 3, 5, 6, 7]
([1, 2, 3, 5, 6, 7],)
[1, 2, 3, [5, 6, 7]]

从中可以看出 只有当b元组中只有一个元素的时候 需要逗号来转换为元组类型

3.逗号在输出语句print中的妙用,例子:

>>> for i in range(0,5):
...     print i
...
0
1
2
3
4
>>> for i in range(0,5):
...     print i,
...
0 1 2 3 4
  1. 解包 ``` a = (1,2,3) _, b, _ = a print(b)

d = [1,2,3,4] _, e, _, _ = d print(e)

def f(): return 1,2 c, _ = f() print(c) 输出 2 2 1 ```

结语

不管怎么样好好加油。

CATALOG
    FEATURED TAGS
    Blog