思路 基础班双指针，还有归并的思想 题目 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。    示例 1： 输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4] 示例 2： 输入：l1 = [], l2 = [] 输出：[] 示例 3： 输入：l1 = [],…

思路 最终需要的结果是前序遍历，最简单的方式就是递归前序遍历，结果存到队列里，最后再组装。难一点的就是一边遍历一边组装结果，如果是递归，遍历左节点时，将父节点的右节点更改为左节点（题目要求的结果），那么会影响右节点的遍历（已经被替换成左节点了）。所以这里用迭代遍历，将遍历顺序存到了栈里，不用担心修改父节点影响遍历了。 题目 给你二叉树的根结点 ro…

工厂模式 作用 唯一的职责就是创建对象，将复制的创建过程，获取对象的逻辑与对象的使用进行解耦。 分为简单工厂、工厂方法、抽象工厂。 简单工厂 对象获取逻辑复杂时，例如根据文件类型获取对应的解析器，解析器有很多，就需要在使用对象前，进行臃肿的逻辑判断，才能获取对应的解析器对象。造成获取对象与使用对象耦合，不好扩展。后续新增解析器，又得在获取对象那里添…

思路 116题还能通过画图看出规律，但这是升级版，非完美二叉树。这题很容易想到用层次遍历，但是是中等难度，肯定不是最优解。 分析下，层次遍历时间复杂度O(N)，已经做到极致了。那么只能从空间复杂度下手，层次遍历空间复杂度为O(N)，如果不存副本，倒是可以优化。 遍历某一层时，就将下一层串起来，这样下一层就可以直接遍历，不用存到队列里。第一层没有上一…

思路 首先想到的是暴力求解，双重循环得出所有连续子串，但是多半要超时。没想到其他办法。看了题解，学到了前缀和的概念，这里的子串和等于end的前缀和减去start的前缀和。在前缀和的基础上，结合了hash来优化，也就是两数之和那道题。 两个地方需要注意。一、需要的前缀和可能出现多次，那么每次都得算上。二、前缀和为0也是一种情况，并且是必要的，需要手动…

装饰器模式 定义 通过将对象放入包含行为的特殊封装对象中来为原对象绑定新的行为。 实现方式 IA 需要增强的功能，对应的接口 public interface IA { void func(); } A 待增强的类 public class A implements IA { @Override public void func() { } } A…

观察者模式 定义 在对象之间定义一个一对多的依赖，当一个对象状态改变的时候，所有依赖的对象都会自动收到通知。 实现方式 可分为阻塞、非阻塞，根据业务场景决定使用哪种。 基础版本 IObserver 观察者接口 public interface IObserver { // 模板模式 default void updateWraper(Message…

责任链模式 定义 在职责链模式中，多个处理器依次处理同一个请求。一个请求先经过 A 处理器处理，然后再把请求传递给 B 处理器，B 处理器处理完后再传递给 C 处理器，以此类推，形成一个链条。链条上的每个处理器各自承担各自的处理职责，所以叫作职责链模式。 在 GoF 的定义中，一旦某个处理器能处理这个请求，就不会继续将请求传递给后续的处理器了。当然…

适配器模式 定义 适配器模式的英文翻译是 Adapter Design Pattern。顾名思义，这个模式就是用来做适配的，它将不兼容的接口转换为可兼容的接口，让原本由于接口不兼容而不能一起工作的类可以一起工作。 一般来说，适配器模式可以看作一种“补偿模式”，用来补救设计上的缺陷。应用这种模式 算是“无奈之举”，如果在设计初期，我们就能协调规避接口…

解决的问题 有些数据在系统中只应该保存一份，比如系统的配置信息类 资源访问冲突的问题，比如多个logger写入同一个日志文件 几种实现方式 饿汉式 静态成员变量，类加载时实例化 线程安全 不支持延迟加载 public class HungryManDemo { private static final HungryManDemo instance …