AcWing.18 重建二叉树
输入一棵二叉树前序遍历和中序遍历的结果,请重建该二叉树。
注意:
二叉树中每个节点的值都互不相同;
输入的前序遍历和中序遍历一定合法;
数据范围
树中节点数量范围 $[0,100]$。
样例
给定:
前序遍历是:[3, 9, 20, 15, 7]
中序遍历是:[9, 3, 15, 20, 7]
返回:[3, 9, 20, null, null, 15, 7, null, null, null, null]
返回的二叉树如下所示:
3
/ \
9 20
/ \
15 7
Code
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970 /*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left; ...
AcWing.3786 二叉排序树
你需要写一种数据结构,来维护一些数,其中需要提供以下操作:
插入数值 $x$。
删除数值 $x$。
题目保证:
操作 $1$ 插入的数值各不相同。
操作 $2$ 删除的数值一定存在。
输出树的前序遍历
输入格式
第一行包含整数 $n$,表示共有 $n$ 个操作命令。
接下来 $n$ 行,每行包含两个整数 $opt$ 和 $x$,表示操作序号和操作数值。
数据范围
$1 \le n \le 2000$,
$-10000 \le x \le 10000$
输入样例:
4
1 1
1 3
1 5
2 3
输出样例:
1 5
思路
插入操作:
删除操作:
对于一个二叉排序树来说,中序遍历(左中右)是有序的。
有三种情况
该节点为叶节点
该节点存在一个左节点,或者一个右节点
该节点存在左节点、右节点
重点说明一下第三种情况:由于是一颗二叉排序树,故节点$X$的左子树中最右的根节点$A$一定是左子树中最大的值,故将节点$A$的值赋值给节点$X$,再递归遍历左子树,删除节点$A$。
Code
12345678910111213141516171819202122232425262 ...
AcWing.840 模拟散列表
840.模拟散列表
维护一个集合,支持如下几种操作:
I x,插入一个数 $x$;
Q x,询问数 $x$ 是否在集合中出现过;
现在要进行 $N$ 次操作,对于每个询问操作输出对应的结果。
输入格式
第一行包含整数 $N$,表示操作数量。
接下来 $N$ 行,每行包含一个操作指令,操作指令为 I x,Q x 中的一种。
输出格式
对于每个询问指令 Q x,输出一个询问结果,如果 $x$ 在集合中出现过,则输出 Yes,否则输出 No。
每个结果占一行。
数据范围
$1 \le N \le 10^5$
$-10^9 \le x \le 10^9$
输入样例:
5
I 1
I 2
I 3
Q 2
Q 5
输出样例:
Yes
No
开散列方法(拉链法)
核心:如果一个位置有多个重复映射到此处的元素,就开一个链表,将所有元素都存储下来。
$Code$:
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636 ...
AcWing.3302 表达式求值
题意
给定一个表达式,其中运算符仅包含 +,-,*,/(加 减 乘 整除),可能包含括号,请你求出表达式的最终值。
注意:
数据保证给定的表达式合法。
题目保证符号 - 只作为减号出现,不会作为负号出现,例如,-1+2,(2+2)*(-(1+1)+2) 之类表达式均不会出现。
题目保证表达式中所有数字均为正整数。
题目保证表达式在中间计算过程以及结果中,均不超过 $2^{31}-1$。
题目中的整除是指向 $0$ 取整,也就是说对于大于 $0$ 的结果向下取整,例如 $5/3=1$,对于小于 $0$ 的结果向上取整,例如 $5/(1-4) = -1$。
C++和Java中的整除默认是向零取整;Python中的整除//默认向下取整,因此Python的eval()函数中的整除也是向下取整,在本题中不能直接使用。
输入格式
共一行,为给定表达式。
输出格式
共一行,为表达式的结果。
数据范围
表达式的长度不超过 $10^5$。
输入样例:
(2+2)*(1+1)
输出样例:
8
思想
表达式求值:
如果当前元素是数字:压入
如果当前元素是(:压入
如果当前元素是):操作到(
如果当前 ...
数学真题
2013
第四题:忘记反常积分条件
第十题:利用原函数$y=f(x)$的导数$\frac{dy}{dx}$和其反函数$x=f^{-1}(y)$的倒数关系:$\frac{dx}{dy}=\frac{1}{\frac{dy}{dx}}$。同时考察了$y=0$处导数值,要找出对应的$x$的值。
第十一题:忘记极坐标的面积方程了:$S=\displaystyle\int_{\theta _1}^{\theta _2}\frac{1}{2}r^{2}(\theta)d\theta$
第十三题:二阶非齐次线性方程的解得结构为:其次方程的通解+非齐次方程的特解。
线性微分方程反问题至高水准:要解非齐次必先求齐次方程,要想解方程比先求通解。
第十六题:定积分面积公式有问题。
第十七题:计算出错。
第十八题:
考察微分等式的证明,要熟知费马定理,罗尔定理,拉格朗日中值定理等等。
还考察了构造函数。
【注】
证明$f^{\prime}(\epsilon)=0$
思路:$\begin{cases} (1)用导数零点定理 \\ (2)用费马定理 \\ (3)用罗尔定理 \end{c ...
周鸽鸽的决胜一百天
第一题
题目
考点
解答
拿到极限先定形;在加减法中慎用等价。
方法一:补项法
由$x\to 0,\ln{(1+x)}-x\sim -\frac{1}{2}x$
$x\to 0,\sin{x}-x\sim -\frac{1}{6}x^3$
可得
$$\begin{aligned} & \displaystyle\lim_{x\to 0}\frac{\ln{(1+x)}-(-x)+[-x+\sin{x}]+\sin{x}[f(x)-1]}{x^2} \\ & = \displaystyle\lim_{x\to x}\frac{\ln{(1-x)}-(-x)}{x^2}+\displaystyle\lim_{x\to x}\frac{-\frac{1}{6}x^3}{x^2}+\displaystyle\lim_{x\to x}\frac{\sin{x}[f(x)-1]}{x^2} \\ & = \displaystyle\lim_{x\to x}\frac{-\frac{1}{2}x^2}{x^2}+\displaystyle\lim_{x\to x}\fra ...
周鸽鸽的强化习题
第一章 函数、极限和连续
[考点1]无穷小量及其阶的问题
题目
回答情况
第1题
x x
第2题
x √
第3题
x √
第4题
x √
第5题
√
总结
计算能力有待提高!
[考点2]函数极限的计算
题目
回答情况
第6题
x √
第7题
x √
第8题
x √
第9题
x √
第10题
√
第11题
x x
第12题
x x
第13题
x x
第14题
x x
第15题
x x
第16题
√
第17题
x x
第18题
x x
第19题
x x
总结
第六题:要求满足$\displaystyle\lim_{x\to\Delta}f(x,a) = \displaystyle\lim_{x\to\Delta}g(x)$式子中的$a$的值,只需要将左右极限算出,取相等,解除$a$即可。
第七题:等价无穷小中没有$\displaystyle\lim_{x\to 0}\displaystyle\sqrt[x]{1 + \Delta} - 1 \sim \frac{\Delta ...
第十八周复盘
第十八周复盘
上个周完成的事
完成线代基础部分
英语阅读 2010 test1
完成880 20道基础题目
总结
上个周的主要目的完成了,接下来就进入了数学的强化阶段。
英语单词每天也能完成,但是阅读的情况不是很理想,只完成了一篇。
线代基础虽然过了一遍,但是还是不牢固,需要在强化阶段经常进行复习。
高数部分的时间完全被线代占用,接下来的一周上午进行线代,下午进行高数,轮换着来。晚上的时间可以进行英语阅读或者政治腿姐强化课。
暑假的安排:
时间
任务
7:30 - 8:00
起床,吃早饭
8:00 - 8:50
背单词
9:00 - 12:00
数学
12:00 - 13:30
午饭、午休
13:30 - 17:30
数学
17:30 - 20:00
晚饭,健身
20:00 - 22:00
专业课、英语
22:00 - 23:00
自由安排
**[注]:**学习的时候经常喝水,学大概50 ~ 60分钟走动一下。学了2小时,可以多休息一会。
下周完成的事情
线代完成强化前三章并且跟着视频做题,高数完成880前三章的部分。
英语完成 2 ...
mathjax-test
$f(x)$ 一阶连续可导 $\quad\Rightarrow\quad$ $\lim\limits_{x \to 0} f’(x_0 + x) = f’(x_0)$
$$ \begin{aligned} \lim\limits_{x\to0}\dfrac{\displaystyle\int_0^{x^2}f(t)dt}{x^2\displaystyle\int_0^xf(t)dt} &\xlongequal{L’} \lim\limits_{x\to0}\dfrac{2x f(x^2)}{2x\displaystyle\int_0^xf(t)dt + x^2f(x)} \\ &= \lim\limits_{x\to0}\dfrac{2f(x^2)}{2\displaystyle\int_0^xf(t)dt + xf(x)} \\ &\xlongequal{L’} \lim\limits_{x\to0}\dfrac{4xf’(x^2)}{3f(x) + xf’(x)} \\ &= \lim\limits_{x\to0}\dfrac{4f’(x^2)}{3 ...
第十七周复盘
第十七周复盘
上个周完成的事
由于上周很忙,事情都是零零碎碎的,故没有完成的事情$-。 -$
总结
上个周回到家里面,开始慢慢进入学习的状态了。
给自己一个大致的安排吧:
暑假的安排:
时间
任务
7:30 - 8:00
起床,吃早饭
8:00 - 8:50
背单词
9:00 - 12:00
数学
12:00 - 13:30
午饭、午休
13:30 - 17:30
数学
17:30 - 20:00
晚饭,健身
20:00 - 22:00
专业课、英语
22:00 - 23:00
自由安排
**[注]:**学习的时候经常喝水,学大概50 ~ 60分钟走动一下。学了2小时,可以多休息一会。
下周完成的事情
完成线代基础部分
英语阅读 2010 test1-4 做完并翻译
高数跟着武老师的每日一题,以及睡前小故事,并搬到博客上