最近几天,每天的基本工作就是写毕设paper,同时做毕设实验,最后就是刷算法题,学习一下JavaWeb和背一下八股。
基本安排和内容都是这样,比较忙和紧张, 没有做到每天都总结,总结一下最近学的内容。
算法
这是最近一段时间做的算法题,主要都是二叉树的相关内容,总结内容和结构如下:
1.红黑树和二叉平衡搜索树弄分开了,其实红黑树就是一种二叉平衡搜索树,这两个树不是独立的,所以C++中map、multimap、set、multiset的底层实现机制是二叉平衡搜索树,再具体一点是红黑树。
2.二叉树的顺序遍历(前序、中序、后序)分为:递归和迭代遍历,迭代是利用栈这一数据结构模拟递归的思想;层次遍历分为:迭代和递归,迭代是最常见和实用的,利用队列先进先出特点。
3.递归 VS 迭代在实现迭代法的过程中,有同学问了:递归与迭代究竟谁优谁劣呢?从时间复杂度上其实迭代法和递归法差不多(在不考虑函数调用开销和函数调用产生的堆栈开销),但是空间复杂度上,递归开销会大一些,因为递归需要系统堆栈存参数返回值等等。递归更容易让程序员理解,但收敛不好,容易栈溢出。这么说吧,递归是方便了程序员,难为了机器(各种保存参数,各种进栈出栈)。
在实际项目开发的过程中我们是要尽量避免递归!因为项目代码参数、调用关系都比较复杂,不容易控制递归深度,甚至会栈溢出。
4.涉及到二叉树的遍历问题(Maybe隐含的,如翻转二叉树,对称二叉树,求深度/高度),一定要弄清用哪种遍历方法,不同问题用的不同顺序是不一样的;一定要掌握前中后序一种迭代的写法,并不因为某种场景的题目一定要用迭代,而是现场面试的时候,面试官看你顺畅的写出了递归,一般会进一步考察能不能写出相应的迭代
5.在二叉树:找我的所有路径? (opens new window)中正式涉及到了回溯,回溯和递归都是相伴相生的,涉及到路径的问题(需要二叉树的节点返回出来结果时),就要回溯了!回溯和递归是一一对应的,有一个递归,就要有一个回溯
6.递归函数什么时候需要返回值?什么时候不需要返回值?一般情况下:如果需要搜索整棵二叉树,那么递归函数就不要返回值,如果要搜索其中一条符合条件的路径,递归函数就需要返回值,因为遇到符合条件的路径了就要及时返回。
这里总结如下三点:
- 如果需要搜索整棵二叉树且不用处理递归返回值,递归函数就不要返回值。(这种情况是113.路径总和II)
- 如果需要搜索整棵二叉树且需要处理递归返回值,递归函数就需要返回值。 (这种情况我们在236. 二叉树的最近公共祖先 (opens new window)中介绍)
- 如果要搜索其中一条符合条件的路径,那么递归一定需要返回值,因为遇到符合条件的路径了就要及时返回。(112.路径总和的情况)
7.习惯了利用节点自身属性判断节点特征时,平时习惯了使用通过节点的左右孩子判断本节点的属性,但发现使用这个思路无法判断左叶子。此时需要相连的三层之间构成的约束条件,也就是要通过节点的父节点以及孩子节点来判断本节点的属性。
8.在构造二叉树时,有三个注意的点:
- 分割时候,坚持区间不变量原则,左闭右开,或者左闭又闭。
- 分割的时候,注意后序 或者 前序已经有一个节点作为中间节点了,不能继续使用了。
- 如何使用切割后的后序数组来切合中序数组?利用中序数组大小一定是和后序数组的大小相同这一特点来进行切割。
9.注意类似用数组构造二叉树的题目,每次分隔尽量不要定义新的数组,而是通过下标索引直接在原数组上操作,这样可以节约时间和空间上的开销。
10.一般情况来说:如果让空节点(空指针)进入递归,就不加if,如果不让空节点进入递归,就加if限制一下, 终止条件也会相应的调整。
毕设
目前毕业论文有效内容已经写了30余页:
但是最后实验仿真和性能分析的部分害没有做出来,甚至设计都是一个很困难的问题,希望快点搞出来吧
其他
学习 and 复习了Web前端开发的基础知识,如Web后端开发的基础(HTTP协议、请求响应),并且也复习了数据库MySQL,以及通过Mybatis框架如何来完成数据库的基本操作。
还没学到案例部分,接下来学习的就是就通过一个案例(智能学习系统),来将前端开发、后端开发、数据库整合起来,涉及到SpringBootWeb的案例、登录认证、AOP等知识。