当前位置: 首页 > news >正文

算法打卡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

思路:

  1. 定义一个回溯函数 backtrack,它接受两个参数:start 表示从候选数字列表中的哪个位置开始搜索,div 表示目标值与当前路径数字之差。

  2. 在回溯函数中,首先判断终止条件:

    • 如果 div 等于 0,说明当前路径上的数字组合的和等于目标值,将当前组合添加到结果列表中并返回。
    • 如果 div 小于 0,说明当前路径上的数字组合的和已经超过目标值,不再继续搜索,直接返回。
  3. 然后,使用一个循环遍历候选数字列表中的数字,从 start 位置开始:

    • 将当前数字添加到当前路径中。
    • 递归调用 backtrack 函数,传入更新后的 start 位置和更新后的 div 值(减去当前数字)。
    • 递归调用结束后,回溯,将当前数字从当前路径中移除。
  4. 最终,当所有可能的组合都搜索完毕后,返回结果列表。

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

思路:

这一题难一点

  1. 我们可以使用回溯算法来生成所有可能的分割方案。
  2. 在每一步中,我们可以从当前位置开始向右扩展,检查以当前位置开头的所有子串是否为回文串。
  3. 如果是回文串,我们将该子串添加到当前路径中,并递归地处理剩余部分。
  4. 当处理到字符串末尾时,将当前路径添加到结果中。

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

今日任务&#xff1a; 1&#xff09;39. 组合总和 2&#xff09;40.组合总和II 3&#xff09;131.分割回文串 39. 组合总和 题目链接&#xff1a;39. 组合总和 - 力扣&#xff08;LeetCode&#xff09; 给定一个无重复元素的数组 candidates 和一个目标数 target &#xff0c;…...

每天五分钟深度学习:神经网络和深度学习有什么样的关系?

本文重点 神经网络是一种模拟人脑神经元连接方式的计算模型&#xff0c;通过大量神经元之间的连接和权重调整&#xff0c;实现对输入数据的处理和分析。而深度学习则是神经网络的一种特殊形式&#xff0c;它通过构建深层次的神经网络结构&#xff0c;实现对复杂数据的深度学习…...

基于PSO优化的CNN-LSTM-Attention的时间序列回归预测matlab仿真

目录 1.算法运行效果图预览 2.算法运行软件版本 3.部分核心程序 4.算法理论概述 4.1卷积神经网络&#xff08;CNN&#xff09;在时间序列中的应用 4.2 长短时记忆网络&#xff08;LSTM&#xff09;处理序列依赖关系 4.3 注意力机制&#xff08;Attention&#xff09; 5…...

物联网监控可视化是什么?部署物联网监控可视化大屏有什么作用?

随着物联网技术的深入应用&#xff0c;物联网监控可视化成为了企业数字化转型的关键环节。物联网监控可视化大屏作为物联网监控平台的重要组成部分&#xff0c;能够实时展示物联网设备的运行状态和数据&#xff0c;为企业管理决策和运维监控提供了有力的支持。今天&#xff0c;…...

设计一个Rust线程安全栈结构 Stack<T>

在Rust中&#xff0c;设计一个线程安全的栈结构Stack<T>&#xff0c;类似于Channel<T>&#xff0c;但使用栈的FILO&#xff08;First-In-Last-Out&#xff09;原则来在线程间传送数据&#xff0c;可以通过使用标准库中的同步原语如Mutex和Condvar来实现。下面是一个…...

Docker Desktop 在 Windows 上的安装和使用

目录 1、安装 Docker Desktop 2、使用 Docker Desktop &#xff08;1&#xff09;运行容器 &#xff08;2&#xff09;查看容器信息 &#xff08;3&#xff09;数据挂载 Docker Desktop是Docker的官方桌面版&#xff0c;专为Mac和Windows用户设计&#xff0c;提供了一个简…...

2024年最受欢迎的 19 个 VS Code 主题排行榜

博主猫头虎的技术世界 &#x1f31f; 欢迎来到猫头虎的博客 — 探索技术的无限可能&#xff01; 专栏链接&#xff1a; &#x1f517; 精选专栏&#xff1a; 《面试题大全》 — 面试准备的宝典&#xff01;《IDEA开发秘籍》 — 提升你的IDEA技能&#xff01;《100天精通鸿蒙》 …...

突破编程_C++_网络编程(OSI 七层模型(物理层与数据链路层))

1 OSI 七层模型概述 OSI&#xff08;Open Systems Interconnection&#xff09;七层模型&#xff0c;即开放系统互联参考模型&#xff0c;起源于 20 世纪 70 年代和 80 年代。随着计算机网络技术的快速发展和普及&#xff0c;不同厂商生产的计算机和网络设备之间的互操作性成为…...

Spring boot如何使用redis缓存

引入依赖 这个是参照若依的&#xff0c;如果没有统一的版本规定的话&#xff0c;这里是需要写版本号的 <!-- redis 缓存操作 --> <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-data-redis</arti…...

红蓝色WordPress外贸建站模板

红蓝色WordPress外贸建站模板 https://www.mymoban.com/wordpress/5.html...

python爬虫----了解爬虫(十一天)

&#x1f388;&#x1f388;作者主页&#xff1a; 喔的嘛呀&#x1f388;&#x1f388; &#x1f388;&#x1f388;所属专栏&#xff1a;python爬虫学习&#x1f388;&#x1f388; ✨✨谢谢大家捧场&#xff0c;祝屏幕前的小伙伴们每天都有好运相伴左右&#xff0c;一定要天天…...

碳素光线疗法与宠物健康

碳素光线与宠物健康 生息在地球上的所有动物、在自然太阳光奇妙的作用下、生长发育。太阳光的能量使它们不断进化、繁衍种族。现在、生物能够生存、全仰仗于太阳的光线。太阳光线中、包含有动物健康所需要的极为重要的波长。因此、和户外饲养的动物相比、在室内喂养的观赏动物、…...

展锐平台camera添加底层水印

展锐平台camera添加水印&#xff0c;从底层用编码覆盖图像数组&#xff0c;保证上层获取图像水印的一致性 时间水印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应用开发系列课程大纲和章节内容设计

本节笔者会详细介绍下本系统专题的大纲&#xff0c;以及每个专题章节的组织结构。这样读者会有一个全局的概念。 在开始前还是在再介绍一下下面这个框架图&#xff0c;因为比较重要&#xff0c;在这里再冗余介绍一下。开发Apple公司相关产品的软件时&#xff0c;主要有两个框架…...

热门IT【视频教程】-华为/思科/红帽/oracle

华为认证 网络工程师-入门基础课&#xff1a;华为HCIA认证课程介绍-CSDN博客 网络工程师进阶课&#xff1a;华为HCIP认证课程介绍-CSDN博客 职场进阶&#xff0c;踏上高峰——HCIE-Datacom认证-CSDN博客 华为HCIA试听课程 &#xff1a; 超级实用&#xff0c;华为VRP系统文件…...

HCTNet:一种用于乳腺超声图像分割的混合CNN-transformer

HCTNet&#xff1a;一种用于乳腺超声图像分割的混合CNN-transformer 摘要引言相关工作方法 Materials and methods分割方法 HCTNet_ A hybrid CNN-transformer network for breast ultrasound image segmentation 摘要 乳腺超声图像的自动分割有助于提高乳腺癌诊断的准确性。近…...

766. 托普利茨矩阵

给你一个 m x n 的矩阵 matrix 。如果这个矩阵是托普利茨矩阵&#xff0c;返回 true &#xff1b;否则&#xff0c;返回 false 。 如果矩阵上每一条由左上到右下的对角线上的元素都相同&#xff0c;那么这个矩阵是 托普利茨矩阵 。 示例 1&#xff1a; 输入&#xff1a;matr…...

基于STM32的汽车防窒息系统

文章目录 基于STM32的汽车防窒息系统系统简介材料展示视频制作硬件连接原理图PCB实物图GSM模块使用GSM模块代码 SGP30模块SGP30模块代码 步进电机驱动步进电机代码 其他模块主逻辑代码 总结 基于STM32的汽车防窒息系统 系统简介 随着社会的发展目前汽车的流行&#xff0c;汽车大…...

GoogleNet神经网络介绍

一、简介 GoogleNet&#xff0c;也称为GoogLeNet&#xff0c;是谷歌工程师设计的一种深度神经网络结构&#xff0c;它在2014年的ImageNet图像识别挑战赛中取得了冠军。该神经网络的设计特点主要体现在其深度和宽度上&#xff0c;通过引入名为Inception的核心子网络结构&#x…...

AI水下颜色校正解决方案,助力企业打造水下视觉盛宴

水下摄影作为一种独特且富有挑战性的拍摄方式&#xff0c;正受到越来越多旅行者和摄影师的青睐。然而由于海水的光线折射和金属成分的影响&#xff0c;水下拍摄的照片和视频往往存在严重的偏色问题&#xff0c;无法真实还原水下世界的美丽与神奇。美摄科技凭借深厚的技术积累和…...

【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型

摘要 拍照搜题系统采用“三层管道&#xff08;多模态 OCR → 语义检索 → 答案渲染&#xff09;、两级检索&#xff08;倒排 BM25 向量 HNSW&#xff09;并以大语言模型兜底”的整体框架&#xff1a; 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后&#xff0c;分别用…...

idea大量爆红问题解决

问题描述 在学习和工作中&#xff0c;idea是程序员不可缺少的一个工具&#xff0c;但是突然在有些时候就会出现大量爆红的问题&#xff0c;发现无法跳转&#xff0c;无论是关机重启或者是替换root都无法解决 就是如上所展示的问题&#xff0c;但是程序依然可以启动。 问题解决…...

ES6从入门到精通:前言

ES6简介 ES6&#xff08;ECMAScript 2015&#xff09;是JavaScript语言的重大更新&#xff0c;引入了许多新特性&#xff0c;包括语法糖、新数据类型、模块化支持等&#xff0c;显著提升了开发效率和代码可维护性。 核心知识点概览 变量声明 let 和 const 取代 var&#xf…...

基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真

目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销&#xff0c;平衡网络负载&#xff0c;延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...

将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?

Otsu 是一种自动阈值化方法&#xff0c;用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理&#xff0c;能够自动确定一个阈值&#xff0c;将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...

Linux云原生安全:零信任架构与机密计算

Linux云原生安全&#xff1a;零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言&#xff1a;云原生安全的范式革命 随着云原生技术的普及&#xff0c;安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测&#xff0c;到2025年&#xff0c;零信任架构将成为超…...

C# 类和继承(抽象类)

抽象类 抽象类是指设计为被继承的类。抽象类只能被用作其他类的基类。 不能创建抽象类的实例。抽象类使用abstract修饰符声明。 抽象类可以包含抽象成员或普通的非抽象成员。抽象类的成员可以是抽象成员和普通带 实现的成员的任意组合。抽象类自己可以派生自另一个抽象类。例…...

【笔记】WSL 中 Rust 安装与测试完整记录

#工作记录 WSL 中 Rust 安装与测试完整记录 1. 运行环境 系统&#xff1a;Ubuntu 24.04 LTS (WSL2)架构&#xff1a;x86_64 (GNU/Linux)Rust 版本&#xff1a;rustc 1.87.0 (2025-05-09)Cargo 版本&#xff1a;cargo 1.87.0 (2025-05-06) 2. 安装 Rust 2.1 使用 Rust 官方安…...

SQL慢可能是触发了ring buffer

简介 最近在进行 postgresql 性能排查的时候,发现 PG 在某一个时间并行执行的 SQL 变得特别慢。最后通过监控监观察到并行发起得时间 buffers_alloc 就急速上升,且低水位伴随在整个慢 SQL,一直是 buferIO 的等待事件,此时也没有其他会话的争抢。SQL 虽然不是高效 SQL ,但…...

前端开发者常用网站

Can I use网站&#xff1a;一个查询网页技术兼容性的网站 一个查询网页技术兼容性的网站Can I use&#xff1a;Can I use... Support tables for HTML5, CSS3, etc (查询浏览器对HTML5的支持情况) 权威网站&#xff1a;MDN JavaScript权威网站&#xff1a;JavaScript | MDN...