十九、迭代器模式
Iterator Design Partern 作用 遍历容器实现复杂,并且方式有多种,例如遍历二叉树时,有前序、后序、中序遍历。将遍历容器从容器中独立出来,让两者的职责更单一。 容器使用的是迭代器接口,基于接口而非实现编程,替换迭代器更加容易。 示例 public class MyArrayList<E> implements Lis…
LeetCode:把二叉搜索树转换为累加树_538
思路 首先二叉搜索树需要中序遍历,但如果是中序遍历,计算前面节点依赖于后面节点的结果。所以将中序遍历倒过来即可。 二叉树的遍历不止3种,可以自行调整。 题目 给出二叉 搜索 树的根节点,该树的节点值各不相同,请你将其转换为累加树(Greater Sum Tree),使每个节点 node 的新值等于原树中大于或等于 node.va…
LeetCode:二叉搜索树中第K小的元素_230
思路 利用二叉搜索树的特征:中序遍历后是个递增的序列,很容易就AC了。 这样的时间复杂度是O(n),如果节点已经存储了序号,就可以像查找值一样O(logN)。 叶节点也满足二叉搜索树 题目 给定一个二叉搜索树的根节点 root ,和一个整数 k ,请你设计一个算法查找其中第 k 个最小元素(从 1 开始计数)。   示例 1: 输入:root = …
LeetCode:二叉树的序列化与反序列化_297
思路 使用前序遍历序列化,遍历的元素往链表末尾添加,根节点先添加,再左子节点,右子节点。所以根节点在链表头部,有了这个信息就好做了,毕竟二叉树的遍历就是找到根节点+做点啥+递归。 使用前序遍历反序列化,需要先得出根节点,在链表的头部,将其抛出。再找出左子节点,还是链表的头部,将其抛出,继续寻找左子节点的左子节点。。。 中序遍历无法反序列化,因为根节…
LeetCode:寻找重复的子树_652
思路 问题一:如果遍历比较 遍历所有节点,然后两两比较。时间复杂度O(n)。一看性能就不行。 利用set来判断是否重复。不过有重复多次的情况,但只需返回一个重复节点,所以还需要记录count,使用map即可。 问题二:如何判断两个节点结构相同 通过递归,同时遍历两个节点。因为一个节点需要和多次比较,所以同一个节点需要遍历多次,性能差。 序列化二叉树…
实战代理模式,模拟Mybatis
实战代理模式,模拟Mybatis 在使用mybatis操作数据库时,我们只需要定义一个接口,然后在xml里编写对应的sql,就能查询数据。其原理是Mybatis通过@mypperscan指定扫描的mapper接口路径,对mapper接口进行动态代理,生成的代理类通过解析xml得到对应sql,最终开发人员只需要调用接口就能执行sql了。 今天我们来实…
十八、代理模式
Proxy Design Pattern 作用 对原有功能进行增强,注意这里的增强是增加额外的功能,和原有功能无关。 使用场景 业务系统中增加非功能性需求,比如:监控、统计、鉴权、限流、事务、幂等、日志等。 还可以实现接口缓存,通过请求参数决定使用缓存还是实时查询。 实现方式 静态代理 代理接口 代理类和被代理类实现同样的接口,通过组合的形式,进行…
十七、访问者模式
Visitor pattern 因为它难理解、难实现,应用它会导致代码的可读性、可维护性变差,所以,访问者模式在实际的软件开发中很少被用到,在没有特别必要的情况下,建议你不要使用访问者模式。 ——设计模式之美 前言 这个模式侧重代码实现,主要是解决分离业务代码,抽取能力带来的问题。 示例V1 模拟读取不同格式的文件。 ResourceFileV1:…
十六、备忘录模式
Memento Design Pattern 定义 在不违背封装原则的情况下,捕获一个对象的内部状态,并在该对象之外保存这个状态,以便以后恢复对象为先前的状态。 应用场景 防丢失、撤销、恢复。可以理解为备份操作,只不过是从代码设计的层面来考虑的。 示例 来自极客时间 输入单词,支持撤销操作。 用户输入文本时,程序将其追加存储在内存文本中;用户输入“…
LeetCode:回文链表_234
思路 简单的方法是遍历一边链表,存入数组,再从首尾往中间判断是否相等。但是题目说了,进阶的解法是空间复杂度为O(1),首先排除递归反转链表,倒是可以利用迭代来反转链表。在优化下,不用反转整条链表来比较,只需反转半条即可。 一次就AC了,爽 题目 给你一个单链表的头节点 head ,请你判断该链表是否为回文链表。如果是,返回 true ;否则,返回 …