当前位置: 首页 > 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。 但是缓存表有一定的规格限…...

【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例

文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...

【ROS】Nav2源码之nav2_behavior_tree-行为树节点列表

1、行为树节点分类 在 Nav2(Navigation2)的行为树框架中,行为树节点插件按照功能分为 Action(动作节点)、Condition(条件节点)、Control(控制节点) 和 Decorator(装饰节点) 四类。 1.1 动作节点 Action 执行具体的机器人操作或任务,直接与硬件、传感器或外部系统…...

VTK如何让部分单位不可见

最近遇到一个需求&#xff0c;需要让一个vtkDataSet中的部分单元不可见&#xff0c;查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行&#xff0c;是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示&#xff0c;主要是最后一个参数&#xff0c;透明度…...

Robots.txt 文件

什么是robots.txt&#xff1f; robots.txt 是一个位于网站根目录下的文本文件&#xff08;如&#xff1a;https://example.com/robots.txt&#xff09;&#xff0c;它用于指导网络爬虫&#xff08;如搜索引擎的蜘蛛程序&#xff09;如何抓取该网站的内容。这个文件遵循 Robots…...

【HarmonyOS 5 开发速记】如何获取用户信息(头像/昵称/手机号)

1.获取 authorizationCode&#xff1a; 2.利用 authorizationCode 获取 accessToken&#xff1a;文档中心 3.获取手机&#xff1a;文档中心 4.获取昵称头像&#xff1a;文档中心 首先创建 request 若要获取手机号&#xff0c;scope必填 phone&#xff0c;permissions 必填 …...

在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?

uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件&#xff0c;用于在原生应用中加载 HTML 页面&#xff1a; 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...

Unsafe Fileupload篇补充-木马的详细教程与木马分享(中国蚁剑方式)

在之前的皮卡丘靶场第九期Unsafe Fileupload篇中我们学习了木马的原理并且学了一个简单的木马文件 本期内容是为了更好的为大家解释木马&#xff08;服务器方面的&#xff09;的原理&#xff0c;连接&#xff0c;以及各种木马及连接工具的分享 文件木马&#xff1a;https://w…...

Docker 本地安装 mysql 数据库

Docker: Accelerated Container Application Development 下载对应操作系统版本的 docker &#xff1b;并安装。 基础操作不再赘述。 打开 macOS 终端&#xff0c;开始 docker 安装mysql之旅 第一步 docker search mysql 》〉docker search mysql NAME DE…...

安全突围:重塑内生安全体系:齐向东在2025年BCS大会的演讲

文章目录 前言第一部分&#xff1a;体系力量是突围之钥第一重困境是体系思想落地不畅。第二重困境是大小体系融合瓶颈。第三重困境是“小体系”运营梗阻。 第二部分&#xff1a;体系矛盾是突围之障一是数据孤岛的障碍。二是投入不足的障碍。三是新旧兼容难的障碍。 第三部分&am…...

Go 并发编程基础:通道(Channel)的使用

在 Go 中&#xff0c;Channel 是 Goroutine 之间通信的核心机制。它提供了一个线程安全的通信方式&#xff0c;用于在多个 Goroutine 之间传递数据&#xff0c;从而实现高效的并发编程。 本章将介绍 Channel 的基本概念、用法、缓冲、关闭机制以及 select 的使用。 一、Channel…...