设计模式总结

一、设计模式七大原则

  1. 单一职责原则:不要存在多于一个导致变更的原因。通俗的说,即一个类只负责一项职责。
  2. 开-闭原则:“对可变性封装”,对扩展开放,对修改闭合。
  3. 里氏替换原则:一个软件实体,如果使用的是一个基类的话,一定适用于其子类,而且根本不能察觉出基类对象和子类对象的区别。在软件中如果能够使用 基类对象,那么一定能够使用其子类对象。
  4. 依赖倒置原则:高层模块不应该依赖低层模块,抽象不应该依赖细节,细节应该依赖于抽象。
  5. 接口隔离原则:使用多个专门的接口比使用单一的总接口要好。解决“胖接口”问题。
  6. 组合/聚合复用原则:要尽量使用组合/聚合,尽量不要使用继承。继承不灵活,紧耦合。
  7. 迪米特法则:一个对象应该对其他对象有尽可能少的了解。“不要跟陌生人说话”。

二、创建型模式

1.简单工厂模式(★★★)

定义一个工厂类,它可以根据参数的不同返回不同类的实例,被创建的实例通常都具有共同的父类。因为在简单工厂模式中用于创建实例的方法是静态方法,因此简单工厂模式又被称为静态工厂方法。
简单工厂模式

2.工厂方法模式(★★★★★)

简单工厂模式虽然简单,但存在一个很严重的问题。当系统中需要引入新产品时,由于静态工厂方法传入的参数的不同来创建不同的产品,这必定要修改工厂类的源代码,这将违背“开闭原则”,如何实现增加新产品而不影响已有代码?————工厂方法模式。
工厂方法模式
优点:良好的封装性,扩展性好,屏蔽产品类,典型的解耦框架。

3.抽象工厂模式(★★★★★)

工厂方法模式通过引入工厂等级结构,解决了简单工厂模式中工厂类职责太重的问题,但由于工厂方法模式中的每个工厂只产生一类产品,可能会导致系统中存在大量的工厂类。强化工厂职责,可以创建不同产品。
抽象工厂模式

4.单例模式(★★★★★)

单例模式的目的是保证一个类仅有一个实例,并提供一个访问它的全局访问点。单例模式包含的角色只有一个,就是单例类——Singleton。单例拥有一个私有构造函数,确保用户无法通过new关键字直接实例化它。
除此之外,该模式中包含一个静态私有成员变量与静态公有的工厂方法,
该工厂方法负责检验实例的存在性并实例化自己,然后存储在静态成员变量中,以确保只有一个实例被创建。这个模式代码很关键

1
2
3
4
5
6
7
8
9
10
public class Singleton {
private static Singleton instance=null; //静态私有成员变量
//私有构造函数
private Singleton() { } //静态公有工厂方法,返回唯一实例
public static Singleton getInstance() {
if(instance==null)
instance=new Singleton();
return instance;
}
}

单例模式
注意以下三点:
1)单例类中的构造函数为私有;
2)私有静态成员变量;
3)提供一个公有的静态工厂方法。
优点:
1)提供了对唯一实例的受控访问;
2)可以节约系统资源;
3)允许可变数目的实例。
缺点:
1)没有抽象层,单例类的扩展有很大的困难;
2)单例类的职责过重;
3)滥用单例将带来一些负面影响(连接池溢出、自动回收状态丢失)

5.建造者模式(★★★)

借用吴佳洪同学的一句话:“其实很多方法稍微改一点,就会成为另外一种方法,都很像。”个人感觉建造者模式与抽象工厂模式的区别就是在于,抽象工厂模式是将不同产品的某个部分的所有方法集中到一个类中,而建造者模式是对某一个产品的所有方法放到一起。
建造者模式利用一个导演者对象和具体建造者对象一个一个地建造出所有的零件,从而建造出完整的对象。
建造者模式
优点:
1)不需要知道产品内部组成的细节,将产品本身与产品的创建过程解耦;
2)每一个建造者相对独立;
3)可以更加精细的控制产品的创建过程;
4)扩展性强。
缺点:
1)组成部分差异太大,不适合使用建造者;
2)内部变化复杂,导致系统修改工作量很大。

6.原型模式(★★★★)

客户请求一个原型克隆自身。
1)深克隆:成员对象克隆
2)浅克隆:成员对象不克隆
原型模式

7.创建型模式小结

Summary

三、结构型模式

1.适配器模式(★★★★)

在不改变原有实现的基础上,将原先不兼容的接口转换成兼容的接口。
适配器模式

2.桥接模式(★★★)

将抽象部分与与它的实现部分分离,使它们都可以独立地变化。个人理解这个模式很简单,就是把共有的属性单独提取出来当作一个类来管理,实现复用。将乘法变成加法。
桥接模式

3.组合模式(★★★★)

典型应用:文件管理器。文件是Leaf,文件夹是Composite。
组合模式的关键是定义了一个抽象的构件类,它既可以代表叶子,也可以代表容器,而客户端针对该抽象构件类进行编程,无需知道它到底表现的是叶子还是容器,可以对其惊醒同意处理。容器对象与抽象构件类之间可以建立聚合关系,在容器对象中既可以包好叶子,也可以包含容器,一次实现地贵组合。
组合模式

4.装饰模式(★★★)

通过继承动态地给一个对象增加一些额外的职责。
朱项宁这样给我们讲的,就像游戏中每个角色可以有不同的衣服,游戏中的角色可以动态地选择穿什么衣服或者不穿衣服。
装饰模式

5.享元模式(★)

“浪费可耻,节约光荣”,享元模式有效节约内存资源。
享元技术有效支持大量细粒度的对象。当对象的力度太小的时候,大量对象将会产生巨大的资源消耗,因此考虑使用共享对象来实现逻辑上的大量对象。
举例:一个字符串,每个字母出现多次,可是其形状是一样的,’a’就是‘a’,不可能是’b’,这就是享元的内蕴状态,而其可能出现的位置不一样,字体可能不一样,这就是享元的外蕴状态。
享元模式

6.facade(读音:法萨德)门面模式(★★★★★)

简化外部客户程序和系统间的交互接口。联想相机多种模式,夜间肖像。封装细节,用户只关心需要而且能够达到的效果,不需要知道内部实现细节。正好吻合(依赖倒置原则)
facade模式

7.代理模式(★★★★)

增加一层间接层作为代理以控制对这个对象的访问。
想象访问某些网站应用的代理服务,经过一层代理,虽然你没有与外部网站有直接访问,但是效果和直接访问是一样的,当然效率可能变慢,代价更高。这个问题想深入探讨,应该找顾少男,你们懂的。
但是有点是,这个对象的细节没有直接暴露,可以用代理控制对对象的访问(访问网站的例子,账号没钱了,访问不了)。还有一点,也是与适配器模式不同的地方,代理模式提供了一个与Subject的接口相同的接口(访问网站的例子,要访问的网站没有做任何改动,只是控制是否能够访问)。代理模式

8.结构型模式小结
小结

四、行为型模式

1.解释器模式(★)

给定一个语言,定义它的问他的一种表示,并定义一个解释器,这个解释器使用该表示来解释语言中的句子。如加减法的解释器,只要输入一个加法/减法表达式,它就能够计算出表达式结果。
输入”1 + 2 - 3 + 4”, 直接输出3(解释器是任珉做的)。
解释器模式

2.模板方法模式(★★★)

解决复用问题,如C++的STL库中的模板,各个类的方法很类似,其内部方法有很多函数名称也是相同的。但是其内部实现原理可能是不相同的,比如vector和list都有size()函数,但是vector是有字段记录size值,而list每调用size()都需从头遍历一遍,所以二者的size()函数表面上看起来相同,其实实现的时间复杂度分别为O(1)和O(n)。
回到模板方法模式,也是一样,我们能够写一个Template,在其中编码了那些高层的 策略、规则、流程。需要针对具体问题进行精化时,我们通过继承来扩展 这个Template中的一些细节。
还有一个例子是数据库中DBMS——Oracle和MS SQL Server,这个课件上有讲,你们可以看课件。
模板方法模式

3.责任链模式(★★)

使多个对象都有机会处理请求,从而避免请求的发送 者和接收者之间的耦合关系。将这些对象连成一条链, 并沿着这条链传递该请求,直到有一个对象处理它为止。
课件中请假的例子。 请假天数不同,批假者相应不同(1-2天经理批假,3-5天人事批假。。。),而对于请假者事先不需要了解是谁批假,也就是说对于请假者是个黑盒,管他谁批假呢,老子就是想请100天的假。
责任链模式

4.命令模式(★★★★)

将“行为请求者”与“行 为实现者”解耦,将一个请求封装为一个对象,从而使你可用不同的请 求对客户进行参数化;对请求排队或记录请求日志,以及支持可撤销的操作。把请求信息和请求执行过程封装起来,中间通过命令实现二者之间的联系。
命令模式

5.迭代器模式(★★★★★)

提供一种方法顺序访问一个聚集对象中各个元素, 而又不需暴露该对象的内部表示。就像C++的STL库中iterator,迭代器可以顺序访问某些类中的各个元素,虽然这些类不同,但是对于迭代器来说,访问方式是一样的。通俗来讲,不管是数组,还是链表,对于迭代器而言都可以顺序访问,而且定义了迭代器之后的访问的操作方法是相同的。
迭代器模式

6.策咯模式(★★★★)

每一个类封装一种具体的算法,在这里,每一个封装算法的类我们都可以称之为一种策略(Strategy),为了保证这些策略在使用时具有一致性,一般会提供一个抽象的策略类来做规则的定义,而每种算法则对应于一个具体策略类。
如电影院要为不同类型的用户提供不同的电影票打折方式,具体打折方案如下:
(1) 学生凭学生证可享受票价8折优惠;
(2) 年龄在10周岁及以下的儿童可享受每张票减免10元的优惠(原始票价需大于等于20元);
(3) 影院VIP用户除享受票价半价优惠外还可进行积分,积分累计到一定额度可换取电影院赠送的奖品。
该系统在将来可能还要根据需要引入新的打折方式。
策略模式的主要目的是将算法的定义与使用分开,也就是将算法的行为和环境分开
策略模式

7.调停者模式(★★)

用一个中介对象来封装一系列的对象交互。中介者使 各对象不需要显式地相互引用,从而使其耦合松散, 而且可以独立地改变它们之间的交互。
调停者模式

7.观察者模式(★★★★★)

定义对象间的一对多的依赖关系,当一个对象的状态发生改变时,所有依赖于它的对象都得到通知并被自动更新。
游戏中,某个玩家牺牲,会广播通知所有其他玩家,其中有一个实时更新的类监听玩家的状态变化。
观察者模式

8.备忘录模式(★★)

用一个类记录某个时候的状态,这样以后就可将该对 象恢复到原先保存的状态。
备忘录模式

9.状态模式(★★★)

允许一个对象在其内部状态改变时改变它的行为。对象看起来似乎修改了它的类。对于客户端而言,无须关心对象状态的转换以及对象所处的当前状态,无论对于何种状态的对象,客户端都可以一致处理。
状态模式

10.访问者模式(★)

可以在不改变各元素的类的前提下定义作用于这些元素的新操作。
想必大家都去过医院,虽然没有人喜欢去医院(爱岗敬业的医务工作人员除外,微笑)。在医生开具处方单(药单)后,很多医院都存在如下处理流程:划价人员拿到处方单之后根据药品名称和数量计算总价,药房工作人员根据药品名称和数量准备药品,我们可以将处方单看成一个药品信息的集合,里面包含了一种或多种不同类型的药品信息,不同类型的工作人员(如划价人员和药房工作人员)在操作同一个药品信息集合时将提供不同的处理方式,而且可能还会增加新类型的工作人员来操作处方单。
在软件开发中,有时候我们也需要处理像处方单这样的集合对象结构,在该对象结构中存储了多个不同类型的对象信息,而且对同一对象结构中的元素的操作方式并不唯一,可能需要提供多种不同的处理方式,还有可能增加新的处理方式。在设计模式中,有一种模式可以满足上述要求,其模式动机就是以不同的方式操作复杂对象结构,该模式就是我们本章将要介绍的访问者模式。
访问者模式

五、备注

如有不懂可以问5104首席架构师朱项宁高工

C++基本知识积累

image

const与#define

  1. 编译器处理方式不同:define宏是在预处理阶段展开,const常量是编译运行阶段使用;
  2. 类型和安全检查不同:define宏没有类型,不做任何类型检查,仅仅是展开,const常量有具体类型,在编译阶段会执行类型检查;
  3. 存储方式不同:define宏是展开,有多少地方使用,就展开多少次,不会分配内存,const常量会在内存中分配(可以是堆中,也可以是栈中);
  4. const可以节省空间;
  5. const可以提高运行效率。

vector内存满时增长方式

一般成倍指数增长

static

静态全局变量
在全局变量前,加上关键字static,该变量就定义称为一个静态全局变量,静态全局变量有以下特点:

  1. 该变量在全局数据区分配内存;
  2. 未经初始化的静态全局变量会被程序自动初始化为0;
  3. 静态全局变量在声明它的整个文件都是可见的,而在文件之外是不可见的。
    静态局部变量
    在局部变量前,加上关键字static,该变量就被定义成一个静态局部变量,静态局部变量有以下特点:
  4. 该变量在全局数据区分配内存;
  5. 静态局部变量在程序执行到该对象的声明处时被首次初始化,即以后的函数调用不再初始化;
  6. 如果没有初始化,会被自动初始化为0;
  7. 它始终驻留在全局数据区,直到程序运行结束。但其作用域为局部作用域,当定义它的函数或语句块执行结束时,其作用域也随之结束。
    静态函数
    在函数的返回类型前加上static关键字,函数即被定义为静态函数。静态函数与普通函数不同,它只能在声明它的文件当中可见,不能被其它文件使用。

MySQL索引算法原理解析

原文出处:MySql索引算法原理解析

B-tree

B-tree,B是balance,一般用于数据库的索引。使用B-tree结构可以显著减少定位记录时所经历的中间过程,从而加快存取速度。而B+tree是B-tree的一个变种,大名鼎鼎的MySQL就普遍使用B+tree实现其索引结构。

索引的优点

一般来说,索引本身也很大,不可能全部存储在内存中,因此索引往往以索引的形式存储在磁盘上。这样的话,索引查找的过程中就要产生磁盘I/O消耗,相对内存存取,I/O存取的消耗要高几个数量级,所以评价一个数据结构作为数据库索引的优劣程度的重要指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。换句话说索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。
为了达到这个目的,磁盘按需读取,要求每次预读的长度一般为页的整数倍。而且数据库系统将一个页的大小设定为等于一个页,这样每个节点只需要一次I/O就可以完全载入

B-tree特性

  1. 树中每个节点至多有m个孩子;
  2. 除根结点和叶子节点外,其他每个节点至少有ceil(m/2)个孩子;
  3. 若根结点不是叶子节点,则至少有两个孩子;
  4. 所有叶子节点都出现在同一层,叶子节点不包含任何关键信息;

B-tree

示例

插入(insert)操作:插入一个元素时,首先判断在B-tree中是否存在,如果不存在,即在叶子节点处结束,然后在叶子节点处插入新的元素,如果空间满了,没有足够的空间插入新的元素,则将该节点进行“分裂”,将左右两半的关键字元素分开,中间元素上移到父节点中,如此递归,如果到根结点仍需上移,则新增加一层。
删除(delete)操作:首先查找B-tree中需要删除的元素,如果该元素在B-tree中存在,则将该元素在其节点中删除,如果删除该元素后,判断是否有孩子节点,若有,上移最近元素,递归到根结点。

聚类基本概念

基本概念

聚类是对点集进行考察并按照某种距离测度将它们聚成多个“簇”的过程。聚类的目标是使得同一簇内的点之间距离较小,而不同簇之间的距离较大。聚类的过程即是发现簇的过程。

聚类技术介绍

按照聚类算法所使用的两种不同的基本策略,可以将聚类分为两类。

  1. 一类称为层次聚类或凝聚式算法。这类算法一开始将每个点都看成一个簇。簇与簇之间是按照接近度来组合,而接近度可以基于“接近”的不同含义采用不同的定义。当进一步的组合导致多个原因之一下的非期望结果时,上述组合过程结束。例如,达到预先给定数目的簇时,或者簇内点分散到达一定程度。
  2. 另一类算法涉及点分配过程,即按照某个顺序依次考虑某个点,并将它分配到最适合的簇中,该过程通常都有一个短暂的初始簇估计阶段。

维数灾难

高维的欧氏空间具有一些非直观的有时被称为“维数灾难的性质。非欧空间也往往有同样的反常情况。“灾难”的一个表现是,在高维空间下,几乎所有的点对之间的距离都差不多相等。另一个表现是,几乎任意两个向量之间都是近似正交的。

LeetCode num064

Minimum Path Sum

Problem

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution
{
public:
int minPathSum(vector<vector<int> > &grid)
{

int row = grid.size();
if (row == 0) return 0;
int column = grid[0].size();
if (column == 0) return 0;
vector<vector<int>> markMin = grid;
for (int i = 0; i < row; i++)
{
for (int j = 0; j < column; j++)
{
if (i == 0 && j == 0) markMin[i][j] = grid[0][0];
else if (i == 0) markMin[i][j] = markMin[i][j - 1] + grid[i][j];
else if (j == 0) markMin[i][j] = markMin[i - 1][j] + grid[i][j];
else markMin[i][j] = (markMin[i][j - 1] < markMin[i - 1][j] ?
markMin[i][j - 1] : markMin[i - 1][j]) + grid[i][j];
}
}
return markMin[row - 1][column - 1];
}
};

Comment

  1. 时间复杂度O(m*n)
  2. 动态规划

LeetCode-num117

Populating Next Right Pointers in Each Node II
beautiful!

Problem

Follow up for problem “Populating Next Right Pointers in Each Node”.

What if the given tree could be any binary tree? Would your previous solution still work?

Note:

You may only use constant extra space.
For example,
Given the following binary tree,

1
2
3
4
5
    1
/ \
2 3
/ \ \
4 5 7

After calling your function, the tree should look like:

1
2
3
4
5
     1 -> NULL
/ \
2 -> 3 -> NULL
/ \ \
4-> 5 -> 7 -> NULL

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/**
* Definition for binary tree with next pointer.
* struct TreeLinkNode {
* int val;
* TreeLinkNode *left, *right, *next;
* TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
* };
*/

class Solution
{
public:
void connect(TreeLinkNode *root)
{

queue<TreeLinkNode *> queNode;
TreeLinkNode *leftTempNode, *rightTempNode, *nowTempNode;
queue<int> queLevel;
int level = 0, nowLevel;
if (root == NULL) return;
queNode.push(root);
queLevel.push(level);
nowLevel = queLevel.front();
nowTempNode = queNode.front();
while (!queNode.empty())
{
queLevel.pop();
queNode.pop();
if (nowTempNode->left != NULL)
{
queNode.push(nowTempNode->left);
queLevel.push(nowLevel + 1);
}
if (nowTempNode->right != NULL)
{
queNode.push(nowTempNode->right);
queLevel.push(nowLevel + 1);
}
if (queNode.empty()) break;
if (nowLevel == queLevel.front())
{
nowTempNode->next = queNode.front();
}
nowTempNode = queNode.front();
nowLevel = queLevel.front();
}
}
};

Comment

  1. 上一道题代码竟然可以直接用。