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

刷题之路径总和Ⅲ(leetcode)

路径总和Ⅲ
在这里插入图片描述
这题和和《为K的数组》思路一致,也是用前缀表。
代码调试过,所以还加一部分用前序遍历数组和中序遍历数组构造二叉树的代码。

#include<vector>
#include<unordered_map>
#include<iostream>
using namespace std;
//Definition for a binary tree node.
struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode() : val(0), left(nullptr), right(nullptr) {}TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};class Solution {
private:unordered_map<long long, int>map;int dfs(TreeNode* root, long long cur, int targetSum){if (root == NULL){return 0;}int count = 0;cur += root->val;if (map.find(cur - targetSum) != map.end()){count += map[cur - targetSum];}map[cur]++;int leftcount = dfs(root->left, cur, targetSum);int rightcount = dfs(root->right, cur, targetSum);map[cur]--;//因为路径总和只是针对同一个头结点,所以不是同一个头结点时需要回溯return count + leftcount + rightcount;}
public:int pathSum(TreeNode* root, int targetSum) {map[0] = 1;return dfs(root, 0, targetSum);}
};class tree {
private:TreeNode* build(vector<int>& preorder, vector<int>& inorder){if (preorder.size() == 0)return NULL;//找到根节点int rootvalue = preorder[0];TreeNode* root = new TreeNode(rootvalue);//叶子节点if (preorder.size() == 1)return root;//区分左右子树位置int index = 0;for (int i = 0; i < inorder.size(); i++){if (inorder[i] == rootvalue){index = i;break;}}vector<int>left_in(inorder.begin(), inorder.begin() + index);vector<int>right_in(inorder.begin() + index + 1, inorder.end());vector<int>left_pre(preorder.begin() + 1, preorder.begin() + 1 + left_in.size());vector<int>right_pre(preorder.begin() + 1 + left_in.size(), preorder.end());root->left = build(left_pre, left_in);root->right = build(right_pre, right_in);return root;}
public:TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {return build(preorder, inorder);}
};int main()
{vector<int>inorder = {3,3,-2,5,2,1,10,-3,11};vector<int>preorder = { 10,5,3,3,-2,2,1,-3,11 };int targetsum = 8;tree mytree;TreeNode* root = mytree.buildTree(preorder,inorder);Solution solution;int result = solution.pathSum(root, targetsum);cout << result << endl;
}

相关文章:

刷题之路径总和Ⅲ(leetcode)

路径总和Ⅲ 这题和和《为K的数组》思路一致&#xff0c;也是用前缀表。 代码调试过&#xff0c;所以还加一部分用前序遍历数组和中序遍历数组构造二叉树的代码。 #include<vector> #include<unordered_map> #include<iostream> using namespace std; //Def…...

MongoDB 原子操作:确保数据一致性和完整性的关键

在 MongoDB 中&#xff0c;原子操作是指可以一次性、不可分割地执行的数据库操作。这些操作能够保证在多个并发操作中不会出现数据不一致或者丢失的情况&#xff0c;确保数据库的数据完整性和一致性。 基本语法 MongoDB 的原子操作通常与更新操作相关&#xff0c;其基本语法如…...

2024上半年软考高级系统架构设计师回顾

本博客地址&#xff1a;https://security.blog.csdn.net/article/details/139238685 2024年上半年软考在5月25-26日举行&#xff0c;趁着时间刚过去记忆还在&#xff0c;简单写一点总结。 关于考试形式&#xff1a;上机考试&#xff08;以后也都是机考&#xff09;&#xff0…...

SQL注入绕过技术深度解析与防御策略

引言 在Web安全领域&#xff0c;SQL注入攻击一直是一个棘手的问题。攻击者通过SQL注入手段获取敏感数据、执行恶意操作&#xff0c;甚至完全控制系统。尽管许多防御措施已被广泛采用&#xff0c;但攻击者仍不断开发新的绕过技术。本文将深度解析SQL注入的绕过技术&#xff0c;…...

Redis教程(十六):Redis的缓存穿透、缓存击穿、缓存雪崩

传送门&#xff1a;Redis教程汇总篇&#xff0c;让你从入门到精通 缓存穿透 描述 用户需要查询一个数据&#xff0c;例如要查一张ASSET_CODE 999999的卡片&#xff0c;查询redis中没有&#xff0c;就直接去请求数据库&#xff0c;数据库中也不存在对应的数据&#xff0c;返回…...

如何实现一个高效的单向链表逆序输出?

实现单向链表逆序输出的关键点有两个: 反转链表本身 遍历反转后的链表并输出首先,我们来看如何反转链表: class Node:def __init__(self, data):self.data dataself.next Nonedef reverse_list(head):"""反转单向链表"""prev Nonecurrent h…...

使用 Go 实现 HelloWorld 程序,并分析其结构

在学习任何新的编程语言时&#xff0c;编写一个 “Hello, World” 程序通常是最初的入门步骤。这不仅是一个传统&#xff0c;也是一种快速了解语言基本语法和运行机制的有效方法。对于 Go 语言&#xff0c;这个过程不仅可以帮助新手快速入门&#xff0c;还提供了一个窗口&#…...

机器学习:在Python中sklearn库的使用,纯干货!12个小时的整理!

无监督学习是在没有标签的数据上训练的。其主要目的可能包括聚类、降维、生成模型等。 以下是 6 个重要的无监督学习算法&#xff0c;这些算法都可以通过使用sklearn&#xff08;Scikit-learn&#xff09;库在Python中很好地处理&#xff1a; 目录 K-Means 聚类 层次聚类 …...

XSS 攻击

XSS 攻击简介 定义&#xff1a; XSS&#xff08;跨站脚本攻击&#xff09;是一种网络安全漏洞&#xff0c;攻击者通过在 Web 页面中注入恶意代码&#xff0c;利用用户的浏览器执行这些恶意脚本&#xff0c;从而实施攻击。 解决方案&#xff1a; 过滤用户输入&#xff1a; 对…...

.Net Core 中间件与过滤器

过滤器这个是.Net MVC旧有的功能&#xff0c;中间件这个概念是新出的&#xff0c; ASP.NET Core只是完成了HTTP请求调度、报文解析等必要的工作&#xff0c;像检查用户身份、设置缓存报文头等操作都是在中间件中完成&#xff0c;中间件就是ASP.NET Core的一个组件&#xff0c;…...

【ARMv7-A】——WFI(wait for interrupt)

文章目录 WFI基本原理使用场景多任务模型注意事项代码实例linux 内核中的 WFI 指令不使用 WFI 指令测试使用 WFI 指令测试WFI WFI 即 Wait for interrupt,常用于低功耗。 WFI (Wait for interrupt) 和 WFE (Wait for event) 是两个让 ARM 核进入 low-power standby 模式的指…...

92. 反转链表 II

题目描述 给你单链表的头指针 head 和两个整数 left 和 right &#xff0c;其中 left < right 。请你反转从位置 left 到位置 right 的链表节点&#xff0c;返回 反转后的链表 。 示例 示例 1&#xff1a; 输入&#xff1a;head [1,2,3,4,5], left 2, right 4 输出&#…...

Modbus工业网关

随着工业自动化程度的不断提高&#xff0c;设备之间的数据通信与交互变得至关重要。在这一背景下&#xff0c;Modbus协议凭借其简单、可靠、开放的特点&#xff0c;成为了工业自动化领域中最常用的通信协议之一。而HiWoo Box网关作为一款支持Modbus协议的工业网关设备&#xff…...

c++——模板初始识

1.函数模板 我们经常用到Swap函数交换两个值。由于需要交换的数据的类型不同&#xff0c;我们就需要写不同参数类型的同名函数&#xff0c;也就是函数重载&#xff1a; 然而这三个函数的逻辑是一样的&#xff0c;写这么多有些多此一举&#xff0c;通过函数模版可以写一个通用…...

帆软生成csv文件

帆软官网提供了导出csv文件的插件&#xff0c;需要下载指定版本的插件 请选择具体的详情点击官网介绍&#xff1a;文档介绍 插件地址&#xff1a;插件地址...

12.Redis之补充类型渐进式遍历

1.stream 官方文档的意思, 就是 stream 类型就可以用来模拟实现这种事件传播的机制~~stream 就是一个队列(阻塞队列)redis 作为一个消息队列的重要支撑属于是 List blpop/brpop 升级版本.用于做消息队列 2.geospatial 用来存储坐标 (经纬度)存储一些点之后,就可以让用户给定…...

品牌做电商控价的原因

品牌控价确实是一项至关重要的任务&#xff0c;它关乎着品牌形象、市场定位以及长期发展的稳定性。在电商平台上&#xff0c;价格的公开性和透明度使得消费者、经销商和其他渠道参与方都能够轻易地进行价格比较。因此&#xff0c;品牌方必须对电商渠道的价格进行严格的管控&…...

安全面试中的一个基础问题:你如何在数据库中存储密码?

3分钟讲解。 上周的面试故事 职位&#xff1a;初级安全工程师&#xff0c;刚毕业。 开始面试。 我&#xff1a;“这里你提到对数据安全有很好的理解。你能举例说明哪些方面的数据安全吗&#xff1f;” A&#xff1a;“当然。例如&#xff0c;当我们构建一个系统时&#xff0c;会…...

【python深度学习】——torch.min()

【python深度学习】——torch.min 1. torch.min()1.1 计算整个张量的最小值1.2 沿特定维度计算最小值1.3 比较两个张量 1. torch.min() torch.min()接受的参数如下: input: 输入的张量。dim: 沿指定维度寻找最小值。如果指定了该参数&#xff0c;返回一个元组&#xff0c;其中…...

华为校招机试 - 最久最少使用缓存(20240508)

题目描述 无线通信移动性需要在基站上配置邻区(本端基站的小区 LocalCell 与周边邻基站的小区 NeighborCelI 映射)关系, 为了能够加速无线算法的计算效率,设计一个邻区关系缓存表,用于快速的通过本小区 LocalCell 查询到邻小区 NeighborCell。 但是缓存表有一定的规格限…...

中南大学无人机智能体的全面评估!BEDI:用于评估无人机上具身智能体的综合性基准测试

作者&#xff1a;Mingning Guo, Mengwei Wu, Jiarun He, Shaoxian Li, Haifeng Li, Chao Tao单位&#xff1a;中南大学地球科学与信息物理学院论文标题&#xff1a;BEDI: A Comprehensive Benchmark for Evaluating Embodied Agents on UAVs论文链接&#xff1a;https://arxiv.…...

【入坑系列】TiDB 强制索引在不同库下不生效问题

文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...

GitHub 趋势日报 (2025年06月08日)

&#x1f4ca; 由 TrendForge 系统生成 | &#x1f310; https://trendforge.devlive.org/ &#x1f310; 本日报中的项目描述已自动翻译为中文 &#x1f4c8; 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...

AI,如何重构理解、匹配与决策?

AI 时代&#xff0c;我们如何理解消费&#xff1f; 作者&#xff5c;王彬 封面&#xff5c;Unplash 人们通过信息理解世界。 曾几何时&#xff0c;PC 与移动互联网重塑了人们的购物路径&#xff1a;信息变得唾手可得&#xff0c;商品决策变得高度依赖内容。 但 AI 时代的来…...

IP如何挑?2025年海外专线IP如何购买?

你花了时间和预算买了IP&#xff0c;结果IP质量不佳&#xff0c;项目效率低下不说&#xff0c;还可能带来莫名的网络问题&#xff0c;是不是太闹心了&#xff1f;尤其是在面对海外专线IP时&#xff0c;到底怎么才能买到适合自己的呢&#xff1f;所以&#xff0c;挑IP绝对是个技…...

MinIO Docker 部署:仅开放一个端口

MinIO Docker 部署:仅开放一个端口 在实际的服务器部署中,出于安全和管理的考虑,我们可能只能开放一个端口。MinIO 是一个高性能的对象存储服务,支持 Docker 部署,但默认情况下它需要两个端口:一个是 API 端口(用于存储和访问数据),另一个是控制台端口(用于管理界面…...

Sklearn 机器学习 缺失值处理 获取填充失值的统计值

💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 使用 Scikit-learn 处理缺失值并提取填充统计信息的完整指南 在机器学习项目中,数据清…...

【实施指南】Android客户端HTTPS双向认证实施指南

&#x1f510; 一、所需准备材料 证书文件&#xff08;6类核心文件&#xff09; 类型 格式 作用 Android端要求 CA根证书 .crt/.pem 验证服务器/客户端证书合法性 需预置到Android信任库 服务器证书 .crt 服务器身份证明 客户端需持有以验证服务器 客户端证书 .crt 客户端身份…...

webpack面试题

面试题&#xff1a;webpack介绍和简单使用 一、webpack&#xff08;模块化打包工具&#xff09;1. webpack是把项目当作一个整体&#xff0c;通过给定的一个主文件&#xff0c;webpack将从这个主文件开始找到你项目当中的所有依赖文件&#xff0c;使用loaders来处理它们&#x…...

从实验室到产业:IndexTTS 在六大核心场景的落地实践

一、内容创作&#xff1a;重构数字内容生产范式 在短视频创作领域&#xff0c;IndexTTS 的语音克隆技术彻底改变了配音流程。B 站 UP 主通过 5 秒参考音频即可克隆出郭老师音色&#xff0c;生成的 “各位吴彦祖们大家好” 语音相似度达 97%&#xff0c;单条视频播放量突破百万…...