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

算法刷题 week3

这里写目录标题

  • 1.重建二叉树
        • 题目
        • 题解
          • (递归) O(n)
  • 2.二叉树的下一个节点
        • 题目
        • 题解
          • (模拟) O(h)
      • 3.用两个栈实现队列
        • 题目
        • 题解
          • (栈,队列) O(n)

1.重建二叉树

题目

在这里插入图片描述

题解

(递归) O(n)

递归建立整棵二叉树:先递归创建左右子树,然后创建根节点,并让指针指向两棵子树。

前序遍历(根 左 右)中序遍历(左 根 右) 后序遍历(左 右 根)

具体步骤如下:

  1. 先利用前序遍历找根节点:前序遍历(根 左 右)的第一个数,就是根节点的值;
  2. 在中序遍历中找到根节点的位置 k,则 k 左边是左子树的中序遍历(左 根 右),右边是右子树的中序遍历;
  3. 假设左子树的中序遍历的长度是 l,则在前序遍历中,根节点后面的 l 个数,是左子树的前序遍历,剩下的数是右子树的前序遍历;
  4. 有了左右子树的前序遍历和中序遍历,我们可以先递归创建出左右子树,然后再创建根节点;

时间复杂度分析

我们在初始化时,用哈希表(unordered_map<int,int>)记录每个值在中序遍历中的位置,这样我们在递归到每个节点时,在中序遍历中查找根节点位置的操作,只需要 O(1) 的时间。此时,创建每个节点需要的时间是 O(1),所以总时间复杂度是 O(n)。

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
//preorder前序遍历(根 左 右),inorder中序遍历(左 根 右)
class Solution {
public:unordered_map<int, int> pos; TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {int n = preorder.size();for (int i = 0; i < n; ++i)pos[inorder[i]] = i;  //用哈希表记录每个值在中序遍历中的位置 return dfs(preorder, inorder, 0, n - 1, 0, n - 1);    }//前序遍历pre的范围是[pl,pr], 中序遍历in的范围是[il,ir]TreeNode* dfs(vector<int>& pre, vector<int>& in, int pl, int pr, int il, int ir) {if (pl > pr) return NULL;int k = pos[pre[pl]] - il;  //寻找前序的根节点在中序遍历中是在第几个位置TreeNode* root = new TreeNode(pre[pl]); //生成新的根节点root->left = dfs(pre, in, pl + 1, pl + k, il, il + k - 1);root->right = dfs(pre, in, pl + k + 1, pr, il + k + 1, ir);return root;}
};

2.二叉树的下一个节点

题目

在这里插入图片描述

题解

(模拟) O(h)

这道题目就是让我们求二叉树中给定节点的后继。

中序遍历(左 根 右)

分情况讨论即可,如下图所示:

  1. (左 右)如果当前节点有右儿子,则右子树中最左侧的节点就是当前节点的后继。比如F的后继是H;
  2. (左 根)如果当前节点没有右儿子,**则需要沿着father域一直向上找,找到第一个是其(这个其非当前节点)father左儿子的节点,该节点的father就是当前节点的后继。**比如当前节点是D,则第一个满足是其father左儿子的节点是F,则C的father就是D的后继,即F是D的后继。

在这里插入图片描述

时间复杂度分析

不论往上找还是往下找,总共遍历的节点数都不大于树的高度。所以时间复杂度是 O(h),其中 h 是树的高度。

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode *father;*     TreeNode(int x) : val(x), left(NULL), right(NULL), father(NULL) {}* };*/
class Solution{
public:TreeNode* inorderSuccessor(TreeNode* p) {if (p->right) {p = p->right;  //易错带while (p->left) p = p->left;return p;}//p == p->father->right 用来判断p是否是右节点while (p->father && p == p->father->right) p = p->father;return p->father;}
};

3.用两个栈实现队列

题目

在这里插入图片描述

题解

(栈,队列) O(n)

这是一道基础题,只要把功能实现对就可以,不需要考虑运行效率。

我们用两个栈来做,一个主栈,用来存储数据;一个辅助栈,用来当缓存。

栈:先进后出,队列:先进先出

  • push(x),我们直接将 x 插入主栈中即可。
  • pop(),此时我们需要弹出最先进入栈的元素,也就是栈底元素。我们可以先将所有元素从主栈中弹出,压入辅助栈中。则辅助栈的栈顶元素就是我们要弹出的元素,将其弹出即可。然后再将辅助栈中的元素全部弹出,压入主栈中。
  • peek(),可以用和pop()操作类似的方式,得到最先压入栈的元素。
  • empty(),直接判断主栈是否为空即可。

时间复杂度分析

  • push():O(1);
  • pop(): 每次需要将主栈元素全部弹出,再压入,所以需要 O(n) 的时间;
  • peek():类似于pop(),需要 O(n) 的时间;
  • empty():O(1);
class MyQueue {
public:/** Initialize your data structure here. */stack<int> stk, cache;MyQueue() {  //初始化,如果栈不为空,则用while()清空while (!stk.empty()) {stk.pop();}while (!cache.empty()) {cache.pop();}}/** Push element x to the back of queue. */void push(int x) {stk.push(x);}void copy(stack<int>& a, stack<int>& b) {while (a.size()) {b.push(a.top());a.pop();}}/** Removes the element from in front of queue and returns that element. */int pop() {if (stk.empty()) return -1;  //如果栈为空,返回-1copy(stk, cache);int res = cache.top();cache.pop();copy(cache, stk);return res;}/** Get the front element. */int peek() {if (stk.empty()) return NULL;  //如果栈为空,返回NULLcopy(stk, cache);int res = cache.top();copy(cache, stk);return res;}/** Returns whether the queue is empty. */bool empty() {return stk.empty();}
};/*** Your MyQueue object will be instantiated and called as such:* MyQueue obj = MyQueue();* obj.push(x);* int param_2 = obj.pop();* int param_3 = obj.peek();* bool param_4 = obj.empty();*/

相关文章:

算法刷题 week3

这里写目录标题 1.重建二叉树题目题解(递归) O(n) 2.二叉树的下一个节点题目题解(模拟) O(h) 3.用两个栈实现队列题目题解(栈&#xff0c;队列) O(n) 1.重建二叉树 题目 题解 (递归) O(n) 递归建立整棵二叉树&#xff1a;先递归创建左右子树&#xff0c;然后创建根节点&…...

TCP详解之流量控制

TCP详解之流量控制 发送方不能无脑的发数据给接收方&#xff0c;要考虑接收方处理能力。 如果一直无脑的发数据给对方&#xff0c;但对方处理不过来&#xff0c;那么就会导致触发重发机制&#xff0c;从而导致网络流量的无端的浪费。 为了解决这种现象发生&#xff0c;TCP 提…...

mac根目录下创建文件不能问题

mac根目录下创建文件不能问题 解决办法2: 原因 mac os引入了系统完整性保护&#xff08;SIP&#xff09;机制&#xff0c;无法在/、/usr目录下新建文件 解决办法1&#xff1a; 打开终端&#xff0c;输入 csrutil status显示enabled表示启用了SIP&#xff0c;接下来需要禁用SIP…...

stable diffusion model训练遇到的问题【No module named ‘triton‘】

一天早晨过来&#xff0c;发现昨天还能跑的diffusion代码&#xff0c;突然出现了【No module named ‘triton’】的问题&#xff0c;导致本就不富裕的显存和优化速度雪上加霜&#xff0c;因此好好探究了解决方案。 首先是原因&#xff0c;由于早晨过来发现【电脑重启】导致了【…...

线性dp,优化记录,273. 分级

273. 分级 273. 分级 - AcWing题库 给定长度为 N 的序列 A&#xff0c;构造一个长度为 N 的序列 B&#xff0c;满足&#xff1a; B 非严格单调&#xff0c;即 B1≤B2≤…≤BN 或 B1≥B2≥…≥BN。最小化 S∑Ni1|Ai−Bi|。 只需要求出这个最小值 S。 输入格式 第一行包含一…...

JWT 安全及案例实战

文章目录 一、JWT (json web token)安全1. Cookie&#xff08;放在浏览器&#xff09;2. Session&#xff08;放在服务器&#xff09;3. Token4. JWT (json web token)4.1 头部4.1.1 alg4.1.2 typ 4.2 payload4.3 签名4.4 通信流程 5. 防御措施 二、漏洞实例&#xff08;webgoa…...

Vue2+Vue3

文章目录 Vue快速上手Vue是什么第一个Vue程序插值表达式Vue核心特性&#xff1a;响应式 Vue指令v-htmlv-show 与 v-ifv-else 与 v-else-ifv-onv-bindv-forv-model指令修饰符 计算属性watch侦听器&#xff08;监视器&#xff09;watch——简写watch——完整写法 Vue生命周期 和 …...

华为云云耀云服务器L实例评测|redis漏洞回顾 MySQL数据安全解决 搭建主从集群MySQL 相关设置

前言 最近华为云云耀云服务器L实例上新&#xff0c;也搞了一台来玩&#xff0c;期间遇到过MySQL数据库被攻击的情况&#xff0c;数据丢失&#xff0c;还好我有几份备份&#xff0c;没有造成太大的损失&#xff1b;后来有发现Redis数据库被攻击的情况&#xff0c;加入了redis密…...

【C++】详解std::thread

2023年9月10日&#xff0c;周日下午开始 2023年9月10日&#xff0c;周日晚上23:35完成 虽然这篇博客我今天花了很多时间去写&#xff0c;但是我对std::thread有了一个完整的认识 不过有些内容还没完善&#xff0c;以后有空再更新.... 目录 头文件类的成员类型方法(construc…...

Apache HTTPD 漏洞复现

文章目录 Apache HTTPD 漏洞复现1. Apache HTTPD 多后缀解析漏洞1.1 漏洞描述1.2 漏洞复现1.3 漏洞利用1.4 获取GetShell1.5 漏洞防御 2. Apache HTTPD 换行解析漏洞-CVE-2017-157152.1 漏洞描述2.2 漏洞复现2.3 漏洞利用2.4 修复建议 3. Apache HTTP Server_2.4.49 路径遍历和…...

【C++从入门到精通】第2篇:C++基础知识(中)

文章目录 2.1 iostream介绍&#xff1a;cout、cin和endl2.1.1 输入/输出库2.1.2 std::cout2.1.3 std::endl2.1.4 std::cout是缓冲的2.1.5 std::endl与\n2.1.6 std::cin2.1.7 总结2.1.8 练习时间 2.2 未初始化的变量和未定义的行为2.2.1 未初始化的变量2.2.2 未定义行为2.2.3 明…...

【RuoYi移动端】uni-app中实现生成二维码功能(代码示例)

完整示例&#xff1a; <template><view><view class"titleBar">执法检查“通行码”信息</view><view class"twoCode"><canvas canvas-id"qrcode"></canvas></view></view> </templat…...

深度解剖数据在栈中的应用

> 作者简介&#xff1a;დ旧言~&#xff0c;目前大一&#xff0c;现在学习Java&#xff0c;c&#xff0c;c&#xff0c;Python等 > 座右铭&#xff1a;松树千年终是朽&#xff0c;槿花一日自为荣。 > 望小伙伴们点赞&#x1f44d;收藏✨加关注哟&#x1f495;&#x1…...

Android10 SystemUI系列 需求定制(一)状态栏控制中心默认tile定制属性适配

一、前言 SystemUI 所包含的界面和模块比较多,这一节主要分享一下控制中心默认tile 列表的实现,通过配置可以实现 下拉状态栏,控制中心默认的tile显示 二、准备工作 按照惯例先找一下控制中心的代码,主要在下面这个路径下 frameworks/base/packages/SystemUI/src/com/andr…...

【微信小程序】文章设置

设置基本字体样式&#xff1a;行高、首行缩进 font-size: 32rpx;line-height: 1.6em;text-indent: 2em;padding: 20rpx 0;border-bottom: 1px dashed var(--themColor); 两端对齐 text-align: justify; css文字两行或者几行显示省略号 css文字两行或者几行显示省略号_css…...

程序员在线周刊(冒泡算法篇)

大家好&#xff0c;欢迎来到程序员在线周刊&#xff01;本期我们将深入探讨一种经典的排序算法——冒泡算法&#xff0c;并附上具体的代码实现。 目录 简介代码原理广告广告1广告2广告3 简介 冒泡算法是一种简单但效率较低的排序算法&#xff0c;它的原理非常直观&#xff1a…...

string

目录 六、STL简介 (一)什么是STL (二)STL的版本 (三)STL六大组件 七、string (一)标准库中的string 1、string类 2、string常用的接口 1)string类对象的常见构造 2)string类对象的容量操作 3)string类对象的访问及遍历操作 4)string类对象的修改操作 5)string类非成…...

html的日期选择插件

1.效果 2.文档 https://layui.gitee.io/v2/docs/ 3.引入 官网地址&#xff1a; https://layui.gitee.io/v2/ 引入&#xff08;在官网下载&#xff0c;&#xff09;jquery-1.7.2.min.js,layui/layui.js **<link href"js/layui/css/layui.css" rel"stylesh…...

OPPO哲库事件 “ 始末 ” ! 集体打哑谜?

1►OPPO哲库解散 2019 年&#xff0c;美国商务部以“科技网络安全”为由&#xff0c;将华为公司及其70家附属公司列入出口管制“实体名单”。与此同时&#xff0c;OPPO 创始人兼 CEO陈明永对外宣布&#xff0c;公司将为未来三年内投入 500 亿元用于前沿技术和深水区技术的探索…...

数据聚类分析

K均值 1.1 数据来源(随机生成) import matplotlib.pyplot as plt from sklearn.datasets import make_blobsX, y make_blobs(n_samples150,n_features2,centers3,cluster_std0.5,shuffleTrue,random_state0) # plt.scatter(X[:, 0], X[:, 1], cwhite, markero, edgecolorsbl…...

10X探头隐藏技能:除了衰减信号,它如何用补偿电容拯救你的高频测量?

10X探头的高频测量奥秘&#xff1a;补偿电容如何成为信号保真的关键 在电子测量领域&#xff0c;示波器探头是工程师们不可或缺的工具&#xff0c;而10X探头凭借其独特的设计在高频测量中展现出无可替代的优势。本文将深入探讨10X探头内部补偿电容的工作原理&#xff0c;揭示它…...

嵌入式系统开发中的关键技术术语解析

嵌入式系统开发中的56个关键技术术语解析1. 数据转换基础概念1.1 采样与保持特性采集时间(Tacq)是从释放保持状态到采样电容电压稳定至新输入值的1 LSB范围之内所需的时间。在采样-保持电路中&#xff0c;这个参数直接影响系统的动态性能。孔径延迟(tAD)描述从时钟信号的采样沿…...

HarmonyOS6 半年磨一剑 - RcTextarea 组件核心架构与类型系统设计

文章目录前言一、组件整体架构1.1 文件结构1.2 装饰器体系二、类型系统深度解析2.1 边框模式类型2.2 清空触发类型2.3 格式化与解析函数类型2.4 文本对齐与回车键类型三、核心参数体系3.1 必传参数3.2 尺寸相关参数3.3 功能开关参数四、内部状态与生命周期4.1 内部状态设计4.2 …...

毕业设计实战:基于SpringBoot+Vue+MySQL的智慧党建系统设计与实现指南

毕业设计实战&#xff1a;基于SpringBootVueMySQL的智慧党建系统设计与实现指南 在开发“基于SpringBootVueMySQL的智慧党建系统”毕业设计时&#xff0c;曾因活动报名记录表未通过党员ID与党建活动ID双外键关联踩过关键坑——初期仅单独设计报名记录表的报名编号字段&#xff…...

Jieba分词实战:5分钟搞定中文文本词频统计(附完整代码)

Jieba分词实战&#xff1a;5分钟搞定中文文本词频统计&#xff08;附完整代码&#xff09; 中文文本处理是自然语言处理&#xff08;NLP&#xff09;的基础环节&#xff0c;而分词则是中文文本处理的第一步。不同于英文等空格分隔的语言&#xff0c;中文文本需要专门的工具进行…...

OpenClaw密码管理:nanobot安全存储与自动填充方案

OpenClaw密码管理&#xff1a;nanobot安全存储与自动填充方案 1. 为什么需要本地化的密码管理方案 去年的一次数据泄露事件让我彻底放弃了所有云端密码管理器。当时我使用的某知名商业工具突然弹出安全警报&#xff0c;提示"您的部分密码可能已被未授权访问"。虽然…...

量子行走:从理论到Python实现——量子力学原理与Qubit物理

目录 2. 量子力学原理与Qubit物理 2.1 量子比特的物理实现 2.1.1 双能级系统建模 2.1.2 布洛赫球表示与可视化 2.2 叠加与纠缠现象 2.2.1 量子叠加原理 2.2.2 量子纠缠理论 2.3 量子测量与退相干 2.3.1 测量公设的实现 2.3.2 噪声与退相干机制 2. 量子力学原理与Qubi…...

别再只会setValue了!Qt进度条QProgressBar/QProgressDialog的5个实战技巧与避坑指南

别再只会setValue了&#xff01;Qt进度条QProgressBar/QProgressDialog的5个实战技巧与避坑指南 在开发文件管理器、下载工具或数据处理软件时&#xff0c;进度条往往是用户最直观的体验指标之一。一个"聪明"的进度条不仅能准确反映任务状态&#xff0c;还能提升用户…...

极简安装方案:树莓派部署OpenClaw轻量版对接云端Qwen3-32B

极简安装方案&#xff1a;树莓派部署OpenClaw轻量版对接云端Qwen3-32B 1. 为什么选择树莓派OpenClaw轻量版&#xff1f; 去年夏天&#xff0c;我突发奇想&#xff1a;能不能用树莓派做个24小时在线的AI管家&#xff1f;既能控制智能家居&#xff0c;又能处理简单办公任务。但…...

Flink技术实践-超时异常踩坑与优化

一、背景介绍在Flink实时计算的生产环境中&#xff0c;最令人头疼的往往不是复杂的业务逻辑&#xff0c;而是那些突如其来的“超时异常”。这些异常就像是系统中的“幽灵”&#xff0c;通常在业务高峰期或网络抖动时出现&#xff0c;导致作业重启、数据延迟甚至数据丢失。最近几…...