算法打卡day23
今日任务:
1)39. 组合总和
2)40.组合总和II
3)131.分割回文串
39. 组合总和
题目链接:39. 组合总和 - 力扣(LeetCode)
给定一个无重复元素的数组 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] ]
文章讲解:代码随想录 (programmercarl.com)
视频讲解:带你学透回溯算法-组合总和(对应「leetcode」力扣题目:39.组合总和)| 回溯法精讲!哔哩哔哩bilibili
思路:
定义一个回溯函数
backtrack,它接受两个参数:start表示从候选数字列表中的哪个位置开始搜索,div表示目标值与当前路径数字之差。在回溯函数中,首先判断终止条件:
- 如果
div等于 0,说明当前路径上的数字组合的和等于目标值,将当前组合添加到结果列表中并返回。- 如果
div小于 0,说明当前路径上的数字组合的和已经超过目标值,不再继续搜索,直接返回。然后,使用一个循环遍历候选数字列表中的数字,从
start位置开始:
- 将当前数字添加到当前路径中。
- 递归调用
backtrack函数,传入更新后的start位置和更新后的div值(减去当前数字)。- 递归调用结束后,回溯,将当前数字从当前路径中移除。
最终,当所有可能的组合都搜索完毕后,返回结果列表。
class Solution:def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:self.candidates = candidatesself.path = []self.result = []self.backtrack(0, target)return self.resultdef backtrack(self, start, div):# 终止条件if div == 0: # 如果目标值为 0,将当前组合添加到结果列表中并返回self.result.append(self.path[:])returnelif div < 0: # 如果目标值为负数,直接返回,不再继续搜索returnfor i in range(start, len(self.candidates)):self.path.append(self.candidates[i])self.backtrack(i, div - self.candidates[i])self.path.pop()
改进:
我们可以先对列表排序,对于有序列表,剪枝效果更好
我们还可以直接传递path变量,而不是作为成员变量,在传递的过程可以采用隐式回溯
class Solution:def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:candidates.sort()self.candidates = candidatesself.result = []self.backtrack(0, target, [])return self.resultdef backtrack(self, start, div, path):# 终止条件:目标值为 0,将当前组合添加到结果列表中并返回if div == 0:self.result.append(path[:])return# 递归层for i in range(start, len(self.candidates)):# 提前剪枝:如果当前候选数大于目标值,直接跳过if self.candidates[i] > div:break# 递归调用self.backtrack(i, div - self.candidates[i], path + [self.candidates[i]])
40.组合总和II
题目链接:40. 组合总和 II - 力扣(LeetCode)
给定一个候选人编号的集合 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
注意:解集不能包含重复的组合。示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[ [1,1,6],
[1,2,5],
[1,7],
[2,6] ]示例 2:
输入: candidates = [2,5,2,1,2], target = 5,
输出:
[ [1,2,2],
[5] ]提示:
1 <= candidates.length <= 100
1 <= candidates[i] <= 50
1 <= target <= 30
文章讲解:代码随想录 (programmercarl.com)
视频讲解:回溯算法中的去重,树层去重树枝去重,你弄清楚了没?| LeetCode:40.组合总和II哔哩哔哩bilibili
思路:
已经做了上一题,这一题比较简单了,先排序,遍历列表,如果遇到重复的跳过
class Solution:def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:candidates.sort()self.candidates = candidatesself.result = []self.backtrack(0, target, [])return self.resultdef backtrack(self, start, div, path):# 终止条件if div == 0:self.result.append(path[:])returnfor i in range(start, len(self.candidates)):# 提前剪枝:如果当前候选数大于目标值,直接跳过if div < self.candidates[i]:break# 避免重复:如果当前候选数和前一个候选数相同,跳过本次循环if i > start and self.candidates[i] == self.candidates[i - 1]:continueself.backtrack(i + 1, div - self.candidates[i], path + [self.candidates[i]])
131.分割回文串
题目链接:131. 分割回文串 - 力扣(LeetCode)
文章讲解:代码随想录 (programmercarl.com)
视频讲解:带你学透回溯算法-分割回文串(对应力扣题目:131.分割回文串)| 回溯法精讲!哔哩哔哩bilibili
思路:
这一题难一点
- 我们可以使用回溯算法来生成所有可能的分割方案。
- 在每一步中,我们可以从当前位置开始向右扩展,检查以当前位置开头的所有子串是否为回文串。
- 如果是回文串,我们将该子串添加到当前路径中,并递归地处理剩余部分。
- 当处理到字符串末尾时,将当前路径添加到结果中。
class Solution:def partition(self, s: str) -> List[List[str]]:self.s = sself.result = []self.backtrack(0, len(self.s), [])return self.resultdef backtrack(self, start, stop, path):# 终止条件:if start == len(self.s):self.result.append(path[:])return# 从当前位置开始向右扩展,检查以当前位置开头的所有子串是否为回文串for i in range(start,len(self.s)):# 判断以i为切分点,判断i之前(包含i)的字符串是否为回文串substring = self.s[start:i+1]if substring == substring[::-1]:path.append(substring)self.backtrack(i+1,len(self.s),path)path.pop()
感想:这一题后面还要再看看,不是很熟练
相关文章:
算法打卡day23
今日任务: 1)39. 组合总和 2)40.组合总和II 3)131.分割回文串 39. 组合总和 题目链接:39. 组合总和 - 力扣(LeetCode) 给定一个无重复元素的数组 candidates 和一个目标数 target ,…...
每天五分钟深度学习:神经网络和深度学习有什么样的关系?
本文重点 神经网络是一种模拟人脑神经元连接方式的计算模型,通过大量神经元之间的连接和权重调整,实现对输入数据的处理和分析。而深度学习则是神经网络的一种特殊形式,它通过构建深层次的神经网络结构,实现对复杂数据的深度学习…...
基于PSO优化的CNN-LSTM-Attention的时间序列回归预测matlab仿真
目录 1.算法运行效果图预览 2.算法运行软件版本 3.部分核心程序 4.算法理论概述 4.1卷积神经网络(CNN)在时间序列中的应用 4.2 长短时记忆网络(LSTM)处理序列依赖关系 4.3 注意力机制(Attention) 5…...
物联网监控可视化是什么?部署物联网监控可视化大屏有什么作用?
随着物联网技术的深入应用,物联网监控可视化成为了企业数字化转型的关键环节。物联网监控可视化大屏作为物联网监控平台的重要组成部分,能够实时展示物联网设备的运行状态和数据,为企业管理决策和运维监控提供了有力的支持。今天,…...
设计一个Rust线程安全栈结构 Stack<T>
在Rust中,设计一个线程安全的栈结构Stack<T>,类似于Channel<T>,但使用栈的FILO(First-In-Last-Out)原则来在线程间传送数据,可以通过使用标准库中的同步原语如Mutex和Condvar来实现。下面是一个…...
Docker Desktop 在 Windows 上的安装和使用
目录 1、安装 Docker Desktop 2、使用 Docker Desktop (1)运行容器 (2)查看容器信息 (3)数据挂载 Docker Desktop是Docker的官方桌面版,专为Mac和Windows用户设计,提供了一个简…...
2024年最受欢迎的 19 个 VS Code 主题排行榜
博主猫头虎的技术世界 🌟 欢迎来到猫头虎的博客 — 探索技术的无限可能! 专栏链接: 🔗 精选专栏: 《面试题大全》 — 面试准备的宝典!《IDEA开发秘籍》 — 提升你的IDEA技能!《100天精通鸿蒙》 …...
突破编程_C++_网络编程(OSI 七层模型(物理层与数据链路层))
1 OSI 七层模型概述 OSI(Open Systems Interconnection)七层模型,即开放系统互联参考模型,起源于 20 世纪 70 年代和 80 年代。随着计算机网络技术的快速发展和普及,不同厂商生产的计算机和网络设备之间的互操作性成为…...
Spring boot如何使用redis缓存
引入依赖 这个是参照若依的,如果没有统一的版本规定的话,这里是需要写版本号的 <!-- redis 缓存操作 --> <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-data-redis</arti…...
红蓝色WordPress外贸建站模板
红蓝色WordPress外贸建站模板 https://www.mymoban.com/wordpress/5.html...
python爬虫----了解爬虫(十一天)
🎈🎈作者主页: 喔的嘛呀🎈🎈 🎈🎈所属专栏:python爬虫学习🎈🎈 ✨✨谢谢大家捧场,祝屏幕前的小伙伴们每天都有好运相伴左右,一定要天天…...
碳素光线疗法与宠物健康
碳素光线与宠物健康 生息在地球上的所有动物、在自然太阳光奇妙的作用下、生长发育。太阳光的能量使它们不断进化、繁衍种族。现在、生物能够生存、全仰仗于太阳的光线。太阳光线中、包含有动物健康所需要的极为重要的波长。因此、和户外饲养的动物相比、在室内喂养的观赏动物、…...
展锐平台camera添加底层水印
展锐平台camera添加水印,从底层用编码覆盖图像数组,保证上层获取图像水印的一致性 时间水印diff --git a/vendor/sprd/modules/libcamera/hal3_2v6/SprdCamera3HWI.cpp b/vendor/sprd/modules/libcamera/hal3_2v6/SprdCamera3HWI.cpp index f2b704f9d6..…...
OSX-02-Mac OS应用开发系列课程大纲和章节内容设计
本节笔者会详细介绍下本系统专题的大纲,以及每个专题章节的组织结构。这样读者会有一个全局的概念。 在开始前还是在再介绍一下下面这个框架图,因为比较重要,在这里再冗余介绍一下。开发Apple公司相关产品的软件时,主要有两个框架…...
热门IT【视频教程】-华为/思科/红帽/oracle
华为认证 网络工程师-入门基础课:华为HCIA认证课程介绍-CSDN博客 网络工程师进阶课:华为HCIP认证课程介绍-CSDN博客 职场进阶,踏上高峰——HCIE-Datacom认证-CSDN博客 华为HCIA试听课程 : 超级实用,华为VRP系统文件…...
HCTNet:一种用于乳腺超声图像分割的混合CNN-transformer
HCTNet:一种用于乳腺超声图像分割的混合CNN-transformer 摘要引言相关工作方法 Materials and methods分割方法 HCTNet_ A hybrid CNN-transformer network for breast ultrasound image segmentation 摘要 乳腺超声图像的自动分割有助于提高乳腺癌诊断的准确性。近…...
766. 托普利茨矩阵
给你一个 m x n 的矩阵 matrix 。如果这个矩阵是托普利茨矩阵,返回 true ;否则,返回 false 。 如果矩阵上每一条由左上到右下的对角线上的元素都相同,那么这个矩阵是 托普利茨矩阵 。 示例 1: 输入:matr…...
基于STM32的汽车防窒息系统
文章目录 基于STM32的汽车防窒息系统系统简介材料展示视频制作硬件连接原理图PCB实物图GSM模块使用GSM模块代码 SGP30模块SGP30模块代码 步进电机驱动步进电机代码 其他模块主逻辑代码 总结 基于STM32的汽车防窒息系统 系统简介 随着社会的发展目前汽车的流行,汽车大…...
GoogleNet神经网络介绍
一、简介 GoogleNet,也称为GoogLeNet,是谷歌工程师设计的一种深度神经网络结构,它在2014年的ImageNet图像识别挑战赛中取得了冠军。该神经网络的设计特点主要体现在其深度和宽度上,通过引入名为Inception的核心子网络结构&#x…...
AI水下颜色校正解决方案,助力企业打造水下视觉盛宴
水下摄影作为一种独特且富有挑战性的拍摄方式,正受到越来越多旅行者和摄影师的青睐。然而由于海水的光线折射和金属成分的影响,水下拍摄的照片和视频往往存在严重的偏色问题,无法真实还原水下世界的美丽与神奇。美摄科技凭借深厚的技术积累和…...
【Python】 -- 趣味代码 - 小恐龙游戏
文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...
页面渲染流程与性能优化
页面渲染流程与性能优化详解(完整版) 一、现代浏览器渲染流程(详细说明) 1. 构建DOM树 浏览器接收到HTML文档后,会逐步解析并构建DOM(Document Object Model)树。具体过程如下: (…...
python如何将word的doc另存为docx
将 DOCX 文件另存为 DOCX 格式(Python 实现) 在 Python 中,你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是,.doc 是旧的 Word 格式,而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...
Golang——9、反射和文件操作
反射和文件操作 1、反射1.1、reflect.TypeOf()获取任意值的类型对象1.2、reflect.ValueOf()1.3、结构体反射 2、文件操作2.1、os.Open()打开文件2.2、方式一:使用Read()读取文件2.3、方式二:bufio读取文件2.4、方式三:os.ReadFile读取2.5、写…...
Caliper 配置文件解析:fisco-bcos.json
config.yaml 文件 config.yaml 是 Caliper 的主配置文件,通常包含以下内容: test:name: fisco-bcos-test # 测试名称description: Performance test of FISCO-BCOS # 测试描述workers:type: local # 工作进程类型number: 5 # 工作进程数量monitor:type: - docker- pro…...
什么是VR全景技术
VR全景技术,全称为虚拟现实全景技术,是通过计算机图像模拟生成三维空间中的虚拟世界,使用户能够在该虚拟世界中进行全方位、无死角的观察和交互的技术。VR全景技术模拟人在真实空间中的视觉体验,结合图文、3D、音视频等多媒体元素…...
【Linux手册】探秘系统世界:从用户交互到硬件底层的全链路工作之旅
目录 前言 操作系统与驱动程序 是什么,为什么 怎么做 system call 用户操作接口 总结 前言 日常生活中,我们在使用电子设备时,我们所输入执行的每一条指令最终大多都会作用到硬件上,比如下载一款软件最终会下载到硬盘上&am…...
全面解析数据库:从基础概念到前沿应用
在数字化时代,数据已成为企业和社会发展的核心资产,而数据库作为存储、管理和处理数据的关键工具,在各个领域发挥着举足轻重的作用。从电商平台的商品信息管理,到社交网络的用户数据存储,再到金融行业的交易记录处理&a…...
Android写一个捕获全局异常的工具类
项目开发和实际运行过程中难免会遇到异常发生,系统提供了一个可以捕获全局异常的工具Uncaughtexceptionhandler,它是Thread的子类(就是package java.lang;里线程的Thread)。本文将利用它将设备信息、报错信息以及错误的发生时间都…...
Linux安全加固:从攻防视角构建系统免疫
Linux安全加固:从攻防视角构建系统免疫 构建坚不可摧的数字堡垒 引言:攻防对抗的新纪元 在日益复杂的网络威胁环境中,Linux系统安全已从被动防御转向主动免疫。2023年全球网络安全报告显示,高级持续性威胁(APT)攻击同比增长65%,平均入侵停留时间缩短至48小时。本章将从…...


