中介者模式

中介对象封装一系列对象交互,使对象不需要显示地相互作用,从而使其低耦合松散,并可独立改变它们之间的交互。但是当同事类过多时,中介者的职责将变得复杂而庞大,以至于难以维护。

使用场景

当类图中出现蜘蛛网状结构。在这种情况下一定考虑使用中介者模式

类图

代码

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
public abstract class AbstractColleague {
protected AbstractMediator mediator;

public AbstractColleague(AbstractMediator mediator) {
this.mediator = mediator;
}
}

public class DevelopColleague extends AbstractColleague {

private String task;

public DevelopColleague(AbstractMediator mediator) {
super(mediator);
}

public void acceptTask(String task) {
this.task = task;
System.out.println("开发确认任务:" + task);
}

public void doneTask() {
System.out.println("开发完成任务:" + task);
super.mediator.reportProgress(task);
}
}

public class ProjectManageColleague extends AbstractColleague {
public ProjectManageColleague(AbstractMediator mediator) {
super(mediator);
}

public void generateTask() {
String task = "用户模块";
System.out.println("PM生成任务:"+task);
super.mediator.developColleague.acceptTask(task);
}

public void taskProgress(String task) {
System.out.println("PM确认项目进度:" + task + "完成");
}
}

public abstract class AbstractMediator {
protected DevelopColleague developColleague;
protected ProjectManageColleague projectManageColleague;

public DevelopColleague getDevelopColleague() {
return developColleague;
}

public void setDevelopColleague(DevelopColleague developColleague) {
this.developColleague = developColleague;
}

public ProjectManageColleague getProjectManageColleague() {
return projectManageColleague;
}

public void setProjectManageColleague(ProjectManageColleague projectManageColleague) {
this.projectManageColleague = projectManageColleague;
}

public abstract void reportProgress(String task);
public abstract void assignWork(String task);
}

public class ConcreteMediator extends AbstractMediator {

@Override
public void reportProgress(String task) {
super.projectManageColleague.taskProgress(task);
}

@Override
public void assignWork(String task) {
super.developColleague.acceptTask(task);
}
}

public class Client {
public static void main(String[] args) {
AbstractMediator mediator = new ConcreteMediator();
DevelopColleague developColleague = new DevelopColleague(mediator);
ProjectManageColleague projectManageColleague = new ProjectManageColleague(mediator);

mediator.setDevelopColleague(developColleague);
mediator.setProjectManageColleague(projectManageColleague);

projectManageColleague.generateTask();
developColleague.doneTask();
}
}

代理模式

为其他对象提供一种代理以控制对这个对象的访问

优点

  • 职责清晰
  • 高扩展

类图

代码实现

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
47
48
49
50
51
52
53
public interface Subject {
/**
* 业务方法
*/
void request();
}

public class RealSubject implements Subject {
@Override
public void request() {
// 具体的业务逻辑
}
}

public class Proxy implements Subject{

private final Subject subject;

/**
* 默认代理对象
*/
public Proxy() {
this.subject = new RealSubject();
}

public Proxy(Subject subject) {
this.subject = subject;
}

@Override
public void request() {
before();
this.subject.request();
after();
}

public void before() {
// 前置处理
}

public void after() {
// 后置处理
}
}

public class Client {
public static void main(String[] args) {
// 默认代理
new Proxy().request();
// 指定代理对象
new Proxy(new RealSubject()).request();
}
}

建造者模式

将一个复杂对象的构造与它的表示分离,使得同样的构建过程可以创建不同的表示

建造者最主要的功能是基本方法的调用顺序安排,也就是这些方法已经实现了,通俗的说就是零件的装配。而工厂方法则重点是创建,创建零部件是他的主要职责,组装顺序不是他关心的

优点

  1. 各个具体的建造者相互独立,有利于系统的扩展。
  2. 客户端不必知道产品内部组成的细节,便于控制细节风险。

缺点

  1. 产品的组成部分必须相同,这限制了其使用范围。
  2. 如果产品的内部变化复杂,该模式会增加很多的建造者类。

使用场景

  1. 相同的方法,不同的执行顺序而产生不同的结果
  2. 多个部件都可以组装到一个产品中,但产生的结果要求不同

通用类图

代码实现

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
public class Director {
private final AbstractBuilder concreteBuilder = new ConcreteBuilder();
public Product createProduct() {
// 构建产品不同的部件
concreteBuilder.buildPart();
return concreteBuilder.buildProduct();
}

}

public abstract class AbstractBuilder {
/**
* 构建零部件
*/
public abstract void buildPart();

/**
* 构建产品
* @return Product
*/
public abstract Product buildProduct();
}

public class ConcreteBuilder extends AbstractBuilder {

private final Product product = new Product();

@Override
public void buildPart() {
// 构建差异部分,即产品内部逻辑不同的部分
}

@Override
public Product buildProduct() {
return product;
}
}

public class Product {}

public class Client {
public static void main(String[] args) {
Director director = new Director();
director.createProduct();
}
}

6 大设计原则

  • 单一职责原则
  • 里氏替换原则
  • 依赖倒置原则
  • 接口隔离原则
  • 迪米特法则
  • 开闭原则

单一职责(Single Responsibility Principle)

  • 应该有且仅有一个原因引起类的变化

    对于职责的划分因项目而异,因环境而异。接口一定要做到单一职责,类的设计做到只有一个原因能引起变化。

里氏替换原则(Liskov Substitution Principle)

  • 所有引用基类的地方都必须能够透明的使用其子类的对象

    继承能够提高代码重用性,提高代码可扩展性。但具有侵入性,降低代码灵活性,增强了代码的耦合性。

    子类中方法的前置条件必须与超类中被覆写的方法的前置条件相同或者更宽松。

    在类中调用其他类时务必要使用父类或接口,如果不能使用,则说明类的设计已经违背了 LSP 原则。

    如果子类不能完整地实现父类的方法,或者父类的某些方法在子类中已经发生“畸变”,则建议断开父子继承关系,采用依赖、聚集、组合等关系代替继承。

依赖倒置原则(Dependency inversion principle)

  • 高层模块不应该依赖低层模块,两者都应依赖其抽象、抽象不应该依赖细节、细节应该依赖抽象。(面向接口编程)

    能够减少类间的耦合性。

    接口负责定义public属性和方法,并且声明与其他对象的依赖关系,抽象类负责公共构造部分的实现, 实现类准确的实现业务逻辑,同时在适当的时候对父类进行细化

接口隔离原则(Interface Segregation Principle)

  • 接口尽量细化、同时接口方法尽量少

    一个接口只服务于一个子模块或业务逻辑;通过业务逻辑压缩接口中的方法;已经污染的接口尽量去修改,若变更的风险较大,则采用适配器模式转化处理

迪米特法则(Law of Demeter)

  • 一个类应该对自己需要调用/耦合的类知道得最少。

    在实际应用中,如果一个类跳转两次以上才能访问到另一个类,就需要想办法进行重构了,跳转次数越多,系统越复杂,维护就越困难。

开闭原则(Open Close Principle)

  • 软件实体应该对扩展开放,对修改关闭

    软件实体应该通过扩展来实现变化,而不应该通过修改已有的代码来实现变化

IEEE 754

IEEE二进制浮点数算术标准(IEEE 754)是20世纪80年代以来最广泛使用的浮点数运算标准,为许多CPU与浮点运算器所采用。这个标准定义了表示浮点数的格式(包括负零-0)与反常值(denormal number)),一些特殊数值(无穷(Inf)与非数值(NaN)),以及这些数值的“浮点数运算符”;它也指明了四种数值舍入规则和五种例外状况(包括例外发生的时机与处理方式)。

最高位 sign 标志位(0正、1负)
指数偏移值 exponent

  • 单精度 8 位: $2^{8-1}-1$ = 127
  • 双精度 11 位: $2^{11-1}-1$ = 1023

有效数字 fraction

  • 单精度 23 位
  • 双精度 52 位

转二进制

例如 4.375

  1. 先转整数部分(除 2 取余)

    • 4 / 2 = 2 余 0
    • 2 / 2 = 1 余 0
    • 1 / 2 = 1 余 1

      4 = 100

  2. 再转小数部分(乘 2 取整)

    • 0.375 * 2 = 0.75 记 0
    • 0.75 * 2 = 1.5 记 1
    • 0.5 * 2 = 1 记 1

      0.375 = 011

所以 4.375 二进制为 100.011


0.2 转 2 进制:0.00110011001100110011001100110011001100110011…..
小数点移至第一个 1 的右侧, 1.10011001100110011001100110011001100110011…..。偏移值为移动次数(左移为加、右移为减)这里为 -3
偏移值 127 - 3 = 01111100
有效数字为小数点后 23 位 (24 位若为 1 则进位,此时存的值比实际值略大)
根据IEEE 754规定存储的 0.2 二进制为 0|01111100|10011001100110011001101

转回十进制

V = (-1)^s *(1+M)* 2^(E-127)(单精度)
V = (-1)^s *(1+M)* 2^(E-1023)(双精度)
s: 标志位
M: 有效数值
E: 指数偏移值

$(-1)^0$ * (1 + 5033165 * $2^{-23}$) * $2^{(124-127)}$ ≈ 0.20000000298023

1
2
3
public static void main(String[] args) {
System.out.println(String.format("%.18f", 0.2f)); // 0.200000002980232240
}

结论:计算机存储的浮点数是近似值

堆排序

堆通常是一个可以被看做一棵树的数组对象。堆的实现通过构造二叉堆(binary heap),实为二叉树的一种

  • 任意节点小于(或大于)它的所有后裔,最小元(或最大元)在堆的根上(堆序性)。
  • 堆总是一棵完全树。即除了最底层,其他层的节点都被元素填满,且最底层尽可能地从左到右填入。

最大堆:根节点最大
最小堆:根节点最小

思路

利用堆的这个特性,可以知道根节点一定是最大值。

将根节点与最后一个叶子节点互换。每次使用n-i个节点继续多次即可(i 为已经交换过的次数)

实现

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
class HeapSort(private val node: IntArray) {
fun sort() {
for (i in 1 until node.size) {
// 构建确保根节点一定最大的堆
buildHeap(node.size - i)
// 根节点与最后一个叶子节点交换
swap(node.size - i)
}
println(node.contentToString())
}

private fun swap(lastIndex: Int) {
val temp = node[0]
node[0] = node[lastIndex]
node[lastIndex] = temp
}

private fun buildHeap(lastIndex: Int) {
/*
从最后一个父节点开始,使其一定大于其子节点。
再继续倒数第二个父节点依然保证其比子节点大
不需要关心下调的节点是否比子节点大,因为上调的节点一定是最大值,我们只需要找出最大值即可。
*/
for (i in (lastIndex - 1) / 2 downTo 0) {
var child = i * 2 + 1
val temp = node[i]
// 存在右节点且比左节点大
if (child + 1 <= lastIndex && node[child] < node[child + 1]) {
child++
}
// 若子节点比父节点大,则父节点下调
if (node[i] < node[child]) {
node[i] = node[child]
node[child] = temp
}
}
}
}

fun main() {
HeapSort(intArrayOf(1, 3, 2, 6, 5, 7, 8, 9, 10, 30)).sort()
}

动态规划算法

动态规划(dynamic programming)是运筹学的一个分支,是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时,提出了著名的最优化原理(principle of optimality),把多阶段过程转化为一系列单阶段问题,利用各阶段之间的关系,逐个求解,创立了解决这类过程优化问题的新方法——动态规划。1957年出版了他的名著《Dynamic Programming》,这是该领域的第一本著作。

题型

背包问题:给定 n 种物品和一个容量为 C 的背包,物品 i 的重量是 wi,其价值为 vi 。
问:应该如何选择装入背包的物品,使得装入背包中的物品的总价值最大?

解法

寻找状态转移方程
F(n, c) = max(F(n-1, c), F(n-1,c-i)+vi)(n≥1, c≥wi)
利用状态转移方程式自底向上求解问题
即买还是不买,若是买,则找出买后背包剩余空间的最大价值(上一轮循环)加上当前价值即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static void main(String[] args) {
int c = 10;
int[] w = {2, 5, 4, 4, 1};
int[] v = {5, 10, 10, 5, 1};

int[] results = new int[c + 1];
for (int n = 1; n <= w.length; n++) {
for (int j = c; j >= 1; j--) {
if (j>=w[n-1]) {
results[j] = Math.max(results[j], results[j - w[n - 1]] + v[n - 1]);
}
}
}
System.out.println(results[c]);
}}

位图算法(bitMap)

内存中连续的二进制位(bit) 所组成的数据结构,主要用于大量整数数据去重查询操作

举例

要插入 1,2,3,4 的数字、先在内存中申请长度为 10 位的 bitMap,所有 bit 位分别对应 0 ~ 9 的整型值。

判断 4 是否在 bitMap 中
我们知道,在二进制中,0 代表 false 、1 true
将上面的位图用二进制表示:
将其做与(&)运算:0000011110 & 0000010000 = 0000010000

添加值到 bitMap 中
即并集; 做或(|)运算: 0000001110 | 0000010000 = 0000011110

不包括 4 的值
做异或(^)运算:0000011110 ^ 0000010000 = 0000001110

阅读全文 »

在线演示

A 星算法

A*搜寻算法俗称A星算法。A*算法是比较流行的启发式搜索算法之一,被广泛应用于路径优化领域。它的独特之处是检查最短路径中每个可能的节点时引入了全局信息,对当前节点距终点的距离做出估计,并作为评价该节点处于最短路线上的可能性的量度

概念

OpenList: 能走的节点
CloseList: 走过的节点
节点评估公式:F = G + H

  • G:从起点到当前节点走过的节点数
  • H:忽视障碍物,从当前节点到目的节点距离
  • F:总体评估值,越低表示最优

举例

活动图

阅读全文 »

二叉树

满二叉树: 所有非叶子都有左右节点、所有叶子节点都在同一级
完全二叉树:满二叉树的特例,路径需跟满二叉树一致、但不要求都有左右叶子(即最后一层不满)

遍历

  • 深度优先遍历

    仅有前序和后序遍历,不能确定一个二叉树,必须有中序遍历的结果

    L、D、R分别表示遍历左子树、访问根结点和遍历右子树

    • 先序遍历:DLR
    • 中序遍历:LDR
    • 后序遍历:LRD
  • 广度优先遍历
    • 层序遍历:从根节点到叶子节点逐层遍历到叶子节点

性质

  • 二叉数
    • 性质1:在二叉树中第 i 层的结点数最多为 $2^{i-1}$ (i≥1)
    • 性质2:高度为 k 的二叉树其结点总数最多为 $2^k-1$ (k≥1)
    • 性质3:叶子的个数为 $n_0$,度为 2 的结点数为 $n_2$,则:$n_0 = n_2 + 1$
      • 节点数 = $n_0$ + $n_1$ + $n_2$
      • 节点数 - 1 = 边
      • $n_0$ + $n_1$ + $n_2$ - 1 = 0 * $n_0$ + 1 * $n_1$ + 2 * $n_2$
      • $n_0$ - 1 = $n_2$
      • $n_0$ = $n_2$ + 1
  • 满二叉树
    • 性质4:第 i 层上的节点数为 $2^{i-1}$
  • 完全二叉树
    • 性质5:对于具有 n 个结点的完全二叉树的高度为 $log_n^2$ + 1