【leetcode100】路径总和Ⅲ
1、题目描述
给定一个二叉树的根节点 root ,和一个整数 targetSum ,求该二叉树里节点值之和等于 targetSum 的 路径 的数目。 路径 不需要从根节点开始,也不需要在叶子节点结束,但是路径方向必须是向下的(只能从父节点到子节点)。
示例 1:
输入:root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8 输出:3 解释:和等于 8 的路径有 3 条,如图所示。
2、初始思路
2.1 题目分析
计算二叉树中路径和等于给定目标值 targetSum
的路径数量。
2.1.1 前缀和
前缀和是指从根节点到当前节点的路径上所有节点值的累加和。例如:如果路径是 1 -> 2 -> 3,那么前缀和依次为 1、3(1+2)、6(1+2+3)。
前缀和的核心思想是:
如果从根节点到节点 A 的前缀和为 s1,从根节点到节点 B 的前缀和为 s2,那么从节点 A 到节点 B 的路径和就是 s2 - s1。
因此,如果我们想要找到路径和等于 targetSum 的路径,只需要找到满足 s2 - s1 = targetSum 的前缀对 (s1, s2)。
2.1.2 字典存储
哈希表 cnt 用于记录从根节点到当前节点的路径上,各个前缀和出现的次数。它的作用是:
在遍历时,快速检查是否存在一个前缀和 s1,使得 s2 - s1 = targetSum。如果存在这样的 s1,则说明从某个节点到当前节点的路径和等于 targetSum。
具体来说:
cnt[s] 表示前缀和 s 出现的次数。当我们计算到当前节点的前缀和 s2 时,检查 s2 - targetSum 是否在 cnt 中。如果存在,则说明有 cnt[s2 - targetSum] 条路径满足条件。
2.2 思路
使用前缀和+字典存储
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:ans = 0cnt = defaultdict(int)cnt[0] = 1def dfs(node,s):if not node:return#nonlocal用于修改外部函数中的变量nonlocal ans#s 代表从根节点到当前节点的前缀和,cnt[s]表示前缀和为s的个数s += node.valans += cnt[s - targetSum]cnt[s] += 1dfs(node.left,s)dfs(node.right,s)cnt[s] -= 1dfs(root,0)return ans
相关文章:
【leetcode100】路径总和Ⅲ
1、题目描述 给定一个二叉树的根节点 root ,和一个整数 targetSum ,求该二叉树里节点值之和等于 targetSum 的 路径 的数目。 路径 不需要从根节点开始,也不需要在叶子节点结束,但是路径方向必须是向下的(只能从父节点…...
用结构加法3ax+1预测第4点的分布
有1个点在19*19的平面上在某种力的作用下运动,轨迹为 共移动了90步,按照(0,1,2,3),(1,2,3,4),…,&…...
CTF-web: Python YAML反序列化利用
PyYAML存在以下几个特殊标签,如果这些标签被不安全的解析,会造成解析漏洞 从 PyYaml 版本 6.0 开始,load 的默认加载器已切换到 SafeLoader,以降低远程代码执行的风险。更新后易受攻击的是 yaml.unsafe_load 和 yaml.load(input, Loaderyaml.UnsafeLoade…...
JDK-1.8.0_432安装(CentOS7)
目录 1、卸载系统自带JDK 2、下载安装包并解压 3、赋予可执行权限 4、设置环境变量 5、刷新环境变量 6、查看JDK版本 1、卸载系统自带JDK # 查询出自带的jdk rpm -qa | grep jdk rpm -qa | grep java # 将上述命令列出的包依次删除 rpm -e --nodeps xxxxxxx 2、下载…...
OpenGL学习笔记(五):Textures 纹理
文章目录 纹理坐标纹理环绕方式纹理过滤——处理纹理分辨率低的情况多级渐远纹理Mipmap——处理纹理分辨率高的情况加载与创建纹理 ( <stb_image.h> )生成纹理应用纹理纹理单元练习1练习2练习3练习4 通过上一篇着色部分的学习,我们可以…...
【Pytorch和Keras】使用transformer库进行图像分类
目录 一、环境准备二、基于Pytorch的预训练模型1、准备数据集2、加载预训练模型3、 使用pytorch进行模型构建 三、基于keras的预训练模型四、模型测试五、参考 现在大多数的模型都会上传到huggface平台进行统一的管理,transformer库能关联到huggface中对应的模型&am…...
2025年Android开发趋势全景解读
文章目录 一、界面开发:从"手写代码"到"智能拼装"1.1 Jetpack Compose实战进化1.2 淘汰XML布局的三大信号 二、AI融合开发:无需炼丹的普惠智能2.1 设备端AI三大杀手级应用2.2 成本对比:设备端VS云端AI 三、跨平台演进&am…...
Python NumPy(12):NumPy 字节交换、NumPy 副本和视图、NumPy 矩阵库(Matrix)
1 NumPy 字节交换 在几乎所有的机器上,多字节对象都被存储为连续的字节序列。字节顺序,是跨越多字节的程序对象的存储规则。 大端模式:指数据的高字节保存在内存的低地址中,而数据的低字节保存在内存的高地址中,这样的…...
【Vaadin flow 实战】第5讲-使用常用UI组件绘制页面元素
vaadin flow官方提供的UI组件文档地址是 https://vaadin.com/docs/latest/components这里,我简单实战了官方提供的一些免费的UI组件,使用案例如下: Accordion 手风琴 Accordion 手风琴效果组件 Accordion 手风琴-测试案例代码 Slf4j PageT…...
第三篇:模型压缩与量化技术——DeepSeek如何在边缘侧突破“小而强”的算力困局
——从算法到芯片的全栈式优化实践 随着AI应用向移动终端与物联网设备渗透,模型轻量化成为行业核心挑战。DeepSeek通过自研的“算法-编译-硬件”协同优化体系,在保持模型性能的前提下,实现参数量与能耗的指数级压缩。本文从技术原理、工程实…...
搜索与图论复习2最短路
单源最短路---所有边权是正数(Dijkstra算法O(n^2)--稠密图(邻接矩阵)和堆优化的Dijkstra算法O(mlogn)--稀疏图(邻接表)) 或存在负边权(Bellman-ford贝尔曼福特算法O(nm)和SPFA一般O(m) 最坏O(nm) ) 多源最短路---Floyd算法O(n^3) 一、迪杰斯特拉算法(Dijkstra):1…...
redis集群理论详解
一. Redis集群发展历程 本片文章只介绍集群理论知识,不包含Redis集群搭建教程 教程文章请点击docker搭建redis集群(三主三从) 阶段一:单机版Redis 优点: 简单:易于部署和使用,适合小型项目或初期…...
本地缓存~
前言 Caffeine是使用Java8对Guava缓存的重写版本,在Spring Boot 2.0中取而代之,基于LRU算法实现,支持多种缓存过期策略。 以下摘抄于https://github.com/ben-manes/caffeine/wiki/Benchmarks-zh-CN 基准测试通过使用Java microbenchmark ha…...
SpringBoot 整合 SpringMVC:SpringMVC的注解管理
分类: 中央转发器(DispatcherServlet)控制器视图解析器静态资源访问消息转化器格式化静态资源管理 中央转发器: 中央转发器被 SpringBoot 自动接管,不需要我们在 web.xml 中配置: <servlet><servlet-name>chapter2&l…...
YOLO11/ultralytics:环境搭建
前言 人工智能物体识别行业应该已经饱和了吧?或许现在并不是一个好的入行时候。 最近看到了各种各样相关的扩展应用,为了理解它,我不得不去尝试了解一下。 我选择了git里非常受欢迎的yolo系列,并尝试了最新版本YOLO11或者叫它ultr…...
扩散模型(三)
相关阅读: 扩散模型(一) 扩散模型(二) Latent Variable Space 潜在扩散模型(LDM;龙巴赫、布拉特曼等人,2022 年)在潜在空间而非像素空间中运行扩散过程,这…...
探索数学:从起源到未来的无尽旅程
数学的定义与本质 数学,这门古老而又充满魅力的学科,自人类文明诞生之初便如影随形。然而,要精准地定义数学并非易事,不同的学者从各自的视角出发,给出了多样的阐释。 亚里士多德将数学定义为 “数量科学”ÿ…...
OpenAI发布o3-mini:免费推理模型,DeepSeek引发的反思
引言 在人工智能领域,OpenAI再次引领潮流,推出了全新的推理模型系列——o3-mini。这一系列包括low、medium和high三个版本,旨在进一步推动低成本推理的发展。与此同时,OpenAI的CEO奥特曼也在Reddit的“有问必答”活动中罕见地公开…...
React中使用箭头函数定义事件处理程序
React中使用箭头函数定义事件处理程序 为什么使用箭头函数?1. 传递动态参数2. 避免闭包问题3. 确保每个方块的事件处理程序是独立的4. 代码可读性和维护性 示例代码总结 在React开发中,处理事件是一个常见的任务。特别是当我们需要传递动态参数时&#x…...
自制虚拟机(C/C++)(三、做成标准GUI Windows软件,扩展指令集,直接支持img软盘)
开源地址:VMwork 要使终端不弹出, #pragma comment(linker, "/subsystem:windows /ENTRY:mainCRTStartup") 还要实现jmp near 0x01类似的 本次的main.cpp #include <graphics.h> #include <conio.h> #include <windows.h> #includ…...
C# 语言基础全面解析
.NET学习资料 .NET学习资料 .NET学习资料 一、引言 C# 是一种功能强大、面向对象且类型安全的编程语言,由微软开发,广泛应用于各种类型的软件开发,从桌面应用、Web 应用到游戏开发等领域。本文将全面介绍 C# 语言的基础知识,帮…...
MySQL的覆盖索引
MySQL的覆盖索引 前言 当一个索引包含了查询所需的全部字段时,就可以提高查询效率,这样的索引又被称之为覆盖索引。 以MySQL常见的三种存储引擎为例:InnoDB、MyISAM、Memory,对于覆盖索引提高查询效率的方式均不同,…...
Hutool工具类
Hutool 是一个非常流行的 Java 工具类库,它提供了丰富的功能来简化开发中的常见任务,比如文件操作、加密、日期处理、字符串操作、数据库工具等。它是一个轻量级的工具库,可以减少开发者编写常用代码的工作量,提高开发效率。 主要…...
C++模板编程——可变参函数模板之折叠表达式
目录 1. 什么是折叠表达式 2. 一元左折 3. 一元右折 4. 二元左折 5. 二元右折 6. 后记 上一节主要讲解了可变参函数模板和参数包展开,这一节主要讲一下折叠表达式。 1. 什么是折叠表达式 折叠表达式是C17中引入的概念,引入折叠表达式的目的是为了…...
使用MATLAB进行雷达数据采集可视化
本文使用轮趣科技N10雷达,需要源码可在后台私信或者资源自取 1. 项目概述 本项目旨在通过 MATLAB 读取 N10 激光雷达 的数据,并进行 实时 3D 点云可视化。数据通过 串口 传输,并经过解析后转换为 三维坐标点,最终使用 pcplayer 进…...
【Linux系统】信号:信号保存 / 信号处理、内核态 / 用户态、操作系统运行原理(中断)
理解Linux系统内进程信号的整个流程可分为: 信号产生 信号保存 信号处理 上篇文章重点讲解了 信号的产生,本文会讲解信号的保存和信号处理相关的概念和操作: 两种信号默认处理 1、信号处理之忽略 ::signal(2, SIG_IGN); // ignore: 忽略#…...
在C语言多线程环境中使用互斥量
如果有十个银行账号通过不同的十条线程同时向同一个账号转账时,如果没有很好的机制保证十个账号依次存入,那么这些转账可能出问题。我们可以通过互斥量来解决。 C标准库提供了这个互斥量,只需要引入threads.头文件。 互斥量就像是一把锁&am…...
PHP代码审计学习02
目录 代码审计一般思路 Beescms代码审计(upload) Finecms基于前台MVC任意文件上传挖掘思路 CLTPHP基于thinkphp5框架的文件上传挖掘思路 今天来看PHP有框架MVC类,文件上传,断点调试挖掘。 同样还是有关键字搜索和功能点抓包两…...
基于微信小程序的医院预约挂号系统设计与实现(LW+源码+讲解)
专注于大学生项目实战开发,讲解,毕业答疑辅导,欢迎高校老师/同行前辈交流合作✌。 技术范围:SpringBoot、Vue、SSM、HLMT、小程序、Jsp、PHP、Nodejs、Python、爬虫、数据可视化、安卓app、大数据、物联网、机器学习等设计与开发。 主要内容:…...
大厂面试题备份20250201
20250201 面试策略 如果三面往后遇到传说中让人忍受不了的业余面试官,就舔着苟过去,入职大概率见不着他,但一二面遇到,反问环节就主动说不够match,让释放流程。 机器/深度学习 百面机器学习 5.4 通用CS 计算机网…...
Spring Boot 实例解析:HelloWorld 探究
POM 文件剖析: 父项目: <parent><groupId>org.springframework.boot</groupId><artifactId>spring‐boot‐starter‐parent</artifactId><version>1.5.9.RELEASE</version> </parent> 他的父项目是 <…...
【课题推荐】基于t分布的非高斯滤波框架在水下自主导航中的应用研究
水下自主导航系统在海洋探测、环境监测及水下作业等领域具有广泛的应用。然而,复杂的水下环境常常导致传感器输出出现野值噪声,这些噪声会严重影响导航信息融合算法的精度,甚至导致系统发散。传统的卡尔曼滤波算法基于高斯噪声假设࿰…...
【C++语言】卡码网语言基础课系列----12. 位置互换
文章目录 练习题目位置互换具体代码实现 小白寄语诗词共勉 练习题目 位置互换 题目描述: 给定一个长度为偶数位的字符串,请编程实现字符串的奇偶位互换。 输入描述: 输入包含多组测试数据。 输入的第一行是一个整数n,表示有测试…...
洛谷的更多功能(不会像其他文章那样复杂且仅支持Edge浏览器)
第一步:下载《洛谷美化 (1).zip》文件夹。 会出现这样的文件夹: 注意:Edge.txt和洛谷前提1.txt是一样的哟! 第二步:篡改猴 先打开Edge.txt或者是洛谷前提1.txt文件,打开后复制粘贴到你的Edge浏览器并打开…...
C++编程语言:抽象机制:模板(Bjarne Stroustrup)
目录 23.1 引言和概观(Introduction and Overview) 23.2 一个简单的字符串模板(A Simple String Template) 23.2.1 模板的定义(Defining a Template) 23.2.2 模板实例化(Template Instantiation) 23.3 类型检查(Type Checking) 23.3.1 类型等价(Type Equivalence) …...
女生年薪12万,算不算属于高收入人群
在繁华喧嚣的都市中,我们时常会听到关于收入、高薪与生活质量等话题的讨论。尤其是对于年轻女性而言,薪资水平不仅关乎个人价值的体现,更直接影响到生活质量与未来的规划。那么,女生年薪12万,是否可以被划入高收入人群…...
2181、合并零之间的节点
2181、[中等] 合并零之间的节点 1、问题描述: 给你一个链表的头节点 head ,该链表包含由 0 分隔开的一连串整数。链表的 开端 和 末尾 的节点都满足 Node.val 0 。 对于每两个相邻的 0 ,请你将它们之间的所有节点合并成一个节点ÿ…...
Immutable设计 SimpleDateFormat DateTimeFormatter
专栏系列文章地址:https://blog.csdn.net/qq_26437925/article/details/145290162 本文目标: 理解不可变设计模式,时间format有线程安全要求的注意使用DateTimeFormatter 目录 ImmutableSimpleDateFormat 非线程安全可以synchronized解决&a…...
【网络】传输层协议TCP(重点)
文章目录 1. TCP协议段格式2. 详解TCP2.1 4位首部长度2.2 32位序号与32位确认序号(确认应答机制)2.3 超时重传机制2.4 连接管理机制(3次握手、4次挥手 3个标志位)2.5 16位窗口大小(流量控制)2.6 滑动窗口2.7 3个标志位 16位紧急…...
17.[前端开发]Day17-形变-动画-vertical-align
1 transform CSS属性 - transform transform的用法 表示一个或者多个 不用记住全部的函数,只用掌握这四个常用的函数即可 位移 - translate <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta ht…...
LeetCode435周赛T2贪心
题目描述 给你一个由字符 N、S、E 和 W 组成的字符串 s,其中 s[i] 表示在无限网格中的移动操作: N:向北移动 1 个单位。S:向南移动 1 个单位。E:向东移动 1 个单位。W:向西移动 1 个单位。 初始时&#…...
陆游的《诗人苦学说》:从藻绘到“功夫在诗外”(中英双语)mastery lies beyond poetry
陆游的《诗人苦学说》:从藻绘到“功夫在诗外” 今天看万维钢的《万万没想到》一书,看到陆游的功夫在诗外的句子,特意去查找这首诗的原文。故而有此文。 我国学人还往往过分强调“功夫在诗外”这句陆游的名言,认为提升综合素质是一…...
AI模型平台之——ModelScope(魔搭)
ModelScope 是什么? ModelScope 是一个由阿里巴巴达摩院推出的开源模型库和工具集,旨在为开发者提供高效、便捷的机器学习模型和工具。ModelScope 提供了丰富的预训练模型、数据集和工具,支持多种任务和应用场景,如自然语言处理、…...
GIt使用笔记大全
Git 使用笔记大全 1. 安装 Git 在终端或命令提示符中,输入以下命令检查是否已安装 Git: git --version如果未安装,可以从 Git 官方网站 下载并安装适合你操作系统的版本。 2. 配置 Git 首次使用 Git 时,需要配置用户名和邮箱…...
42【文件名的编码规则】
我们在学习的过程中,写出数据或读取数据时需要考虑编码类型 火山采用:UTF-16 易语言采用:GBK php采用:UTF-8 那么我们写出的文件名应该是何种编码的?比如火山程序向本地写出一个“测试.txt”,理论上这个“测…...
Linux网络 HTTPS 协议原理
概念 HTTPS 也是一个应用层协议,不过 是在 HTTP 协议的基础上引入了一个加密层。因为 HTTP的内容是明文传输的,明文数据会经过路由器、wifi 热点、通信服务运营商、代理服务器等多个物理节点,如果信息在传输过程中被劫持,传输的…...
Vue.js组件开发-实现全屏手风琴幻灯片切换特效
使用 Vue 实现全屏手风琴幻灯片切换特效 步骤概述 创建 Vue 项目:使用 Vue CLI 创建一个新的 Vue 项目。设计组件结构:创建一个手风琴幻灯片组件,包含幻灯片项和切换逻辑。实现样式:使用 CSS 实现全屏和手风琴效果。添加交互逻辑…...
数据库、数据仓库、数据湖有什么不同
数据库、数据仓库和数据湖是三种不同的数据存储和管理技术,它们在用途、设计目标、数据处理方式以及适用场景上存在显著差异。以下将从多个角度详细说明它们之间的区别: 1. 数据结构与存储方式 数据库: 数据库主要用于存储结构化的数据&…...
MLM之MiniCPM-o:MiniCPM-o的简介(涉及MiniCPM-o 2.6和MiniCPM-V 2.6)、安装和使用方法、案例应用之详细攻略
MLM之MiniCPM-o:MiniCPM-o的简介(涉及MiniCPM-o 2.6和MiniCPM-V 2.6)、安装和使用方法、案例应用之详细攻略 目录 MiniCPM-o的简介 0、更新日志 1、MiniCPM-o系列模型特点 MiniCPM-o 2.6 的主要特点 MiniCPM-V 2.6的主要特点 2、MiniCPM-o系列模型架构 MiniC…...
【Conda 和 虚拟环境详细指南】
Conda 和 虚拟环境的详细指南 什么是 Conda? Conda 是一个开源的包管理和环境管理系统,支持多种编程语言(如Python、R等),最初由Continuum Analytics开发。 主要功能: 包管理:安装、更新、删…...