组合总和(python3) - 编程思维

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

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

解题思路:我使用的是笨办法,找出该数组满足target的全排列,再插入解集前,判断该排列是否在解集中存在,如果存在,不插入。全排列的求解查看全排列(Python3)

代码如下( ̄▽ ̄):

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        self.re = []
        self.target = target
        self.candidates = candidates
        self.sub_combinationSum(target,[])
        return self.re
    
    def sub_combinationSum(self,target,temp):
        if target<0:
            return
        if target==0:
            temp.sort()
            if temp not in self.re:
                self.re.append(temp)
        else:
            for i in self.candidates:
                self.sub_combinationSum(target-i,temp+[i])

时间与空间复杂度:

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/probl...

版权声明:本文版权归作者所有,遵循 CC 4.0 BY-SA 许可协议, 转载请注明原文链接
https://segmentfault.com/a/1190000020851953

爬楼梯(python3) - 编程思维

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?注意:给定 n 是一个正整数。 示例 1:输入: 2输出: 2解释: 有两种方法可以爬到楼顶。1 阶 + 1 阶 和 2 阶 解题思路:实现了两种方法,但是第一种超出时间限制(。ì _ í。),因为递归的

机器学习汇总 - 编程思维

机器学习汇总 介绍 本模块包含自己学习机器学习过程中学习过的内容,包含基础案例和实战案例,大部分以ipynb的格式展示,包含数据集和源代码,可以下载使用练习,包含机器学习的常见算法,如逻辑斯蒂回归,决策树,支持向量机,集成算法,贝叶斯,聚类等等。 由于包含数据集内容比较大,鉴于网速没有上传到github,而且码云自带i

python3网络爬虫开发实战之使用代理爬取微信公众号文章 - 编程思维

1.本节目标我们的主要目标是利用代理爬取微信公众号的文章,提取正文、发表日期、公众号等内容,爬取来源是搜狗微信,其链接为 http://weixin.sogou.com/,然后把爬取结果保存到 MySQL 数据库。 2.准备工作首先需要准备并正常运行前文中所介绍的代理池。这里需要用的 Python 库有 aiohttp

全排列(python3) - 编程思维

题目描述:给定一个没有重复数字的序列,返回其所有可能的全排列。 示例:输入: [1,2,3]输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] 解题思路: 代码如下: class Solution: def permute(self, nums: List[

爬楼梯(python3) - 编程思维

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?注意:给定 n 是一个正整数。 示例 1:输入: 2输出: 2解释: 有两种方法可以爬到楼顶。1 阶 + 1 阶 和 2 阶 解题思路:实现了两种方法,但是第一种超出时间限制(。ì _ í。),因为递归的

不同路径(python3) - 编程思维

问题描述:一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。问总共有多少条不同的路径? 示例:输入: m = 3, n = 2输出: 3解释:从左上角开始,总共有 3 条路径可以到达右

解码方法(python3) - 编程思维

问题描述:一条包含字母 A-Z 的消息通过以下方式进行了编码: 'A' -> 1'B' -> 2...'Z' -> 26 给定一个只包含数字的非空字符串,请计算解码方法的总数。 示例 1:输入: "12"输出: 2解释: 它可以解码为 "AB"(1 2)或者 "L"(12)。示例 2:输入: "226

全排列(python3) - 编程思维

题目描述:给定一个没有重复数字的序列,返回其所有可能的全排列。 示例:输入: [1,2,3]输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] 解题思路: 代码如下: class Solution: def permute(self, nums: List[

电话号码的字母组合(python3) - 编程思维

题目描述:给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。给出数字到字母的映射如下(与电话按键相同)。注意1不对应任何字母。示例:输入:"23"输出:["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]说明:尽管上面的答案是按字典序排列的,但是你

最长回文子串(python3) - 编程思维

问题描述:给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。示例:输入: "babad"输出: "bab"注意: "aba" 也是一个有效答案。 解决思路:从字符串的第一个字符开始遍历到最后一个字符,判断该字符到第一个字符的子串是否为回文,设立变量更新最长的回文子串长度。 代码如下