算法刷题 week3
这里写目录标题
- 1.重建二叉树
- 题目
- 题解
- (递归) O(n)
- 2.二叉树的下一个节点
- 题目
- 题解
- (模拟) O(h)
- 3.用两个栈实现队列
- 题目
- 题解
- (栈,队列) O(n)
1.重建二叉树
题目
题解
(递归) O(n)
递归建立整棵二叉树:先递归创建左右子树,然后创建根节点,并让指针指向两棵子树。
前序遍历(根 左 右)中序遍历(左 根 右) 后序遍历(左 右 根)
具体步骤如下:
- 先利用前序遍历找根节点:前序遍历(根 左 右)的第一个数,就是根节点的值;
- 在中序遍历中找到根节点的位置 k,则 k 左边是左子树的中序遍历(左 根 右),右边是右子树的中序遍历;
- 假设左子树的中序遍历的长度是 l,则在前序遍历中,根节点后面的 l 个数,是左子树的前序遍历,剩下的数是右子树的前序遍历;
- 有了左右子树的前序遍历和中序遍历,我们可以先递归创建出左右子树,然后再创建根节点;
时间复杂度分析
我们在初始化时,用哈希表(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)
这道题目就是让我们求二叉树中给定节点的后继。
中序遍历(左 根 右)
分情况讨论即可,如下图所示:
- (左 根 右)如果当前节点有右儿子,则右子树中最左侧的节点就是当前节点的后继。比如F的后继是H;
- (左 根)如果当前节点没有右儿子,**则需要沿着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.用两个栈实现队列题目题解(栈,队列) O(n) 1.重建二叉树 题目 题解 (递归) O(n) 递归建立整棵二叉树:先递归创建左右子树,然后创建根节点&…...

TCP详解之流量控制
TCP详解之流量控制 发送方不能无脑的发数据给接收方,要考虑接收方处理能力。 如果一直无脑的发数据给对方,但对方处理不过来,那么就会导致触发重发机制,从而导致网络流量的无端的浪费。 为了解决这种现象发生,TCP 提…...
mac根目录下创建文件不能问题
mac根目录下创建文件不能问题 解决办法2: 原因 mac os引入了系统完整性保护(SIP)机制,无法在/、/usr目录下新建文件 解决办法1: 打开终端,输入 csrutil status显示enabled表示启用了SIP,接下来需要禁用SIP…...
stable diffusion model训练遇到的问题【No module named ‘triton‘】
一天早晨过来,发现昨天还能跑的diffusion代码,突然出现了【No module named ‘triton’】的问题,导致本就不富裕的显存和优化速度雪上加霜,因此好好探究了解决方案。 首先是原因,由于早晨过来发现【电脑重启】导致了【…...
线性dp,优化记录,273. 分级
273. 分级 273. 分级 - AcWing题库 给定长度为 N 的序列 A,构造一个长度为 N 的序列 B,满足: B 非严格单调,即 B1≤B2≤…≤BN 或 B1≥B2≥…≥BN。最小化 S∑Ni1|Ai−Bi|。 只需要求出这个最小值 S。 输入格式 第一行包含一…...

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

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

华为云云耀云服务器L实例评测|redis漏洞回顾 MySQL数据安全解决 搭建主从集群MySQL 相关设置
前言 最近华为云云耀云服务器L实例上新,也搞了一台来玩,期间遇到过MySQL数据库被攻击的情况,数据丢失,还好我有几份备份,没有造成太大的损失;后来有发现Redis数据库被攻击的情况,加入了redis密…...

【C++】详解std::thread
2023年9月10日,周日下午开始 2023年9月10日,周日晚上23:35完成 虽然这篇博客我今天花了很多时间去写,但是我对std::thread有了一个完整的认识 不过有些内容还没完善,以后有空再更新.... 目录 头文件类的成员类型方法(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介绍: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中实现生成二维码功能(代码示例)
完整示例: <template><view><view class"titleBar">执法检查“通行码”信息</view><view class"twoCode"><canvas canvas-id"qrcode"></canvas></view></view> </templat…...

深度解剖数据在栈中的应用
> 作者简介:დ旧言~,目前大一,现在学习Java,c,c,Python等 > 座右铭:松树千年终是朽,槿花一日自为荣。 > 望小伙伴们点赞👍收藏✨加关注哟💕…...
Android10 SystemUI系列 需求定制(一)状态栏控制中心默认tile定制属性适配
一、前言 SystemUI 所包含的界面和模块比较多,这一节主要分享一下控制中心默认tile 列表的实现,通过配置可以实现 下拉状态栏,控制中心默认的tile显示 二、准备工作 按照惯例先找一下控制中心的代码,主要在下面这个路径下 frameworks/base/packages/SystemUI/src/com/andr…...

【微信小程序】文章设置
设置基本字体样式:行高、首行缩进 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…...
程序员在线周刊(冒泡算法篇)
大家好,欢迎来到程序员在线周刊!本期我们将深入探讨一种经典的排序算法——冒泡算法,并附上具体的代码实现。 目录 简介代码原理广告广告1广告2广告3 简介 冒泡算法是一种简单但效率较低的排序算法,它的原理非常直观:…...

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.引入 官网地址: https://layui.gitee.io/v2/ 引入(在官网下载,)jquery-1.7.2.min.js,layui/layui.js **<link href"js/layui/css/layui.css" rel"stylesh…...

OPPO哲库事件 “ 始末 ” ! 集体打哑谜?
1►OPPO哲库解散 2019 年,美国商务部以“科技网络安全”为由,将华为公司及其70家附属公司列入出口管制“实体名单”。与此同时,OPPO 创始人兼 CEO陈明永对外宣布,公司将为未来三年内投入 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…...
挑战杯推荐项目
“人工智能”创意赛 - 智能艺术创作助手:借助大模型技术,开发能根据用户输入的主题、风格等要求,生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用,帮助艺术家和创意爱好者激发创意、提高创作效率。 - 个性化梦境…...

【OSG学习笔记】Day 18: 碰撞检测与物理交互
物理引擎(Physics Engine) 物理引擎 是一种通过计算机模拟物理规律(如力学、碰撞、重力、流体动力学等)的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互,广泛应用于 游戏开发、动画制作、虚…...

23-Oracle 23 ai 区块链表(Blockchain Table)
小伙伴有没有在金融强合规的领域中遇见,必须要保持数据不可变,管理员都无法修改和留痕的要求。比如医疗的电子病历中,影像检查检验结果不可篡改行的,药品追溯过程中数据只可插入无法删除的特性需求;登录日志、修改日志…...
AtCoder 第409场初级竞赛 A~E题解
A Conflict 【题目链接】 原题链接:A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串,只有在同时为 o 时输出 Yes 并结束程序,否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...
Python爬虫(二):爬虫完整流程
爬虫完整流程详解(7大核心步骤实战技巧) 一、爬虫完整工作流程 以下是爬虫开发的完整流程,我将结合具体技术点和实战经验展开说明: 1. 目标分析与前期准备 网站技术分析: 使用浏览器开发者工具(F12&…...
高防服务器能够抵御哪些网络攻击呢?
高防服务器作为一种有着高度防御能力的服务器,可以帮助网站应对分布式拒绝服务攻击,有效识别和清理一些恶意的网络流量,为用户提供安全且稳定的网络环境,那么,高防服务器一般都可以抵御哪些网络攻击呢?下面…...

第 86 场周赛:矩阵中的幻方、钥匙和房间、将数组拆分成斐波那契序列、猜猜这个单词
Q1、[中等] 矩阵中的幻方 1、题目描述 3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵,其中每行,每列以及两条对角线上的各数之和都相等。 给定一个由整数组成的row x col 的 grid,其中有多少个 3 3 的 “幻方” 子矩阵&am…...

OPENCV形态学基础之二腐蚀
一.腐蚀的原理 (图1) 数学表达式:dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一,腐蚀跟膨胀属于反向操作,膨胀是把图像图像变大,而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...
Python Einops库:深度学习中的张量操作革命
Einops(爱因斯坦操作库)就像给张量操作戴上了一副"语义眼镜"——让你用人类能理解的方式告诉计算机如何操作多维数组。这个基于爱因斯坦求和约定的库,用类似自然语言的表达式替代了晦涩的API调用,彻底改变了深度学习工程…...

毫米波雷达基础理论(3D+4D)
3D、4D毫米波雷达基础知识及厂商选型 PreView : https://mp.weixin.qq.com/s/bQkju4r6med7I3TBGJI_bQ 1. FMCW毫米波雷达基础知识 主要参考博文: 一文入门汽车毫米波雷达基本原理 :https://mp.weixin.qq.com/s/_EN7A5lKcz2Eh8dLnjE19w 毫米波雷达基础…...