代码随想录算法训练营第二十七天|39.组合总和、40.组合总和II、131.分割回文串

39.组合总和

思路:

本题和77.组合 ,216.组合总和III的区别是:本题没有数量要求,可以无限重复,但是有总和的限制,所以间接的也是有个数的限制。

本题搜索的过程抽象成树形结构如下:

39.组合总和

注意图中叶子节点的返回条件,因为本题没有组合数量要求,仅仅是总和的限制,所以递归没有层数的限制,只要选取的元素总和超过target,就返回!

而在77.组合和216.组合总和III中都可以知道要递归K层,因为要取k个元素的组合。

剪枝优化:

在这个树形结构中:

39.组合总和

以及上面的版本一的代码大家可以看到,对于sum已经大于target的情况,其实是依然进入了下一层递归,只是下一层递归结束判断的时候,会判断sum > target的话就返回。

其实如果已经知道下一层的sum会大于target,就没有必要进入下一层递归了。

那么可以在for循环的搜索范围上做做文章了。

对总集合排序之后,如果下一层的sum(就是本层的 sum + candidates[i])已经大于target,就可以结束本轮for循环的遍历

39.组合总和1

代码:

未剪枝优化

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        result = [] # 初始化一个空列表,用于存储所有满足条件的组合
        path = [] # 初始化一个空列表,用于存储当前正在构建的组合
        self.backtracking(candidates, target, 0, 0, path, result) # 调用回溯函数开始搜索
        return result # 返回所有满足条件的组合

    def backtracking(self, candidates, target, total, startIndex, path, result):
        if total > target: # 如果当前组合的总和大于目标值,返回上一层
            return
        if total == target: # 如果当前组合的总和等于目标值,则将该组合添加到结果列表中
            result.append(path[:]) # 注意这里使用了切片操作,是为了避免直接添加path的引用,从而确保添加到result中的是组合的一个副本
            return

        for i in range(startIndex, len(candidates)): # 从startIndex开始遍历candidates数组
            total += candidates[i] # 将当前数字添加到当前组合的总和中
            path.append(candidates[i]) # 将当前数字添加到当前正在构建的组合中
            self.backtracking(candidates, target, total, i, path, result) # 递归调用回溯函数,继续搜索。startIndex不用i+1了,表示可以重复使用相同的数
            total -= candidates[i] # 回溯,将当前数字从当前组合的总和中减去
            path.pop() # 回溯,将当前数字从当前正在构建的组合中移除

剪枝优化 

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        result = []
        path = []
        candidates.sort() # 需要排序
        self.backtracking(candidates, target, 0, 0, path, result)
        return result

    def backtracking(self, candidates, target, total, startIndex, path, result):
        if total == target:
            result.append(path[:])
            return

        for i in range(startIndex, len(candidates)):
            if total + candidates[i] > target: # 剪枝操作
                break
            total += candidates[i]
            path.append(candidates[i])
            self.backtracking(candidates, target, total, i, path, result)
            total -= candidates[i]
            path.pop()
  • 时间复杂度: O(n * 2^n),注意这只是复杂度的上界,因为剪枝的存在,真实的时间复杂度远小于此
  • 空间复杂度: O(target)

40. 组合总和 II

思路:

本题的难点在于:集合(数组candidates)有重复元素,但还不能有重复的组合

一些同学可能想了:我把所有组合求出来,再用set或者map去重,这么做很容易超时!所以要在搜索的过程中就去掉重复组合。

所谓去重,其实就是使用过的元素不能重复选取。

都知道组合问题可以抽象为树形结构,那么“使用过”在这个树形结构上是有两个维度的,一个维度是同一树枝上使用过,一个维度是同一树层上使用过。

回看一下题目,元素在同一个组合内是可以重复的,怎么重复都没事,但两个组合不能相同。

所以我们要去重的是同一树层上的“使用过”,同一树枝上的都是一个组合里的元素,不用去重

为了理解去重我们来举一个例子,candidates = [1, 1, 2], target = 3,(方便起见candidates已经排序了)强调一下,树层去重的话,需要对数组排序!

选择过程树形结构如图所示:

40.组合总和II

直接用startIndex来去重也是可以的, 就不用used数组了 

 if i > startIndex and candidates[i] == candidates[i - 1]

 可以让同一层级,不出现相同的元素(就是重复出现的只保留最左侧的一支树枝,其他的就去重)

代码:

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        result = [] # 初始化结果列表,用于存放所有可能的组合
        path = [] # 初始化当前路径列表,用于构建当前的组合
        candidates.sort() # 对候选数字列表进行排序,以便处理重复数字时能够跳过它们
        self.backtracking(candidates, target, 0, 0, path, result) # 调用回溯方法开始搜索所有可能的组合
        return result # 返回所有有效的组合列表
    
    def backtracking(self, candidates, target, total, startIndex, path, result):
        if total == target: # 如果当前路径的总和等于目标值,则将当前路径添加到结果列表中
            result.append(path[:])
            return

        for i in range(startIndex, len(candidates)): # 遍历候选数字列表,从startIndex开始
            if i > startIndex and candidates[i] == candidates[i - 1]: # 去重。如果当前数字和前一个数字相同,并且不是第一个数字,则跳过,以避免重复的组合
                continue
            if total + candidates[i] > target: # 剪枝。如果加上当前数字后的总和已经超过了目标值,则结束循环
                break
            total += candidates[i] # 将当前数字添加到当前组合的总和中
            path.append(candidates[i]) # 将当前数字添加到当前正在构建的组合中
            self.backtracking(candidates, target, total, i + 1, path, result) # 递归调用回溯函数,继续搜索。更新startIndex为i+1,确保不会重复使用相同的数字
            total -= candidates[i] # 回溯,将当前数字从当前组合的总和中减去
            path.pop() # 回溯,将当前数字从当前正在构建的组合中移除
  • 时间复杂度: O(n * 2^n)
  • 空间复杂度: O(n)

131. 分割回文串

思路:

本题这涉及到两个关键问题:

  1. 切割问题,有不同的切割方式
  2. 判断回文

这种题目,想用for循环暴力解法,可能都不那么容易写出来,所以要换一种暴力的方式,就是回溯。 

一些同学可能想不清楚 回溯究竟是如何切割字符串呢?

我们来分析一下切割,其实切割问题类似组合问题

例如对于字符串abcdef:

  • 组合问题:选取一个a之后,在bcdef中再去选取第二个,选取b之后在cdef中再选取第三个.....。
  • 切割问题:切割一个a之后,在bcdef中再去切割第二段,切割b之后在cdef中再切割第三段.....。

所以切割问题,也可以抽象为一棵树形结构,如图:

131.分割回文串

递归用来纵向遍历,for循环用来横向遍历,切割线(就是图中的红线)切割到字符串的结尾位置,说明找到了一个切割方法。

此时可以发现,切割问题的回溯搜索的过程和组合问题的回溯搜索的过程是差不多的。

 

代码:

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        result = [] # 初始化一个空列表,用于存储所有可能的回文子串组合
        path = [] # 初始化一个空列表,用于在回溯过程中存储当前的回文子串组合
        self.backtracking(s, 0, path, result) # 调用回溯方法开始搜索
        return result # 返回所有可能的回文子串组合
    
    def backtracking(self, s, start_index, path, result ):
        if start_index == len(s): # 如果已经遍历(切割)到字符串的末尾
            result.append(path[:]) # 将当前的回文子串组合添加到结果列表中(注意这里使用了path的副本,避免后续修改影响结果)
            return # 结束递归,返回上一层
        
        for i in range(start_index, len(s)): # 从start_index开始遍历字符串的剩余部分
            if s[start_index: i + 1] == s[start_index: i + 1][::-1]: # 检查从start_index到i的子串是否是回文
                path.append(s[start_index:i+1]) # 如果是回文,则将其添加到当前的回文子串组合中
                self.backtracking(s, i+1, path, result) # 递归调用,从下一个位置继续搜索。注意切割过的位置,不能重复切割,所以,backtracking(s, i + 1); 传入下一层的起始位置为i + 1。
                path.pop() # 回溯,移除最后一个添加的回文子串,尝试其他可能的组合

时间复杂度:O(N * 2 ^ N),因为总共有O(2^N)种分割方法,每次分割都要判断是否回文需要 O(N) 的时间复杂度。
空间复杂度:O(2 ^ N),返回结果最多有O(2 ^ N)种划分方法。

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/546615.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

《HF经理》:二认知误区

一、管理者掌握重要权力: 二、全力来自管理者的职位: 三、管理者必须控制自己的直接下属: 对策:展示自己的品质,能力和影响力 四、管理者必须建立良好的个人关系: 五、管理这必须确保一切运行正常&…

【爬虫开发】爬虫从0到1全知识md笔记第5篇:Selenium课程概要,selenium的其它使用方法【附代码文档】

爬虫开发从0到1全知识教程完整教程(附代码资料)主要内容讲述:爬虫课程概要,爬虫基础爬虫概述,,http协议复习。requests模块,requests模块1. requests模块介绍,2. response响应对象,3. requests模块发送请求,4. request…

分享2024 golang学习路线

写在前面 Go语言(也称为Golang)是Google开发的一种静态强类型、编译型语言,它具有简洁、快速、安全、并发等特点,尤其适合构建大型软件、微服务架构和云平台服务。Go的学习曲线相对平缓,社区活跃,是现代编…

韩顺平 | 零基础快速学Python(16) 文件处理

文件 输入与输出 输入:数据从数据源(文件)到程序(内存); 输出:数据从程序(内存)到数据源(文件)。 #mermaid-svg-06PG6JZq4jJMV1oH {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-sv…

五、LoadBalancer负载均衡服务调用

一、Ribbon目前也进入维护模式 1、是什么 Spring Cloud Ribbon是基于Netflix Ribbon实现的一套客户端负载均衡的工具。 简单的说,Ribbon是Netflix发布的开源项目,主要功能是提供客户端的软件负载均衡算法和服务调用。Ribbon客户端组件提供一系列完善的…

掌握CRM+邮箱技巧:销售速度与客户信任双丰收

在千行百业都在谈提效的今天,如果您的销售团队效率较低,恐怕很难过好2024。销售团队提效是个大话题,总的说来就是销售团队需要在正确的时间做正确的事。如何做到?自然要借助CRM工具。过去我们也讲了不少CRM如何辅助销售团队提效的…

Playwright已经是目前最好的测试自动化工具了吗?

作者观点:很长时间以来,Selenium是QA工程师寻求测试自动化解决方案的首选测试框架。它能够测试任何浏览器(这在IE浏览器的统治时期尤其重要)和任何平台。然而,现在看来,那个时代已经过去了。 今天&#xf…

Python机器学习实战教程

一、引言 机器学习是人工智能的一个子集,它使用算法来让计算机系统从数据中“学习”并改进其性能,而无需进行明确的编程。Python因其易于学习、强大的库和广泛的应用场景,成为了机器学习的首选语言。本教程旨在帮助读者从零开始学习Python机…

APP开发突增20倍!安卓和鸿蒙你站哪边?

随着科技的快速发展,智能设备已经成为我们生活中不可或缺的一部分。 根据不少业内人士爆料,今年9月华为将发布mate70系列,而同时华为自己也官宣了"鸿蒙星河版",也就是原生鸿蒙系统,将于今年4季度商用。这很…

31、链表-K个一组反转链表

思路: 首先知道如何反转链表,其次找出每组的开始节点和结束节点,然后对于不足与k个的链表保持原状。 代码如下: class Solution {public ListNode reverseKGroup(ListNode head, int k) {if (headnull||k1){return head;}ListN…

家居网购项目(Ajax验证用户名+上传图片)

文章目录 1.Ajax验证用户名1.程序框架图2.修改MemberServlet3.修改login.jsp4.结果展示 2.Ajax判断验证码是否输入正确1.修改MemberServlet2.修改login.jsp3.结果展示 3.Ajax添加购物车1.程序框架图2.修改CartServlet2.修改index.jsp3.解决问题—未登录直接添加购物车&#xff…

每日一题---OJ题: 有效的括号

片头 嗨! 小伙伴们,大家好! 我们又见面啦! 今天我们来一起尝试一下这道题目---有效的括号,准备好了吗? 我们开始咯! 说实话,我刚开始做这道题的时候也是一脸懵,怎么进行括号匹配呢? 别慌,我们一起画个图,分析分析括号匹配的过程~ 如下图所示,上方表示一个字符串数组,存放不…

【C++】力扣OJ题:找出只出现一次的数字

Hello everybody!这是我第一次写关于OJ题目的博客,因为正好学到完了C的STL库,就顺手刷了一些OJ题。 我今天要介绍的题目虽然是力扣上的简单题,但思想很巧妙,我觉得有必要和大家分享一下! 1.题目 2.代码 class Solut…

【Go】原子并发操作

目录 一、基本概念 支持的数据类型 主要函数 使用场景 二、基础代码实例 开协程给原子变量做加法 统计多个变量 原子标志判断 三、并发日志记录器 四、并发计数器与性能监控 五、优雅的停止并发任务 worker函数 Main函数 应用价值 Go语言中,原子并发操…

飞机飞行数据三维可视化管控系统更智能、精准

近年来,随着无人化工厂和智能工厂在中国大量涌现,基于成熟的数字孪生理念,智能工厂三维可视化虚拟管控系统引领未来工业革命的先锋。数字孪生公司深圳华锐视点结合前沿的三维仿真、GIS和三维可视化技术技术,深度集成工厂生产、经营…

鸿蒙 Failed :entry:default@CompileResource...

Failed :entry:defaultCompileResource... media 文件夹下有文件夹或者图片名称包含中文字符 rawfile 文件夹下文件名称、图片名称不能包含中文字符

IGBT退饱和现象解析与防范

IGBT是一种重要的功率半导体器件,广泛应用于电力电子领域,如变频器、电动机驱动、电力传输等。在这些应用中,IGBT的导通和关断特性至关重要,而退饱和是IGBT工作过程中的一个重要现象。 IGBT的退饱和定义 退饱和是指IGBT在导通状态…

软件测试面试题分享(含答案+文档)

🍅 视频学习:文末有免费的配套视频可观看 🍅 点击文末小卡片,免费获取软件测试全套资料,资料在手,涨薪更快 准备找工作的小伙伴们,今天我给大家带来了一些自动化测试面试题,在这个公…

NLP vs. LLMs: 理解它们之间的区别

作者:Elastic Platform Team 随着人工智能持续发展并在无数行业解决问题,技术的一个关键部分是能够无缝地桥接人类语言和机器理解之间的差距。这就是自然语言处理(NLP)和大型语言模型(LLMs)的用武之地。它们…

运用OSI模型提升排错能力

1. OSI模型有什么实际的应用价值? 2. 二层和三层网络的区别和应用; 3. 如何通过OSI模型提升组网排错能力? -- OSI - 开放式系统互联 - 一个互联标准 - 从软件和硬件 定义标准 - 不同厂商的设备 研发的技术 - 具备兼容性 -- O…