Cao Note算法与设计模式
配套知识点：设计模式
怎么用这份笔记
- 分级：
★★★ 必须吃透/★★☆ 了解即可（记结论就行）/★☆☆ 可以跳过（一句话看一眼）- 【简历亮点，高频追问】：简历里写过的技术，面试官会顺着往下挖，这段必须能展开讲
- 每个考点按「定义 → 原理 → 要点 / 易错点」组织，只讲知识点
1. 排序算法：快排、归并、堆排 ★★★ （手撕题）
需要重点掌握的是快排、归并、堆排三种。
- 快排：分治，平均 O(nlogn)，最坏 O(n²)，不稳定，原地排序。最坏情况出现在数组已经有序时，用随机选基准规避。
- 归并：稳定，O(nlogn)，需要额外 O(n) 空间。
- 堆排：O(1) 额外空间，不稳定。
稳定性速记：稳定的是冒泡、插入、归并；不稳定的是快排、选择、堆排。
工程实践里排序通常交给数据库 ORDER BY 或 Collections.sort，值得关注的不是手写排序，而是排序字段有没有索引。
2. 二分查找 ★★★ （手撕题）
前提是数组有序，每次排除一半，复杂度 O(logn)。
两个关键点：
- 循环条件用
left <= right； - 中点写成
left + (right - left) / 2，防止相加溢出。
常见变体：找第一个 / 最后一个相等的位置（左右边界）、找插入位置、旋转数组中查找。边界变体最容易出错。
工程中「定位时间区间边界」这类需求本质也是二分思想，只是通常由数据库索引和区间查询完成。
int binarySearch(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;
else if (nums[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}int binarySearch(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;
else if (nums[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}3. 常见算法与数据结构题（手撕高频）★★★ （手撕题）
按套路归类记忆，比一题一题背有效：
- 有序数组 / 两数之和 → 双指针
- 子串 / 连续区间 → 滑动窗口
- 求最优解 → 动态规划
- 树的问题 → 递归
- 找环 / 找中点 → 快慢指针
高频题：反转链表、环形链表、两数之和、三数之和、最长无重复子串、二叉树遍历、爬楼梯、最长递增子序列。其中反转链表和 LRU 的具体写法见第 10 节。
4. 设计模式六大原则 ★★☆
六个原则：
- 单一职责：一个类只负责一件事。
- 开闭原则：对扩展开放、对修改关闭。
- 里氏替换：子类能够替换父类而不破坏原有逻辑。
- 依赖倒置：依赖抽象，不依赖具体实现。
- 接口隔离：接口要小而专，不要强迫实现方依赖用不到的方法。
- 迪米特法则：最少知道，一个对象尽量少了解其他对象的内部细节。
记忆时抓核心：最关键的是开闭原则和依赖倒置，其他原则基本是它们的衍生。
开闭原则的典型落地：对接多个外部渠道时，新增一个渠道只增加一个实现类，主流程不动。
5. 单例模式（各种写法，手撕高频）★★★
常见写法和取舍：
- 饿汉式：类加载时就创建，简单、线程安全，但可能浪费。
- DCL 双重校验锁：
volatile不能省——实例化分「分配内存、初始化、赋值引用」三步，可能发生指令重排，使其他线程拿到还没初始化完的对象。 - 静态内部类：懒加载 + 线程安全（靠类加载机制保证），推荐写法。
- 枚举：最安全，天然防反射、防反序列化破坏单例。
易错点：单例本身没问题，问题是往单例里放可变状态。Spring 的 Bean 默认就是单例，如果在单例 Bean 里用 HashMap 当可变本地缓存，多线程下数据就会错乱。
// DCL 双重校验锁（volatile 不可省）
public class Singleton {
private static volatile Singleton instance;
public static Singleton getInstance() {
if (instance == null) {
synchronized (Singleton.class) {
if (instance == null) instance = new Singleton();
}
}
return instance;
}
}// DCL 双重校验锁（volatile 不可省）
public class Singleton {
private static volatile Singleton instance;
public static Singleton getInstance() {
if (instance == null) {
synchronized (Singleton.class) {
if (instance == null) instance = new Singleton();
}
}
return instance;
}
}6. 工厂模式 ★★★ 【简历亮点，高频追问】
三种形态：
- 简单工厂：一个工厂按参数返回不同产品，新增产品要改工厂的创建逻辑。
- 工厂方法：每个产品对应一个工厂，符合开闭原则。
- 抽象工厂：创建一族相关产品。
和策略模式的区别：工厂管「创建对象」，策略管「选择行为」。
典型落地是工厂 + 策略组合：按厂商 / 渠道编码拿到对应的解析器和处理器实现，新增一家只加一个实现类，主流程不动，正是开闭原则的体现。
7. 代理、装饰器、适配器、观察者、策略、模板方法 ★★★ 【简历亮点，高频追问】
- 代理：控制访问，分静态代理和动态代理（JDK 接口、CGLIB 继承），AOP 就是它的应用；业务里的日志、事务、权限都由 AOP 代理织入，不用手写。
- 装饰器：给对象叠加功能而不改原类，Java IO 的层层包装是典型。
- 适配器：把不兼容的接口转成兼容的，HandlerAdapter 是典型实现；对接多个第三方渠道时，各家字段和鉴权方式不同，统一包一层适配，上层只认自己的接口。
- 观察者：状态一变通知所有观察者，Spring 事件机制就是它。
- 策略：多个算法可互相替换，典型场景是不同支付渠道、不同计费规则各一套实现。
- 模板方法：父类定骨架、子类填步骤，JdbcTemplate 是典型；对账流程骨架固定（拉渠道账单 → 比对 → 处理差错账），不同渠道只填拉单和比对细节，也属于这个模式。
8. 代理模式与 AOP 的关系 ★★★
AOP 的底层就是代理：有接口用 JDK 动态代理，没接口用 CGLIB 继承。代理对象在方法前后织入通知（before / around / after）。
易错点：这也是 @Transactional 失效的常见原因——同类内部方法自调用不走代理对象，事务注解不生效，现象是内部方法抛异常但数据没有回滚。修复方式是把方法拆到另一个 Bean，或者注入自身代理。相关细节见 04 笔记。
9. 手写：反转链表、LRU（经典手撕）★★★
- 反转链表：用 prev / curr / next 三个指针逐步挪动，遍历时先存下
next，再改curr.next指向prev，最后整体前移。 - LRU：哈希表负责 O(1) 定位节点，双向链表维护访问顺序，get / put 都是 O(1)。用双向链表的原因：删除节点必须知道前驱，单向链表删除要 O(n)。
- 偷懒写法：
LinkedHashMap(accessOrder=true)重写removeEldestEntry。
本地缓存组件（如 Caffeine）的淘汰策略与 LRU 同源，目的都是防止本地缓存无限膨胀。
// 反转链表（迭代）
public ListNode reverseList(ListNode head) {
ListNode prev = null, curr = head;
while (curr != null) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}// 反转链表（迭代）
public ListNode reverseList(ListNode head) {
ListNode prev = null, curr = head;
while (curr != null) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}附：原始题库（旧版逐题，与上文重叠，可折叠跳过）
展开查看原始题库
11. 说说什么是单例模式
答：单例模式是一种常用的软件设计模式，在应用这个模式时，单例对象的类必须保证只有一个实例存在，整个系统只能使用一个对象实例。
优点：不会频繁地创建和销毁对象，浪费系统资源。
可能这会需要你手写一个单例模式，这就得自己去学了，因为单例模式有很多种写法，懒汉模式， 饿汉模式，双重检查模式等。懒汉模式就是用的时候再去创建对象，饿汉模式就是提前就已经加载好的静态static对象，双重检查模式就是两次检查避免多线程造成创建了多个对象。
单例模式有很多种的写法，我总结一下：
（ 1）饿汉式单例模式的写法：线程安全
（ 2）懒汉式单例模式的写法：非线程安全
（ 3）双检锁单例模式的写法：线程安全
12. 说说你对代理模式的理解
代理模式是给某一个对象提供一个代理，并由代理对象控制对原对象的引用。
优点：
代理模式能够协调调用者和被调用者，在一定程度上降低了系统的耦合度； 可以灵活地隐藏被代理对象的部分功能和服务，也增加额外的功能和服务。
缺点：
由于使用了代理模式，因此程序的性能没有直接调用性能高；
使用代理模式提高了代码的复杂度。
黄牛卖火车票：没有流行网络购票的年代是很喜欢找黄牛买火车票的，因为工作忙的原因，没时间去买票，然后就托黄牛给你买张回家过年的火车票。这个过程中黄牛就是代理人，火车票就是被代理的对象。
婚姻介绍所：婚姻介绍所的工作人员，搜集单身人士信息，婚介所的工作人员为这个单身人士找对象，这个过程也是代理模式的生活案例。对象就是被代理的对象。
注意了，问代理模式的时候，很有可能会问：动态代理。在Spring篇中已经讲述过，如果你把动态代理讲了后，很有可能还会问什么是静态代理？一个洞一个是静，大致也能才出来，就是中间代理层使我们手动写的，通常说的代理模式就是静态代理。
13. 说说工厂模式
答：简单工厂模式又叫静态工厂方法模式，就是建立一个工厂类，对实现了同一接口的一些类进行实例的创建。比如，一台咖啡机就可以理解为一个工厂模式，你只需要按下想喝的咖啡品类的按钮 （摩卡或拿铁），它就会给你生产一杯相应的咖啡，你不需要管它内部的具体实现，只要告诉它你的需求即可。
优点：
工厂类含有必要的判断逻辑，可以决定在什么时候创建哪一个产品类的实例，客户端可以免除直接创建产品对象的责任，而仅仅“消费”产品；简单工厂模式通过这种做法实现了对责任的分割，它提供了专门的工厂类用于创建对象；
客户端无须知道所创建的具体产品类的类名，只需要知道具体产品类所对应的参数即可，对于一些复杂的类名，通过简单工厂模式可以减少使用者的记忆量；
通过引入配置文件，可以在不修改任何客户端代码的情况下更换和增加新的具体产品类，在一
定程度上提高了系统的灵活性。
缺点：
不易拓展，一旦添加新的产品类型，就不得不修改工厂的创建逻辑；
产品类型较多时，工厂的创建逻辑可能过于复杂，一旦出错可能造成所有产品的创建失败，不利于系统的维护。
14. 抽象工厂模式
答：抽象工厂模式是在简单工厂的基础上将未来可能需要修改的代码抽象出来，通过继承的方式让子类去做决定。
比如，以上面的咖啡工厂为例，某天我的口味突然变了，不想喝咖啡了想喝啤酒，这个时候如果直接修改简单工厂里面的代码，这种做法不但不够优雅，也不符合软件设计的“开闭原则”，因为每次新增品类都要修改原来的代码。这个时候就可以使用抽象工厂类了，抽象工厂里只声明方法，具体的实现交给子类（子工厂）去实现，这个时候再有新增品类的需求，只需要新创建代码即可。
15. 装饰器模式是什么
答：装饰器模式是指动态地给一个对象增加一些额外的功能，同时又不改变其结构。
优点：装饰类和被装饰类可以独立发展，不会相互耦合，装饰模式是继承的一个替代模式，装饰模式可以动态扩展一个实现类的功能。
装饰器模式的关键：装饰器中使用了被装饰的对象。
比如，创建一个对象“laowang”，给对象添加不同的装饰，穿上夹克、戴上帽子......，这个执行过程就是装饰者模式。
一句名言：人靠衣裳马靠鞍。都是装饰器模式的生活案列。
16. 代理模式和装饰器模式有什么区别？
答：都是结构型模式，代理模式重在访问权限的控制，而装饰器模式重在功能的加强。
17. 模板方法模式
答：模板方法模式是指定义一个算法骨架，将具体内容延迟到子类去实现。
优点：
提高代码复用性：将相同部分的代码放在抽象的父类中，而将不同的代码放入不同的子类中；
. 实现了反向控制：通过一个父类调用其子类的操作，通过对子类的具体实现扩展不同的行为， 实现了反向控制并且符合开闭原则。
喝茶茶：烧水----放入茶叶---喝茶。放入的茶叶每个人自己的喜好不一样，有的是普洱、有的是铁观音等。
每日工作：上班打卡----工作---下班打卡。每个人工作的内容不一样，后端开发的、前端开发、测试、产品每个人的工作内容不一样。
18. 知道享元模式吗？
答：顾名思义就是被共享的单元。享元模式的意图是复用对象，节省内存，前提是享元对象是不可变对象。
具体来讲，当一个系统中存在大量重复对象的时候，如果这些重复的对象是不可变对象，我们就可以利用享元模式将对象设计成享元，在内存中只保留一份实例，供多处代码引用。这样可以减少内存中对象的数量，起到节省内存的目的。
典型的使用场景：Integer中cache，就是享元模式很经典的实现。
怎么看起来享元模式和单例模式是一毛一样的？面试官很有可能会继续问：
19. 享元模式和单例模式的区别？
答：单例模式是创建型模式，重在只能有一个对象。而享元模式是结构型模式，重在节约内存使用，提升程序性能。
享元模式：把一个或者多可对象霍村起来，用的时候，直接从缓存里获取。也就是说享元模式不一定只有一个对象。
20. 说说策略模式在我们生活的场景？
答：策略模式是指定义一系列算法，将每个算法都封装起来，并且使他们之间可以相互替换。
优点：遵循了开闭原则，扩展性良好。
缺点：随着策略的增加，对外暴露越来越多。
条条大路通罗马，条条大路通北京。
我们去北京的交通方式（策略）很多，比如说坐飞机、坐高铁、自己开车等方式。每一种方式就可以理解为每一种策略。
这就是生活中的策略模式。
21. 知道责任链模式吗？
答：是行为型设计模式之一，其将链中每一个节点看作是一个对象，每个节点处理的请求均不同， 且内部自动维护一个下一节点对象。当一个请求从链式的首端发出时，会沿着链的路径依次传递给每一个节点对象，直至有对象处理这个请求为止。
优点
解耦了请求与处理；
请求处理者（节点对象）只需关注自己感兴趣的请求进行处理即可，对于不感兴趣的请求，直接转发给下一级节点对象；
具备链式传递处理请求功能，请求发送者无需知晓链路结构，只需等待请求处理结果； 链路结构灵活，可以通过改变链路结构动态地新增或删减责任；
易于扩展新的请求处理类（节点），符合开闭原则；
缺点
责任链路过长时，可能对请求传递处理效率有影响；
如果节点对象存在循环引用时，会造成死循环，导致系统崩溃；
生活案列：我们在公司内部发起一个OA审批流程，项目经理审批、部门经理审批。老板审批、人力审批。这就是生活中的责任链模式，每个角色的责任是不同。
SpringMVC中的拦截器和Mybatis中的插件机制，都是拦截器经典实现。
22. 了解过适配器模式么？
答：适配器模式是将一个类的接口变成客户端所期望的另一种接口，从而使原本因接口不匹配而无法一起工作的两个类能够在一起工作。
优点：
可以让两个没有关联的类一起运行，起着中间转换的作用；
灵活性好，不会破坏原有的系统。
缺点：过多地使用适配器，容易使代码结构混乱，如明明看到调用的是 A 接口，内部调用的却是 B 接口的实现。
生活中的插座，为了适应各种插头，然后上面有两个孔的，三个空的，基本都能适应。还有万能充电器、 USB接口等。这些都是生活中的适配器模式。
23. 知道观察者模式吗？
答：观察者模式是定义对象间的一种一对多依赖关系，使得每当一个对象状态发生改变时，其相关依赖对象皆得到通知并被自动更新。观察者模式又叫做发布-订阅（Publish/Subscribe）模式、模型-视图（Model/View）模式、源-监听器（Source/Listener）模式或从属者（Dependents）模式。 优点：
. 观察者模式可以实现表示层和数据逻辑层的分离，并定义了稳定的消息更新传递机制，抽象了更新接口，使得可以有各种各样不同的表示层作为具体观察者角色；
观察者模式在观察目标和观察者之间建立一个抽象的耦合；
观察者模式支持广播通信；
观察者模式符合开闭原则（对拓展开放，对修改关闭）的要求。
缺点：
如果一个观察目标对象有很多直接和间接的观察者的话，将所有的观察者都通知到会花费很多时间；
如果在观察者和观察目标之间有循环依赖的话，观察目标会触发它们之间进行循环调用，可能导致系统崩溃；
观察者模式没有相应的机制让观察者知道所观察的目标对象是怎么发生变化的，而仅仅只是知道观察目标发生了变化。
在观察者模式中有如下角色：
Subject：抽象主题（抽象被观察者），抽象主题角色把所有观察者对象保存在一个集合里，每个主题都可以有任意数量的观察者，抽象主题提供一个接口，可以增加和删除观察者对象；
ConcreteSubject：具体主题（具体被观察者），该角色将有关状态存入具体观察者对象，在具体主题的内部状态发生改变时，给所有注册过的观察者发送通知；
Observer：抽象观察者，是观察者者的抽象类，它定义了一个更新接口，使得在得到主题更改通知时更新自己；
ConcrereObserver：具体观察者，实现抽象观察者定义的更新接口，以便在得到主题更改通知时更新自身的状态。
在Spring中大量的使用的观察者模式，只要看到是以Event结尾或者Publish开头的基本上都是观察者模式。
上面一共说了11种设计模式，这些设计模式能应对绝大多数人和面试场景来说。建议私下自己用代码实现一番，便于更好地理解。
附：一句话速记（可以跳过 ★☆☆）
- 希尔排序 / 基数排序 / 计数排序：非比较排序（基数、计数）在特定场景能到 O(n)，面试基本不考。
- KMP：字符串匹配算法，理解「利用已匹配信息避免回退」就行，手撕概率低。
- 建造者模式：链式构造复杂对象（
@Builder、StringBuilder），知道用途即可。 - 组合模式 / 桥接模式 / 享元模式：属于了解层面，面试问到说「用过享元思路做对象复用」足够。