软件设计师笔记(三)-设计模式和算法设计

本文内容来自笔者学习zst 留下的笔记，都是零碎的要点，查缺补漏，希望大家都能通过，记得加上免费的关注！谢谢！本章主要以下午题出现形式为主！

文章编辑于：2024-5-13 13:43:47

目录

1. 设计模式考试要点：

1.1 创建型

1.1.1 Product Method(工厂方法) 类模式

1.1.2 Abstract Factory(抽象工厂模式)

1.1.3 Builder(生成器模式)

1.1.4 Prototype(原型模式)

1.1.5 Singleton(单例)

1.2 结构性模式

1.2.1 Adapter(适配器) 类模式

1.2.3 Bridge(桥接)

1.2.4 Composite(组合)

1.2.5 Decorator(装饰器)

1.2.6 Facade(外观)

1.2.6 Flyweight(享元)

1.2.7 Proxy(代理)

1.3 行为设计模式

1.3.1 Chain of Responsibility （责任链）

1.3.2 Command（命令）

1.3.3. Interptreter（解释器）类模式

1.3.4 Iterator(迭代器)

1.3.5 Mediator(中介者)

1.3.6 Memento(备忘录)

1.3.7 Observer(观察者)

1.3.8 State（状态）

1.3.9 Strategy (策略)

1.3.10 Template Method（模板方法） 类模式

2. 算法设计

2.1 回溯法

2.2 分治法

2.3 动态规划

---

1. 设计模式考试要点：

记忆：

类模式【4种】： 工厂方法类模式，适配器类模式，解释器类模式，模板方法类模式，

创建型： 丹丹原本想去超市买生抽，但去了工厂。

结构性：ABCDFFP (首字母)

行为性：xxx(自己记xxx)

注意：适配器： 属于结构性模式，存在适配器类模式和适配器对象模式！

1.1 创建型

1.1.1 Product Method(工厂方法) 类模式

关键词Product

1.1.2 Abstract Factory(抽象工厂模式)

1.1.3 Builder(生成器模式)

1.1.4 Prototype(原型模式)

1.1.5 Singleton(单例)

1.2 结构性模式

1.2.1 Adapter(适配器) 类模式

1.2.3 Bridge(桥接)

1.2.4 Composite(组合)

1.2.5 Decorator(装饰器)

1.2.6 Facade(外观)

1.2.6 Flyweight(享元)

1.2.7 Proxy(代理)

1.3 行为设计模式

1.3.1 Chain of Responsibility （责任链）

1.3.2 Command（命令）

1.3.3. Interptreter（解释器）类模式

1.3.4 Iterator(迭代器)

1.3.5 Mediator(中介者)

1.3.6 Memento(备忘录)

1.3.7 Observer(观察者)

1.3.8 State（状态）

1.3.9 Strategy (策略)

1.3.10 Template Method（模板方法） 类模式

2. 算法设计

2.1 回溯法

经典例子：N皇后的问题

注意不能在同一行，不能在斜线上，

假如使用一维数组表示第I行位置的位置Q[i], j作为下一行的位置

判断同一行的话就是Q[i] == Q[j]

判断同一斜线：abs(i-j) == fabs(Q[i]-Q[j])

2.2 分治法

常常使用到递归；

经典例子：阶乘，归并排序, 硬币查真假

递归排序算法

时间复杂度O(nlog2n)

空间复杂度O(n)

硬币查真假问题

2.3 动态规划

经典例子：0-1 背包问题

矩阵连乘

最长公共子序列

0-1背包，时间复杂度：O(NW) N是价值，W是重量

0-1背包，空间复杂度：O(NW)