月度归档: 2021年10月

10 篇文章

thumbnail
LeetCode:二叉树的序列化与反序列化_297
思路 使用前序遍历序列化,遍历的元素往链表末尾添加,根节点先添加,再左子节点,右子节点。所以根节点在链表头部,有了这个信息就好做了,毕竟二叉树的遍历就是找到根节点+做点啥+递归。 使用前序遍历反序列化,需要先得出根节点,在链表的头部,将其抛出。再找出左子节点,还是链表的头部,将其抛出,继续寻找左子节点的左子节点。。。 中序遍历无法反序列化,因为根节…
thumbnail
LeetCode:寻找重复的子树_652
思路 问题一:如果遍历比较 遍历所有节点,然后两两比较。时间复杂度O(n)。一看性能就不行。 利用set来判断是否重复。不过有重复多次的情况,但只需返回一个重复节点,所以还需要记录count,使用map即可。 问题二:如何判断两个节点结构相同 通过递归,同时遍历两个节点。因为一个节点需要和多次比较,所以同一个节点需要遍历多次,性能差。 序列化二叉树…
thumbnail
实战代理模式,模拟Mybatis
实战代理模式,模拟Mybatis 在使用mybatis操作数据库时,我们只需要定义一个接口,然后在xml里编写对应的sql,就能查询数据。其原理是Mybatis通过@mypperscan指定扫描的mapper接口路径,对mapper接口进行动态代理,生成的代理类通过解析xml得到对应sql,最终开发人员只需要调用接口就能执行sql了。 今天我们来实…
十八、代理模式
Proxy Design Pattern 作用 对原有功能进行增强,注意这里的增强是增加额外的功能,和原有功能无关。 使用场景 业务系统中增加非功能性需求,比如:监控、统计、鉴权、限流、事务、幂等、日志等。 还可以实现接口缓存,通过请求参数决定使用缓存还是实时查询。 实现方式 静态代理 代理接口 代理类和被代理类实现同样的接口,通过组合的形式,进行…
thumbnail
十七、访问者模式
Visitor pattern 因为它难理解、难实现,应用它会导致代码的可读性、可维护性变差,所以,访问者模式在实际的软件开发中很少被用到,在没有特别必要的情况下,建议你不要使用访问者模式。 ——设计模式之美 前言 这个模式侧重代码实现,主要是解决分离业务代码,抽取能力带来的问题。 示例V1 模拟读取不同格式的文件。 ResourceFileV1:…
十六、备忘录模式
Memento Design Pattern 定义 在不违背封装原则的情况下,捕获一个对象的内部状态,并在该对象之外保存这个状态,以便以后恢复对象为先前的状态。 应用场景 防丢失、撤销、恢复。可以理解为备份操作,只不过是从代码设计的层面来考虑的。 示例 来自极客时间 输入单词,支持撤销操作。 用户输入文本时,程序将其追加存储在内存文本中;用户输入“…
thumbnail
LeetCode:回文链表_234
思路 简单的方法是遍历一边链表,存入数组,再从首尾往中间判断是否相等。但是题目说了,进阶的解法是空间复杂度为O(1),首先排除递归反转链表,倒是可以利用迭代来反转链表。在优化下,不用反转整条链表来比较,只需反转半条即可。 一次就AC了,爽 题目 给你一个单链表的头节点 head ,请你判断该链表是否为回文链表。如果是,返回 true ;否则,返回 …
thumbnail
十五、状态模式
State Pattern 有限状态机 简称状态机, 由三部分组成:状态、事件、动作。事件触发状态转移,执行动作(非必须)。 状态机实现方式一:分支逻辑法 就是各种if else,switch case。判断不同的状态,遇到不同的事件,执行不同的操作,例如改变状态,执行动作。适用于简单的场景,毕竟不要过度设计。 状态机实现方式二:查表法 状态机有两…
LeetCode:最长回文子串_5
思路 算是入门题了,运用双指针即可。 题目 给你一个字符串 s,找到 s 中最长的回文子串。   示例 1: 输入:s = "babad" 输出:"bab" 解释:"aba" 同样是符合题意的答案。 示例 2: 输入:s = "cbbd" 输出:"bb" 示例 3: 输入:s = "a" 输出:"a" 示例 4: 输入:s = "ac" 输出:"a…
thumbnail
Leetcode:验证回文串_125
思路 判断是否为回文字符串,最开始想到的是找到中点,利用双指针往外扩。后来发现直接从头尾往中间收就行了。 有两个注意点 本题有只判断字符和数字,其他的符号不管 大小写不敏感 在leetcode评论区学到个技巧 题目 给定一个字符串,验证它是否是回文串,只考虑字母和数字字符,可以忽略字母的大小写。 说明:本题中,我们将空字符串定义为有效的回文串。  …