设计模式:Proxy

Proxy

概述

用代理的形式访问对象

应用场景

对于一个controller,调用它执行函数时将Tag切换到对应的页面

使用方法

1
export const Controller = new Proxy(ControllerBase, handler);

其中ControllerBase是被代理的对象,而handler是代理的具体实现

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
const COLOR_UPDATE_FUNCTION_NAME = ["updatePaletteInfos", "updateQuantization"];

const EYE_UPDATE_FUNCTION_NAME = [
"updateEyeModel",
"updateEyeComponentColor",
"updateEyeSeperated",
];

const BASE_UPDATE_FUNCTION_NAME = ["updateBaseModel", "updateBaseColor"];

const TRANSFORMCONTROLLER_UPDATE_FUNCTION_NAME = [
"updateModelPosition",
"updateModelRotation",
"updateModelScale",
"resetModel",
"resetUndo",
"lockedScale",
"lockedcaleModel",
"updateBaseSeperated",
];

const EMIT_SERIALIZE_FUNCTION_NAME = [
...EYE_UPDATE_FUNCTION_NAME,
...COLOR_UPDATE_FUNCTION_NAME,
...BASE_UPDATE_FUNCTION_NAME,
];

// 代理模式,用于监听函数触发,统一进行调用。
const handler = {
//target是需要被代理的对象,receiver是代理本身
construct(target: any, args: any) {
const instance = new target(...args);
return new Proxy(instance, {
get(target: any, prop: string, receiver: any) {
//将this绑定到receiver而不是target
const originalMethod = Reflect.get(target, prop, receiver);

if (EMIT_SERIALIZE_FUNCTION_NAME.includes(prop)) {
return (...args: any[]) => {
const result = originalMethod.apply(receiver, args);

// 对于不同的操作,会需要触发到不同的 tab.
let targetStep = EditorStep.COLOR;
if (EYE_UPDATE_FUNCTION_NAME.includes(prop)) {
targetStep = EditorStep.EYES;
}
if (BASE_UPDATE_FUNCTION_NAME.includes(prop)) {
targetStep = EditorStep.BASE;
}
if (TRANSFORMCONTROLLER_UPDATE_FUNCTION_NAME.includes(prop)) {
targetStep = EditorStep.TRANSFORMCONTROLLER;
}
if (receiver?.store?.step !== targetStep) {
receiver?.store?.setStep(targetStep);
}
return result;
};
}
return originalMethod;
},
});
},
};

设计模式:Invoker

Invoker

结构

globalStore中存了controllerinvoker,其中,controllerinvoker的控制权

1
2
3
graph TB
A[controller] --> B[invoker]
A --> C[renderer]

UI 存储变量用作offset,ThreeJsRenderer 存储变量记录实际数据
command内部更新 UI 的变量,并调用 controller 来调用 ThreeJsRenderer 的方法

流程图(以更新缩放为例)

1
2
3
4
graph LR
A[UI] --> B["invoker(globalStore)"]
B -->|Command| C[controller]
C --> D[ThreeJsRenderer]

ThreejsRenderer

提供函数实现模型的更新

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public moveModel(params: { x?: number; y?: number; z?: number }) {
const { x, y, z } = params
if (this.object) {
if (x !== undefined) this.object.position.x = x
if (y !== undefined) this.object.position.y = y
if (z !== undefined) this.offsetZ = z

this.object.updateMatrixWorld()
this.convexHull.matrix = this.object.matrix.clone()
if (this.baseModel) {
this.object.position.z -=
findMinZ(this.convexHull) - findMaxZ(this.baseConvexHubll) + this.offsetZ
this.object.updateMatrixWorld()
this.convexHull.matrix = this.object.matrix.clone()
this.positionLimits = findRangeBounds(
this.convexHull,
this.baseConvexHubll,
this.object.position.x,
this.object.position.y
)
this.store.setPositionLimits(this.positionLimits)
}
}
}

controller

在这里实现 UI 变量的更改以及模型的更改

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
public updateModelPosition = (params: { x?: number; y?: number; z?: number }) => {
const { positionLimits } = this.store
const newPosition: number[] = [...this.store.modelPosition]
const updatePosition = (value: number, index: number) => {
if (value < positionLimits[index * 2]) {
newPosition[index] = positionLimits[index * 2]
} else if (value > positionLimits[index * 2 + 1]) {
newPosition[index] = positionLimits[index * 2 + 1]
} else {
newPosition[index] = value
}
}

Object.entries(params).forEach(([key, value]) => {
if (value !== undefined) {
switch (key) {
case 'x':
updatePosition(value, 0)
break
case 'y':
updatePosition(value, 1)
break
case 'z':
updatePosition(value, 2)
break
}
}
})
this.store.setModelPosition(newPosition)
this.renderer.moveModel(params)
}

封装 command

不要在前端以参数的形式给Command传入前后状态,而是在Command中直接取得需要的参数。

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
import { ICommand, getController, getEditStore } from "./Command";

export class Move implements ICommand {
prePosition: { x?: number; y?: number; z?: number };
curPosition: { x?: number; y?: number; z?: number };
public constructor(params: { x?: number; y?: number; z?: number }) {
this.prePosition = params;

const modelPosition = getEditStore().modelPosition;
this.curPosition = {};

if (params.x !== undefined) {
this.curPosition.x = modelPosition[0];
}
if (params.y !== undefined) {
this.curPosition.y = modelPosition[1];
}
if (params.z !== undefined) {
this.curPosition.z = modelPosition[2];
}
}

execute(): void | Promise<void> {
const controller = getController();
if (controller) {
controller.updateModelPosition(this.curPosition);
}
}

undo(): void | Promise<void> {
const controller = getController();
if (controller) {
controller.updateModelPosition(this.prePosition);
}
}
}

invoker 执行 command

1
2
3
4
5
6
7
8
9
10
11
12
public async execute<CMD extends ICommand, T extends Array<any>>(
// @ts-ignore
type: { new (...T): CMD },
...args: T
) {
const cmd = new type(...args)
await cmd.execute()

this.undoStack.push(cmd)
this.redoStack = []
this.updateStack()
}

UI 触发

这里传入发送变化前一个瞬间的值,当下的值可以在发生变化后从全局存储文件中直接获取

1
invoker.execute(Move, { x: 1 });

完整代码

Controller.ts
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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
import { SCALE_MAX, SCALE_MIN } from "@src/core/EditorConstants";
import { useEditorStore } from "@src/stores/editorStore";
import { BASE_DEFAULT_COLOR } from "./EditorConstants";
import { EditorContext } from "./EditorContext";
import { Invoker } from "./Invoker";
import ThreeJsRenderer from "./ThreeJsRenderer";
type Props = {
context: EditorContext;
canvas: HTMLCanvasElement;
cubeCanvas: HTMLCanvasElement;
};

export class Controller {
public invoker: Invoker;
private renderer: ThreeJsRenderer;
private context: EditorContext;

public constructor({ context, canvas, cubeCanvas }: Props) {
this.invoker = new Invoker();
this.context = context;
this.renderer = new ThreeJsRenderer({
canvas,
context: this.context,
cubeCanvas,
});

if (this.context.modelUrl) {
this.renderer.updateModel(
this.context.modelUrl,
this.context.modelTextureUrl
);
} else {
console.error("Model url should not be empty!");
}
}

public dispose() {
this.renderer.dispose();
this.store.reset();
}

private get store() {
return useEditorStore.getState();
}

private get bodyColor() {
const { quantizedNum, quantizedInfos } = this.store;
if (!quantizedInfos || quantizedNum === undefined) {
return [];
}

const quantizedInfo = quantizedInfos.find(
(item) => item.colorNum === quantizedNum
);
return quantizedInfo?.bodyColor ?? [];
}

private get eyeColor() {
const { quantizedNum, quantizedInfos } = this.store;
if (!quantizedInfos || quantizedNum === undefined) {
return [];
}

const quantizedInfo = quantizedInfos.find(
(item) => item.colorNum === quantizedNum
);
return quantizedInfo?.eyeColor ?? [];
}

public getCurrentQuantization() {
if (!this.context.modelTextureUrl || !this.store.quantizedNum) {
return {
quantizedNum: 0,
bodyColor: [],
eyeColor: [],
textureUrl: this.context.modelTextureUrl ?? "",
};
}

return {
textureUrl:
this.context.quantizedModelTextureUrl ?? this.context.modelTextureUrl,
quantizedNum: this.store.quantizedNum,
bodyColor: this.bodyColor,
eyeColor: this.eyeColor,
};
}

public updateEyeResources(eyeModelUrls: string[][]) {
this.context.eyeModelUrls = eyeModelUrls;
}

public updateEyeModel(index: number) {
this.context.selectedEyeIndex = index;
if (index >= 0 && index < this.context.eyeModelUrls.length) {
this.renderer.updateEyeModel(
this.context.eyeModelUrls[this.context.selectedEyeIndex]
);
} else {
if (index !== -1) {
console.error("Invalid eye index!");
}
this.renderer.updateEyeModel([]);
}
}

public onCanvasResize() {
this.renderer.onCanvasResize();
}

public updateBaseModel(baseUrl: string) {
this.renderer.updateBaseModel(baseUrl);
}

public updateBaseColor(color: string) {
this.store.setBaseColor(color);
this.renderer.updateBaseColor(color);
}

public updateModelPosition = (params: {
x?: number;
y?: number;
z?: number;
}) => {
const { positionLimits } = this.store;
const newPosition: number[] = [...this.store.modelPosition];
const updatePosition = (value: number, index: number) => {
if (value < positionLimits[index * 2]) {
newPosition[index] = positionLimits[index * 2];
} else if (value > positionLimits[index * 2 + 1]) {
newPosition[index] = positionLimits[index * 2 + 1];
} else {
newPosition[index] = value;
}
};

Object.entries(params).forEach(([key, value]) => {
if (value !== undefined) {
switch (key) {
case "x":
updatePosition(value, 0);
break;
case "y":
updatePosition(value, 1);
break;
case "z":
updatePosition(value, 2);
break;
}
}
});
this.store.setModelPosition(newPosition);
this.renderer.moveModel(params);
};

public updateModelRotation = (params: {
x?: number;
y?: number;
z?: number;
}) => {
const newRotation: number[] = [...this.store.modelRotation];

const updateRotation = (value: number, index: number) => {
newRotation[index] = value;
};

Object.entries(params).forEach(([key, value]) => {
if (value !== undefined) {
switch (key) {
case "x":
updateRotation(value, 0);
break;
case "y":
updateRotation(value, 1);
break;
case "z":
updateRotation(value, 2);
break;
}
}
});

this.store.setModelRotation(newRotation);
this.renderer.rotateModel(params);
};

public updateModelScale = (params: {
x?: number;
y?: number;
z?: number;
}) => {
const newScale: number[] = [...this.store.relativelyScale];

const updateScale = (value: number, index: number) => {
if (value > SCALE_MAX) {
newScale[index] = SCALE_MAX;
} else if (value < SCALE_MIN) {
newScale[index] = SCALE_MIN;
} else {
newScale[index] = value;
}
};

Object.entries(params).forEach(([key, value]) => {
if (value !== undefined) {
switch (key) {
case "x":
updateScale(value, 0);
break;
case "y":
updateScale(value, 1);
break;
case "z":
updateScale(value, 2);
break;
}
}
});

this.store.setRelativelyScale(newScale);
this.renderer.scaleModel(params);
};

public resetModel = () => {
this.store.setModelPosition(
new Array(3).fill(parseFloat(this.store.subjectInits[0]))
);
this.store.setModelRotation(
new Array(3).fill(parseFloat(this.store.subjectInits[1]))
);
this.store.setRelativelyScale(
new Array(3).fill(parseFloat(this.store.subjectInits[2]))
);
this.store.setOverallScale(
new Array(1).fill(parseFloat(this.store.overallInits[0]))
);
this.store.setBaseColor(BASE_DEFAULT_COLOR);
this.renderer.resetModel();
};
public resetUndo = (
prePosition: number[],
preRotation: number[],
preScale: number[],
preScaleOverall: number[],
preBaseColor: string
) => {
this.store.setModelPosition(prePosition);
this.store.setModelRotation(preRotation);
this.store.setRelativelyScale(preScale);
this.store.setOverallScale(preScaleOverall);
this.store.setBaseColor(preBaseColor);
this.renderer.resetUndo(
prePosition,
preRotation,
preScale,
preScaleOverall,
preBaseColor
);
};
public lockedScale = (scale: number) => {
this.store.setOverallScale([scale]);
this.renderer.lockedScale(scale);
};
public lockedcaleModel = (scales: number[]) => {
this.store.setRelativelyScale(scales);
this.renderer.lockedScaleModel(scales);
};
public updateCameraAngle(azimuthal: number, polar: number) {
this.renderer.updateCameraAngle(azimuthal, polar);
}

public clearCameraCubeMesh() {
this.renderer.clearCameraCubeMesh();
}

public updatePokemonTexture(textureUrl: string) {
this.context.updateTextureUrl(textureUrl);
this.renderer.updatePokemonTexture(textureUrl);
}

public updateEyeColor(colorList: string[]) {
this.renderer.updateEyeColor(colorList);
}

public updatePaletteInfos({
originColorKey,
options,
}: {
originColorKey: string;
options?: Partial<FilamentInfo>;
}) {
this.store.updateFilamentInfo(originColorKey, { ...options });
this.updateTextureColor(this.store.filamentList);
}

public deletePalette({
colorKey,
newColorKey,
}: {
colorKey: string;
newColorKey: string;
}) {
this.store.updateFilamentInfo(colorKey, {
deleted: true,
sourceKey: newColorKey,
});
this.updateTextureColor();
}

private async updateTextureColor(filamentList = this.store.filamentList) {
const textureUrl = await this.context.updateTextureColor(filamentList);
if (textureUrl) {
this.renderer.updatePokemonTexture(textureUrl);
}
}

public updateQuantization({
bodyColor,
quantizedNum,
originFilamentColorList,
textureUrl,
}: {
bodyColor: string[];
quantizedNum: number;
originFilamentColorList?: FilamentInfo[];
textureUrl: string;
}) {
const { setFilamentColorList, setQuantizedNum } = this.store;
setFilamentColorList(
originFilamentColorList ??
bodyColor.map((v) => {
return {
key: v,
color: v,
};
})
);
setQuantizedNum(quantizedNum);
this.context.updateTextureUrl(textureUrl);
this.updateTextureColor();
}
}
Command.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import { useGlobalStore } from "@src/stores/globalStore";
import { Controller } from "../Controller";
import { useEditorStore } from "@src/stores/editorStore";
export interface ICommand {
execute(): void | Promise<void>;
undo(): void | Promise<void>;
}

export function getController(): Controller | undefined {
const { controller } = useGlobalStore.getState();
return controller;
}

export function getEditStore() {
return useEditorStore.getState();
}
Invoker.ts
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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
import { useEditorStore } from "@src/stores/editorStore";
import { ICommand } from "./commands/Command";

export class Invoker {
undoStack: ICommand[] = [];
redoStack: ICommand[] = [];

public constructor() {}

public async executeCmd(cmd: ICommand) {
await cmd.execute();
this.undoStack.push(cmd);
this.redoStack = [];
this.updateStack();
}

public async batchExecute<CMD extends ICommand, T extends Array<any>>(
// @ts-ignore
type: { new (...T): CMD },
selectedIndexes: number[],
...args: T
) {
const cmd = new type(selectedIndexes, ...args);
await cmd.execute();

this.undoStack.push(cmd);
this.redoStack = [];
this.updateStack();
}

public redo(): Promise<ICommand> | undefined {
if (this.redoStack.length === 0) {
return;
}

const toRedo = this.redoStack.pop() as ICommand;
const res = toRedo.execute();
const handleRes = () => {
this.undoStack.push(toRedo);
this.updateStack();
};

if (res instanceof Promise) {
return new Promise<ICommand>((resolve) => {
res.then(() => {
handleRes();
resolve({ ...toRedo });
});
});
} else {
handleRes();
return new Promise<ICommand>((resolve) => resolve({ ...toRedo }));
}
}

public undo(): Promise<ICommand> | undefined {
if (this.undoStack.length === 0) {
return;
}
const toUndo = this.undoStack.pop() as ICommand;
const res = toUndo?.undo();
const handleRes = () => {
this.redoStack.push(toUndo);
this.updateStack();
};
if (res instanceof Promise) {
return new Promise<ICommand>((resolve) => {
res.then(() => {
handleRes();
resolve({ ...toUndo });
});
});
} else {
handleRes();
return new Promise<ICommand>((resolve) => resolve({ ...toUndo }));
}
}

public updateStack() {
useEditorStore
.getState()
.updateStack(this.undoStack.length, this.redoStack.length);
const { setUndoDisabled, setRedoDisabled } = useEditorStore.getState();
setUndoDisabled(this.undoStack.length === 0);
setRedoDisabled(this.redoStack.length === 0);
}

public async execute<CMD extends ICommand, T extends Array<any>>(
// @ts-ignore
type: { new (...T): CMD },
...args: T
) {
const cmd = new type(...args);
await cmd.execute();
this.undoStack.push(cmd);
this.redoStack = [];
this.updateStack();
}

private async genericChangeCommand<COMMAND extends ICommand, T extends any[]>(
type: new (...constructorArgs: T) => COMMAND,
...constructorArgs: T
) {
const cmd = new type(...constructorArgs);
await cmd.execute();
this.undoStack.push(cmd);
this.redoStack = [];
this.updateStack();
}
}

搜索

BFS

概述

将当下遍历到的结点的子结点都入队列,只要队列不空,就不断令元素出队,由于先入队的先出队,此算法可以实现广度优先搜索

例题

1、迷宫最值

问题描述

n*m 的整型数地图,第一行和最后一行都是 0,从第一行任一点进入,出到第 n 行任一点,途中经过的最大数字为代价,求最小代价

代码逻辑

  • 利用BFS结合二分法求解

核心代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
bool bfs(int x, int y, int ans)
{
queue<pair<int,int>> q;
q.push(make_pair(x,y));
visited[x][y] = true;
while(!q.empty())
{
int xx = q.front().first, yy = q.front().second;
for(int i=0;i<4;i++) //上下左右位移
{
int nx = xx + dx[i], ny = yy + dy[i];
if(nx<1||nx>n||ny<1||ny>m||visited[nx][ny]||mp[nx][ny]>ans)
continue;
if(nx==n)
return true;
visited[nx][ny] = true;
q.push(make_pair(nx,ny));
}
}
return false;
}

DFS

概述

  • 利用递归的特性实现深度优先算法

例题

1、淹没海岛

问题描述

N*N 的地图,’.’表示海洋,’#’表示陆地,数据保证第一行、第一列、最后一行、最后一列为海洋,联通的陆地视作同一个海岛,只有上下左右都是陆地的陆地才不被淹没,求被淹没的海岛数量

代码逻辑
  • 分别求出淹没前后的海岛数量,做减法就是答案
  • 一个地图存储初始数据,还有一个地图存储实行淹没后的数据,被淹没的陆地用另一个符号*来表示,dfs 实现淹没操作的时候就是把非.处修改为. 所以初始化淹没地图的时候不能把陆地直接改为.
  • 计算海岛数时,有一块陆地就把答案增 1 且 dfs 把与它相连的陆地都变成海洋
核心代码_计算海岛数量
1
2
3
4
5
6
7
8
9
10
11
for(int i=2;i<n;i++)
{
for(int j=2;j<n;j++)
{
if(mp[i][j]=='#')
{
ans++;
dfs(i,j).
}
}
}
核心代码_深搜
1
2
3
4
5
6
7
8
9
10
void dfs(int x, int y)
{
mp[x][y] = '.';
for(int i=0;i<4;i++)
{
int nx = x + dx[i], ny = y + dy[i];
if(nx>1 && nx<n && ny>1 && ny<n && mp[nx][ny]!='.')
dfs(nx,ny);
}
}

2、树上求和

问题描述

有 n 个结点 n-1 条边构成树,每个结点存一个整数(有正有负) 求最大和

代码逻辑
  • 对每一个结点都当作根结点应用 dfs 求得子树和的最大值,在所有结点的最大值中取最大的,由于要让每一个结点都作为根结点且走完整子树,所以这是 dfs 问题不是 bfs 问题
  • 利用 fath 参数防止走入父结点,dp 数组初始化为各结点存储的值
核心代码
1
2
3
4
5
6
7
8
9
10
11
void dfs(int cur,int fath)
{
dp[cur] = data[cur];
for(int ver : edge[cur])
{
if(ver==fath)
continue;
dfs(ver,cur);
dp[cur] += dp[ver] > 0 ? dp[ver] : 0;
}
}

记忆化搜索

概述

将过程答案记下,以此达到减枝的效果

特点

  • 往往是求约束条件下的方案数

代码模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int dfs(condition 1,condition 2,...)
{
if(dp[condition1][condition2]....!=初始化的值)
return dp[condition1][condition2]....
if(递归终点) //根据限制条件求递归终点
返回
int ans = 0;
else
{
for(可走到的子结点) //超出限制条件的子结点忽略掉
ans += dfs(子结点)
}
return dp[condition1][condition2]....=ans;
}

例题

1、牛走草地

问题描述

N*M 的地图,#代表树,不可走,*代表草,可以走,走一次花费 1 时间,求从 x1,y1 走到 x2,y2 花费时间小于等于 t 的方案数

代码逻辑
  • dfs 中三个参数表示当下坐标和来到此处已经花费的时间
  • 限制条件是时间,时间达到了 T 必然不用接着尝试走下去了,如果到了终点,也可以走出终点再走回去,所以递归终点条件和有无到达终点无关
  • 只有不超出地图边界的子结点需要被考虑
核心代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int dfs(int x,int y,int time)
{
if(dp[x][y][time]!=-1)
return dp[x][y][time];
if(time==T)
{
if(x==x_end&&y==y_end)
return ans[x][y][time]=1;
else
return ans[x][y][time]=0;
}

int result=0;
for(int i=0;i<4;i++)
{
int nx=x+dx[i];
int ny=y+dy[i];
if(nx<1||nx>N||ny<1||ny>M||mp[nx][ny]=='#')
continue;
result += dfs(nx,ny,time+1);
}
return dp[x][y][time]=result;
}

2、地宫取宝

问题描述

n*m 的地图从左上入,右下出,只能向右或者向下走。如果一件宝物大于手上宝物最大价值,那就选择拿它,当然也可以不拿,求抵达终点时手上恰好 k 件宝物的方案数

代码逻辑
  • dfs 四个参数表示当下坐标和手上已有宝物的最大价值和手上已有宝物的数量
  • 限制条件是宝物数量和终点限制,由于只能向右或向下,无法走回头路,所以到了终点必须停下,但是如果已经拿了 k 个物品,后面可以一路都不拿,所以物品限制不作为递归终点的判据
  • 只有不超出地图终点的子结点需要考虑,如果选择拿当下物品,到子结点时已经拿过的物品达到 num+1,只有 num+1<=k 的子结点需要考虑
核心代码
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
int dfs(int x, int y, int maxV, int num)
{

if(dp[x][y][maxV][num] != -1)
return dp[x][y][maxV][num];
if(x==n&&y==m)
{
if(num==k || num==(k-1) && maxV<Map[x][y] )
return dp[x][y][maxV][num]=1;
else
return dp[x][y][maxV][num]=0;
}

int ans=0;
if(x+1<=n)
ans += dfs(x+1,y,maxV,num);
if(y+1<=m)
ans += dfs(x,y+1,maxV,num);

if(Map[x][y]>maxV && x+1<=n && num<k)
ans += dfs(x+1,y,Map[x][y],num+1);
if(Map[x][y]>maxV && y+1<=m && num<k)
ans += dfs(x,y+1,Map[x][y],num+1);

return dp[x][y][maxV][num] = ans ;
}

动态规划(资源优化版)

特点

  • 有限的资源组合出尽可能大的答案,答案关于资源数单调不减,这里的单调不减指的是资源越多答案只可能越优,不可能变差

线性 dp(基础版)

特点

  • 只在一个维度资源有限,另外的维度视作无限资源

解决方法

  • 资源从小到大递推
  • 求出转移方程

例题

1、牛吃草问题

问题描述

有 n 块草地坐标范围 Li-Ri,每块草地有 Ri-Li+1 份草,不能选择有重叠区域的草地,最多能吃多少草?

代码逻辑
  • 有限的资源(n 块草地)吃到尽可能多的草,草地变多,答案单调不减
  • 只要有草就能吃,容量无限
  • 吃草的终点坐标从小到大递推,那么资源也就从小到大递推
  • dp[i]>dp[j]当且仅当 dp[i]中选择了右端点处于 j+1 到 i 的草地
  • 状态转移时,尽可能从近的状态转移(因为答案关于资源单调不减)
  • 选 i 为终点的草地,转移方程见 for 循环, 不选 i 为终点的草地,转移方程 dp[i]=dp[i-1],两者选择一个答案最优的
核心代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<int> right_left[maxn];
//对于每一个右端点,存下它的所有左端点,right的下标表示右端点,对应的容器中的值表示与此右端点对应的左端点
for(int i=1;i<=right_max;i++) //right_max为数据中最大的右端点
{
dp[i] = dp[i-1]; //不选以i为终点的草地

for(int ver : right_left[i])
{
if(dp[ver-1] + i - ver + 1 > dp[i] )
dp[i] = dp[ver-1] + i - ver + 1;
//如果dp[i]从下标ver到i-1的dp值转移而来,这个dp值要么等于dp[ver-1],要么这个dp值对应的状态和当下冲突
}
}
cout<<dp[right_max];

2、物品摆放问题

问题描述

有 n 个位置可以摆放物品,物品无限,但要求两者之间至少有 k 个空位,什么物品都不摆放也算一种方案,一共有多少种摆放方案?

代码逻辑
  • 有限的资源(n 个位置)求尽可能多的摆放方案,位置变多,答案单调不减
  • 只要有合法位置就能摆物品,物品无限
  • 摆放物品的终点从小到大递推,那么资源也就从小到大递推
  • 第 n 个位置要么摆放物品要么不摆放物品,两种对应的情况数相加得到答案
核心代码
1
2
3
4
5
6
7
8
9
dp[0] = 1; //只考虑0个位置,即什么都不放
for(int i=1;i<=n;i++)
{
dp[i] = dp[i-1]; //第i个位置不摆放物品
//加上第i个位置摆放物品的方案
dp[i] += i-k+1>0 ? dp[i-k+1] : 1;
//i-k+1<=0时,只有前面什么物品都不放才能在i这里放物品,只加一种情况
//i-k+1>0时,从i-k+2到i-1必然都没有物品且第i位有物品,后面定了,所以前面有多少种方案就加多少种方案
}

滚动数组

特点

  • 有限的资源和有限的容量组合出尽可能大的结果,相同的资源条件下,结果随容量单调不减,但各结果无递归关系,当下结果只与前一个资源条件下的结果有关

例题

1、奇怪的数列

问题描述

n 个数字构成和为 s 的数列,其中 ai只能加 a 或者减 b 到 ai+1,求满足条件的数列有多少个

代码逻辑
  • 把+a 和-b 都视作+P
  • 求和时,a0-an-1的+P 的权重为 0 到 n-1,$$\sum_{i=0}^{n-1}$$ai = na0+$$\frac{n(n-1)P}{2}$$,$$\frac{n(n-1)}{2}$$里面有 i 次是+a 时,权重分配方案为 dpi,各种分配方案求出来的 a0是定值,如果是整数,那么答案加 dpi,否则,答案加 0
  • 有限的资源(n 个数列元素),有限的容量(分配给+a 的权重至多为$$\frac{n(n-1)}{2}$$,这里 n 表示当下资源规模)外循环表示资源从小到大
  • dpij=dp(i-1)j+dp(i-1)(j-i),把第一层维度放到外循环上
核心代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
dp[0]=1; //规模为1时,无权重可分,只有dp[0]为1,其他为0
for(int i=1;i<n;i++) //问题规模为1+i,终点为下标为i的数列元素
{
//滚动数组先默认继承了上一个状态的值,相当于i号元素权重不给+a的方案数
//然后再加上i号元素的权重赋给+a的方案数
for(int j=(i+1)*i/2;j>=i;j--)
dp[j] += dp[j-i]; //如果j本身小于i,那么i号元素权重赋给+a的方案数为0,也就是dp[j]+=0
}
for(int i=0;i<=n*(n-1)/2;i++)
{
int a0 = s + b * ( n*(n-1)/2 - i ) - a * i ;
if (a0%n==0)
ans += dp[i];
}

2、背包问题(基础版)

问题描述

有一个容量 V 的背包,有 n 个物品体积分别为 vi,求出背包用掉的最大容量

代码逻辑
  • 有限资源(n 个物品),有限容量(V)要求组合出尽可能大的体积
  • dpij=dp(i-1)j+dp(i-1)(j-v)+v 可以把第一维度体现在外循环上
  • 状态转移时,用尽可能贴近的 dp 值做转移,因为答案单调不减
核心代码
1
2
3
4
5
6
7
8
9
10
11
for(int i=1;i<=n;i++)  //考虑前i件物品
{
//默认第i件物品不放入
for(int j=V;j>=V-v[i];j--)
{
//如果第i件物品可以放入,且放入结果更大,就放入
if( dp[j] < dp[ j - v[i] ] + v[i] )
dp[j] = dp[ j - v[i] ] + v[i];
}
}

3、多重背包

问题描述

背包有 V 容量,n 种商品分别有价值量 wi,体积 vi和数量 si,求出背包可以装下的最大价值

代码逻辑
  • 有限的资源(n 种商品),有限的容量(背包容量 V)求出尽可能大的价值量
  • dpij=dp(i-1)j+dp(i-1)(j-v)+w 可以把第一维度体现在外循环上
  • 外循环表示物品种类一件件增加,问题规模从小到大
  • 每考虑一种商品需要考虑 si次状态转移,把 si二进制分解,减少计算次数
核心代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
for(int i=1;i<=n;i++)
{
cin>>w>>v>>s;
for(int j=1;j<=s;s-=j,j+=j) // 每次循环代表的物品体积j*v,价值j*w
{
//默认这件物品不放入
for(int k=V;k>=j*v;k--)
{
//如果这件物品可以放入,且放入结果更大,就放入
if(dp[k] < dp[k-j*v] + j * w)
dp[k] = dp[k-j*v] + j * w;
}
}
if(s>0) //s未被分尽
{
for(int k=V;k>=s*v;k--)
{
if(dp[k] < dp[k-s*v] + s * w)
dp[k] = dp[k-s*v] + s * w;
}
}
}

背包问题拓展

例题

1、完全背包

问题描述

背包容量 V,n 种商品具有价值量 wi和体积 vi,每种商品都可以无限次购买,求背包装下的最大价值

代码逻辑
  • 有限的资源(n 种商品),有限的容量(背包容量 V),组成尽可能大的价值
  • dpij=dp(i-1)j(j<vi),dpij=max(dpij , dpi(j-vi)+wi) 先用外循环继承上一个状态的结果,再用内循环从前向后递推
核心代码
1
2
3
4
5
6
7
for(int i=1;i<=n;i++)
{
for(int j=v[i];j<=V;j++)
{
dp[j] = max(dp[j],dp[ j - v[i] ] + w[i])
}
}

二维 dp

特点

状态转移时,必须考虑两个维度

例题

1、砝码称重

题目描述

N 个砝码分别重 Wi,求出最多可以称量多少种重量

代码逻辑
  • 如果只用一维数组,那么 dpi能表示的信息只有前 i 个砝码可以称出多少种重量,但是考虑状态转移的时候发现,由于不知道到底具体哪些重量可以被称出来,所以无法排重。比如 dpi=3 时,如果四个砝码可以称出重量 10,无法确定 dp4应该比 dp3大还是和 dp3一样大
  • 用二维数组 dpij表示前 i 个砝码是否可以称出重量 j
核心代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
for(int i=1;i<=n;i++) //资源从小到大遍历
{
for(int j=sumW;j>=1;j--)
{
if(dp[i-1][j]) //继承
dp[i][j] = true;
else if(j==w[i]) //只用i这个砝码
dp[i][j] = true;
else if(dp][i-1][ j + w[i] ]) //第i个砝码和物品在天平同一边
dp[i][j] = true;
//第i个砝码与物品分别在天平的两边
else if(j<w[i] && dp[i-1][ w[i] - j ])
dp[i][j] = true;
else if(j>w[i] && dp[i-1][ j - w[i] ])
dp[i][j] = true;
}
}

状态压缩 dp

特点

总状态数不多,可以用二进制表示

例题

1、买糖果

问题描述

商店有 n 包糖,每包糖里面有 k 种口味,一共有 m(<=20)种口味,每包糖里面的口味用数字 1 到 20 表示,最少买几包糖可以吃遍所有口味

代码逻辑
  • 用二进制对口味编码,口味的数字为 i,那么二进制第 i-1 位就为 1,编码出来的一个二进制数就代表一种口味组合
  • 资源从小遍历到大,如果某种口味组合可以被买到,那么它再加上当下的这包糖果的组合也可以被买到
核心代码_预处理
1
2
3
4
5
6
7
8
9
10
11
12
//求出每包糖果的口味组合
for(int i=1;i<=n;i++)
{
for(int j=1;j<=k;j++)
{
cin>>taste;
pac[i] |= ( 1<< (taste-1) );
}
}
max_taste = ( 1<<m ) - 1; //从第0位到第m-1位都是1
memset(dp,inf,sizeof(dp)); //初始化所有口味组合都无法买到
dp[0] = 0; //口味组合:什么口味都不要,这种情况买0包就可以了
核心代码_状态转移
1
2
3
4
5
6
7
8
9
10
11
12
for(int i=1;i<=n;i++)
{
for(int j=0;j<=max_taste;j++)
{
if(dp[j]<inf) //可以买到口味组合j
{
//买到了口味组合j的基础上,买下当下这包糖果,可以让口味组合j|pac[i]所需的糖果更少,那么就更新答案
dp[ j | pac[i] ] = min( dp[ j | pac[i] ], dp[j] + 1 );
}
}
}

图论

二叉树

例题

1、已知中、后序遍历求先序

代码逻辑
  • 后序遍历的最后一个字符一定是当下二叉树的根结点,先序遍历中根节点首先被遍历,所以每找到一个根节点就输出。在中序遍历中,根结点前面的是左子树,后面的是右子树,根据后序遍历的最后一个字符可以确定根,从而根据中序遍历确定左子树,从而根据左子树的大小从后序遍历中取出左子树,然后递归求解子树,右子树同理用递归求解
核心代码
1
2
3
4
5
6
7
8
9
void forw(string s1, string s2)
{
if(!s1.size()) return ;
char root = s2[s2.size()-1];
int p = s1.find(root);
std::cout<<root;
forw(s1.substr(0,p),s2.substr(0,p));
forw(s1.substr(p+1,std::string::npos),s2.substr(p,s2.size()-p-1));
}

2、已知先、后序遍历,求中序

代码逻辑
  • 考虑一棵树只有一个根结点和一个结点,那么它子结点为左和子结点为右结点时,得出的先、后序遍历不变
  • 如果树有一棵子树满足上述条件,那么子树有 2 种中序遍历,整棵树也就有 2 种中序遍历,根据乘法原理,如果树上有 k 个结点只有一个子结点,那么整棵树有 2^k^种中序遍历
  • 如果一个结点只有一个子结点,那么先序遍历时,子结点一定在它的后一位,后序遍历时,子结点一定在它的前一位
核心代码
1
2
3
4
5
6
7
8
9
10
pow = 0
for(int i=0;i<=s1.length()-2;i++)
{
for(int j=1;j<=s2.length()-1;j++)
{
if( s1[i]==s2[j] && s1[i+1]==s2[j-1] )
pow++;
}
}
ans = (1<<pow)

树的直径

概述

边具有权重,如果以权重代表距离,那么整棵树距离最远的两个结点的距离就是树的直径

代码逻辑

  • 以任意结点(比如 1 结点)为起点,dfs 求出各结点到 1 结点的距离,找到距离 1 结点最远的 far 结点
  • 以 far 结点为起点,dfs 求结点到 far 结点的距离,找到最大距离,最大距离就是树的直径

核心代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void dfs( int cur, int fath)
{
if(dist[cur] > D)
{
D = dist[cur];
far = cur;
}
for( int ver : edge[cur])
{
if(ver==fat)
continue;
dist[ver] = dist[cur] + 1;
dfs(ver,cur);
}
}

例题

1、城市规划

问题描述

n 个城市有 n-1 条边,边权都视作 1,以 k 个城市组成核心城市,核心城市之间可以不经过普通城市相互联通,求其他城市到核心城市的最大距离的最小值

代码逻辑
  • 先求直径,dfs 找到以任意结点为起点,离它最远的结点 far,然后用 dfs 求离 far 最远的结点,第二份 dfs 相比前一份 dfs 多一行代码,每次递归求子结点 dfs 之前先令 fa[ver] = cur,留下回溯数组方便找直径中点
  • 直径中点作为核心城市的核心,其他所有结点都具有两个距离值,一个是自己到核心的距离,一个是自己联通的子结点距离核心最远的距离。为了让普通城市离核心城市群尽可能近,必须把自己到核心距离与子结点到核心最远距离的差值前 k-1 大的归为核心城市
核心代码_求直径留回溯
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void dfs( int cur, int fat)
{
if(dist[cur] > D)
{
D = dist[cur];
far = cur;
}
for (int ver : edge[cur])
{
if(ver==fat)
continue;
dist[ver] = dist[cur] + 1;
fa[ver] = cur;
dfs(ver,cur);
}
}
核心代码_回溯找直径中点
1
2
3
center = far;
for(int i=1;i<=( D + 1 )/2;i++)
center = fa[center];
核心代码_核心距离、最深距离
1
2
3
4
5
6
7
8
9
10
11
12
void dfs( int cur, int fat)
{
dist_max[cur] = dist[cur];
for( int ver : edge[cur])
{
if(ver==fat)
continue;
dist[ver] = dist[cur] + 1;
dfs(ver,cur);
dist_max[cur] = dist_max[ver] > dist_max[cur] ? dist_max[ver] : dist_max[cur];
}
}

最小生成树

Kruskal

例题

N 个结点的图有 M 条无向有权边,判断能否生成一棵树,如果能则求出最小权重和

代码逻辑

  • 将边从小到大遍历,如果边的两个结点不在同一个并查集中,就合并它们,合并的权重代价就是这条边的权重

核心代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int Kruskal()
{
for(int i=1;i<=m;i++)
{
int root1 = FindRoot(edge[i].u), root2 = FindRoot(edge[i].v);
if(root1==root2)
continue;
root[root1] = root[root2];
ans += edge[i].w;
cnt++;
if(cnt==n-1) //合并n-1次并查集可以得到n个结点的树
return ans;
}
return -1;
}

Prime

代码逻辑

  • 起始让 1 结点入树,每当有结点入树就更新和它相连且未入树的结点到树的距离,每次找距离树最近的结点收入树中,无法用边联通的结点的距离视作 inf
  • visited 判断结点是否已经入树

核心代码

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
bool prime()
{
for(int i=2;i<=n;i++)
dist[i] = inf;
for(edge ver : e[1])
dist[ver.to] = dist[ver.to] < ver.weight ? dist[ver.to] : ver.weight;
int now = 1, tot = 0;
while(++tot<n)
{
int min = inf;
visited[now] = true;

for(int i=1;i<=n;i++)
{
if(!visited[i] && min>dist[i])
{
min = dist[i];
now = i;
}
}
//树中结点还没到n个,但已经找不到可以连接的结点了
if(min==inf)
return false;
ans+=min;

for(edge ver : e[now])
{
if(!visited[ver.to] && dist[ver.to]>ver.weight)
dist[ver.to] = ver.weight;
}
}
return true;
}

树上结点最近祖先(LCA)

例题

问题描述

n 个结点的树,s 为根,查询任意两个结点的最近祖先

代码逻辑

  • 先将两结点提到同一深度,然后一起向上回溯,回溯数组存 2 的幂次祖先,fanow,i表示从 now 向前回溯 2^i^得到的祖先
  • 无论是提到同一高度还是一起回溯,都按照 2 的幂次为单位向前跳,可以降低时间开销
  • 一起回溯时,从大到小遍历所有 2 的幂次级别的祖先结点,若不相同就跳。如果最近公共祖先是 x 结点,再向上看,两个结点上面的全部祖先结点肯定都相同

核心代码_预处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void dfs(int now, int fath)
{
//求深度
depth[now] = depth[fath] + 1;
//求回溯数组
fa[now][0] = fath;
for(int i=1;i<= (int)( log(depth[now])/log(2) );i++)
fa[now][i] = fa[fa[now][i-1]][i-1];

for(int ver : edge[now])
{
if(ver!=fath)
dfs(ver,now);
}
return ;
}

核心代码_LCA 主程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int LCA(int a, int b)
{
if(depth[a]<depth[b])
Swap(a,b);

while(depth[a]>depth[b])
a = fa[a][log_2[depth[a]-depth[b]]-1];
if(a==b)
return a;

for(int i=log_2[depth[a]]-1;i>=0;i--)
{
if(fa[a][i]!=fa[b][i])
a = fa[a][i], b = fa[b][i];
}
return fa[a][0];
}

单源最短路径(Dijkstra)

概述

  • Dijkstra只能处理无负权图的单源最短路径问题

例题

1、有向有权图单源最短距离

问题描述

n 个结点 m 条边,以 s 为源点,求其它所有结点到它的最短距离

代码逻辑
  • 辅助数据结构:优先队列 元素属性:队列中元素具有标号和距源点距离两个属性 排序方式:距离源点小的排前
  • 先让源点入队,每次循环从队列中弹出元素,更新它子结点到源点的距离,将被修改的子结点入队
  • 代码是广度优先搜索的逻辑,所以可能会出现同一个结点被修改多次,所以它会多次入队,由于是优先队列,只有第一次出队表示的才是它离源点的最短距离,所以用 visited 数组记录结点是否出过队
核心代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void Dijkstra()
{
q.push( (node) {s,0} );
while(!q.empty())
{
int ind = q.top().ind;
q.pop();
if(visited[ind])
continue;
for( edge ver : e[ind] )
{
if( dist[ver.to] > dist[ind] + ver.w ) //满足if条件的必然没有出过队
{
dist[ver.to] = dist[ind] + ver.w;
q.push( (node) { ver.to,dist[ver.to] } );
}
}
}
}

2、无向无权图单源最短路

问题描述

n 个结点 m 条边的无向无权图(边权都视作 1)以 1 为源点,求抵达任意点的最短路径的条数

代码逻辑
  • 先初始化 dist1为 0,其它 dist 都为 inf,ans1为 1,其它 ans 为 0
  • 利用优先队列,使到源点距离小的排前,但优先队列默认小的排后,所以传值时,传入距离的相反数
  • 处理当下结点的子结点时,如果子结点 dist 大于当下结点 dist 再+1,那么说明从当下结点去到子结点才是去它的最短路径,赋值式更新子结的 ans,但如果子结点的 dist 原本就和当下结点的 dist 再+1 相等,由于每个结点只会 visit 一次,所以子结点的 dist 被另外一个父结点更新为了当下结点的 dist 再+1,由排列组合加法原理知子结点的 ans 应当加上当下结点的 ans
核心代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void Dijkstra()
{
std::priority_queue< std::pair<int,int> > q;
q.push( std::make_pair(0,1) );
while(q.size())
{
int pos = q.top().second;
q.pop();
if(visited[pos])
continue;
visited[pos] = true;
for(int ver : edge[pos])
{
if(dist[ver] > dist[pos] + 1)
{
dist[ver] = dist[pos] + 1;
ans[ver] = ans[pos];
q.push( std::make_pair(-dist[ver],ver) );
}
else if(dist[ver] == dist[pos] + 1)
ans[ver] = ( ans[ver] + ans[pos] ) % mod;
}
}
}

图上最小环

例题

1、生日

题目描述

现在有 n 个人,起始时每个人只知道自己的生日,每个人都有一个信息传递对象,这个传递对象可以是自己,每一轮都会把自己知道的所有生日告诉传递对象,最少多少轮的时候会有人从别人口中听到自己的生日?

代码逻辑
  • 这是一个找最小环的问题,因为每个人只有一个信息传递对象,所以环都是独立的
  • 初始化每个人的传递对象为自己,每输入一个传递对象就判断能否构成环,可以的话就更新答案,不行的话说明更新传递对象
  • FindEnd 找到直线传递路径的终点,如果成环了,那么成环的结点的 nxt 不会被更新,所以它会导致 FindEnd 返回,也就是说,成环的结点就是直线传递路径的终点
核心代码_寻找直线传递路径终点
1
2
3
4
5
6
7
int FindEnd(int x)
{
cnt++; //全局变量
if(x==nxt[x])
return x;
return FindEnd(nxt[x]);
}
核心代码_寻找最小环
1
2
3
4
5
6
7
8
9
10
11
12
13
for(int i=1;i<=n;i++)
nxt[i] = i;
ans = inf;
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
cnt = 0; //全局变量
if(FindEnd(x)==i)
ans = min(ans,cnt);
else
nxt[i] = x;
}

拓扑结构

概述

拓扑结构关注结点之间的依赖关系

例题

1、工序时间

问题描述

有 n 项事件待做,输入 n 行,表示事件的标号和花费时间和需要的准备工作的标号,工人无限,可以无限制并行完成任务,输出完成所有事件的最小时间

代码逻辑
  • 利用入度数组 in 存下事件的前驱结点个数,如果入度为 0 了,就说明这件事情可以开始做了
  • ans 数组存完成各事件的最小时间,最终的答案为数组的最大值
  • 入度为 0 的事件入队列,每次把出队列的对象的子结点的入度减 1,且更新它的 ans,同一个事件有多个前驱结点,ans 会被更新多次,必须取最大值,如果子结点的入度被减为 1,那么它入队列
核心代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
for(int i=1;i<=n;i++)
{
if(in[i])
{
q.push(i);
ans[i] = t[i];
}
}
while(!q.empty())
{
int temp = q.top();
q.pop();
for(int ver : edge[temp])
{
ans[ver] = max( ans[ver], ans[temp] + t[ver] );
in[ver]--;
if(in[ver]==0)
q.push(ver);
}
}

2、火车站分级

问题描述

有 n 个站点(编号 1 到 n)的火车站,每个站点都有一个级别,火车站内走过了 m 躺火车,这些火车都遵循一个原则:如果在某一个站停了车,那么后面凡是级别大于等于这个站的站点都要停车,现在已知 m 躺火车停过的站,求火车站的站点至少有几种级别

代码逻辑
  • 这是一个用拓扑排序分层次的问题
  • 火车停过的站之间没有停下的站的级别必然小于停过的站的级别,用 greateri,j表示 i 号站点级别是否大于 j 号站点,用 out 数组记录出度,outi存的是比 i 号站点级别小的站点的个数
  • 每一层级可能有多个站点,但是答案只关注层级的个数,每次循环消去一个层级,把答案加 1
核心代码
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
int cnt,ans=-1;
do
{
ans++;
//删除最低层的站点,记下被删的站点
cnt = 0;
for(int i=1;i<=n;i++)
{
if(out[i]==0 && !deleted[i])
{
lowest[++cnt] = i;
deleted[i] = true;
}
}
//更新比被删除站点要高级的站点的出度
for(int i=1;i<=cnt;i++)
{
for(int j=1;j<=n;j++)
{
if(greater[j][lowest[i]])
{
greater[j][lowest[i]] = false;
out[j]--;
}
}
}
}while(cnt); //有执行删除操作才把答案加1,第一次进去的加1是多余的,所以ans初始化为-1

动态规划(子问题最优解递推)

特点

  • 问题可以划分为若干个子问题,从最小的子问题开始向上递推,最终解决总问题

例题

1、树形 dp(基础版)

题目描述

n 个结点的无权无向图,结点存权重,有 n-1 条边,边相连结点不能同时选择,求最大权重和

代码逻辑

  • 边数比结点数少 1,构成树,无向图可以用任意结点作根结点
  • 当下结点是否被选择这一信息必须保留,这是一个二维 dp 问题
  • dpi0表示以 i 为根且 i 不选的最优结果,dpi1表示以 i 为根且 i 选的最优结果,树划分为若干个子树
  • 对每一个结点取它的最优解用来更新它父节点的结果,最终得到根结点的最优结果

核心代码

1
2
3
4
5
6
7
8
9
10
11
void dfs(int cur,int fath)
{
for(int ver : edge[cur])
{
if(ver==fath)
continue;
dfs(ver,cur); //从子问题得到总问题的解,先要解出子问题
dp[cur][0] += max(dp[ver][0],dp[ver][1]);
dp[cur][1] += dp[ver][0];
}
}

2、树形 dp(拓展版)

题目描述

n 个结点的无权有向图,结点存代价,边相连结点可以互相监视,求全部结点都被监视的最小代价

代码逻辑

  • 有向,所以要先找到总根,然后划分为子树,解决子问题再递推到总问题
  • 二维 dp 问题,以 i 为根的子问题:如果 i 被选择,那么子结点选不选都可以让这棵树全部结点都被监视,如果 i 不被选择且要求这棵树不借助外来监视就可以被完全监视,那么子结点至少选一个,如果 i 不被选择且必须借助外来监视,那么子结点可以不选
  • 0 表示选择根结点,1 表示不选择根节点但是整棵树被监视,2 表示不选择根结点,除了根节点之外整棵树被监视
  • 根结点不选而且整棵树必须不借助外来监视就被完全监视,子树只能是 0 或者 1 状态,取最小值加到当下树即可,但是子树至少有一个是 0 状态,才能保证当下树是 0 状态,为了去掉子树的最小值都在 1 状态取的情况,求出每一个子树从最小值对应的状态到 0 状态的最小偏移量,当下树的结果加上这个偏移量
  • 最后的答案从 dproot,0和 dproot,1中取一个最小值,不能取 dp~root,2

核心代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void dfs(int cur)
{
for(int ver : edge[cur])
{
dfs(ver); //从子问题得到总问题的解,先要解出子问题
//cur被选,子结点任意
dp[cur][0] += min(dp[ver][0],dp[ver][1],dp[ver][2]);
//cur不选但整棵树被监视,子结点不允许借助外来监视
dp[cur][1] += min(dp[ver][0],dp[ver][1]);
//对于状态1,对于每一个子结点都不要求必须选择,但是至少一个子结点需要被选择,下面排除一个子结点都不选的情况
dt = min(dt,dp[ver][0] - min(dp[ver][0],dp[ver][1]) );
//cur不选且必须借助外来监视,子结点不可选择,且子结点不可借助外来监视
dp[cur][2] += dp[ver][1];
}
//如果最小偏移量为0,那么说明已经至少选择了一个子结点,那么dp[cur][1]需要加的量也就是0
dp[cur][1] += dt;
}

3、区间 dp

问题描述

n 块石头重量分别是 wi,合并两堆石头的代价是两堆石头的总重量和,只能合并相邻两堆石堆,求所有石头被合并为一堆石头最小代价

代码逻辑

  • 由于只能合并相邻两堆石堆,把问题划分为区间最值,dpij表示 i 到 j 之间的石头被合成一堆的最小代价,i 到 j 之间的石头被分作两堆的方式很多,子问题划分的时候只有一件事是确定的,那就是子问题的石堆的长度小于总问题,比如 1-5 合并成 1 堆,可以先把 1-3 合并为 1 堆,4-5 合并成 1 堆,然后再把这两堆合并,也可以 1-2 合并,3-5 合并,然后这两堆合并,但是无论无何,总问题 1 堆长 5,子问题 1 堆的长度必然小于 5,根据堆的长度做递推。长度确定后,遍历起点 i,终点 j 就固定为 i+len-1,此时考虑 dpij,它可以由很多种不同的方式转移过来,选一个结果最优的即可。

核心代码_预处理

1
2
3
4
5
6
7
8
9
10
//dp预处理
memset(dp,inf,sizeof(dp))
for(int i=1;i<=n;i++)
dp[i][i] = 0;
//前缀和预处理
for(int i=1;i<=n;i++)
{
cin>>w[i];
pre[i] = pre[i-1] + w[i];
}

核心代码_递推

1
2
3
4
5
6
7
8
9
10
for(int len=2;len<=n;len++)
{
for(int i=1;i<=n-len+1;i++)
{
j = i + len - 1;
for(int k=i;k<j;k++) //遍历所有可能转移到当下结果的子结果,取最小的
dp[i][j] = min(dp[i][j],dp[i][k]+dp[k+1][j]+pre[j]-pre[i-1] );

}
}

数据结构

单调栈

特点

单调表示从起点开始单调,遇到破坏单调性的元素时,会去掉栈内的元素来保持单调。以单增栈为例,如果处理了原数组 1 到 n 号元素,那么栈内第一个元素必然是 1 到 n 之间最小的元素,第二个元素必然是 1 到 n 之间第二小的元素,但是无法保证栈的长度等于 n

例题

1、海报

问题描述

N 个矩形房子拍成一排,高度分别是 hi用海报盖住它们,海报所盖之处不能是天空,最少用几张海报?

代码逻辑
  • 先假设答案为 N,如果两个房子同高,且它们之间的房子都比它们高,那么答案就可以减 1
核心代码
1
2
3
4
5
6
7
8
9
10
11
cin>>N>>h;
s.push(h);
for(int i=2;i<=N;i++)
{
cin>>h;
while( !s.empty() && h < s.top() )
s.pop();
if( !s.empty() && s.top()==h )
ans--;
s.push(h);
}

单调队列

特点

单调表示从起点开始单调,遇到破坏单调性的元素时,会去掉队列内的元素来保持单调。以单增队列为例,如果处理了原数组 1 到 n 号元素,那么队列内第一个元素必然是 1 到 n 之间最小的元素,第二个元素必然是 1 到 n 之间第二小的元素,但是无法保证队列的长度等于 n

例题

1、k 区间最大极值差

题目描述

有 N 个数字,Fi表示区间[max(1,i-k),i]之间的最大值与最小值的差,求 Fi的最大值

代码逻辑
  • 维护一个单增队列和一个单减队列求极值差
  • 由于 1-2、1-3….1-k 的最大极值差必然是 1-k 的极值差,求出原数组 1-k 之间的极值差,以代表 i<=k 时的答案
  • i>k 时,每次将 k 区间右移一位,最左边的元素被移出,在队列中删去它
核心代码
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
#include<deque>
........
//先处理1-k区间的极值差
for(int i=1;i<=n;i++)
{
while( !dq1.empty() && data[i]<dq1.back() )
dq1.pop_back();
dq1.push_back(data[i]);
}
for(int i=1;i<=n;i++)
{
while( !dq2.empty() && data[i]>dq2.back() )
dq2.pop_back();
dq2.push_back(data[i]);
}
ans = dq2.front() - dq1.front();
//处理后面的k区间
for(int i=k+1;i<=n-k+1;i++)
{
while( !dq1.empty() && data[i]<dq1.back() )
dq1.pop_back();
dq1.push_back(data[i]);

while( !dq2.empty() && data[i]>dq2.back() )
dq2.pop_back();
dq2.push_bac(data[i]);
//处理被移出去的元素
if(dq1.front()==data[i-k])
dq1.pop_front();
if(dq2.front()==data[i-k])
dq2.pop_front();
ans = max(ans,dq2.front()-dq1.front());
}

Map

概述

  • c++的 map 库中提供了数据类型 map,实现键值对的映射

  • map 会自动按照 first 第一,second 其次的优先级来排序

例题

1、点赞日志

问题描述

有 N 条点赞记录,每条记录包含被点赞内容的编号 id 和点赞时间 ts,如果存在 T,使得[T,T+D)之间 id 被赞的次数大于 k,那么就输出 id

代码逻辑
  • 用键值对< id,vector<int> >记录数据即可
核心代码
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
map< string, vector<int> > mp;
for(int i=1;i<=N;i++)
{
cin>>id>>ts;
mp[id].push(ts);
}
for(auto ver : mp)
{
vector<int> temp = mp.second;
if(temp.size()<k)
continue;
sort(temp.begin(),temp.end());
//枚举点赞记录时间起点,如果可以找到大于等于k条满足条件的点赞记录,就输出id
for(int i=0;i<=temp.size()-k+1;i++)
{
int ans = 1;
for(int j=i+1;j<=i+k;j++)
{
if(temp[j]-temp[i]<D)
ans++;
}
if(ans>=k)
{
cout<<ver.first<<'\n';
break;
}
}
}

并查集

概述

将祖先结点相同的结点放入同一个集合

路径压缩算法

  • 如果每次找结点的祖先结点都一个个父节点向上回溯,就多做了很多次不必要的操作
  • 路径压缩算法每回溯一次都把结点的父结点赋值为父结点的父结点,这样下次调用的时候就不用再做已经做过的回溯

代码示例

1
2
3
4
int FindRoot(int index)
{
return root[index]==index ? index : ( root[index] = FindRoot(root[index]) );
}

例题

1、奶酪

问题描述

奶酪高度 h,有 n 个半径 r 的洞(坐标 xi,yi),上表面视作高度 h,下表面视作高度 0,是否存在一条路径贯穿上下表面

代码逻辑
  • 枚举与上下表面联通的洞,如果能找到一对洞分别与上表面和下表面联通且它们有公共祖先结点,那么输出”YES”,否则输出”NO”
核心代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
for(int i=1;i<=n;i++)
{
cin>>x>>y;
if(is_up())
up.push_back(x,y);
else if(is_down())
down.push_back(x,y);
all[i] = {x,y};
for(int j=1;j<i;j++)
{
if(connected())
{
root1 = FindRoot(i), root2 = FindRoot(j);
if(root1!=root2)
//直接修改祖先结点的祖先结点,表示两个并查集的合并
root[root1] = root[root2];
}
}
}

2、关押犯人

问题描述

两个监狱关押 N 个犯人,有 M 对仇恨值,仇恨对象在同一监狱就会爆发等同于仇恨值的冲突,合理放置犯人使最大的冲突值最小

代码逻辑
  • 仇恨值从大到小排列,优先规避大仇恨值,第一个无法规避的仇恨值就是实际爆发的冲突中的最大值,由于可能的更大值已经被规避,所以实际的最大冲突值就是最大冲突值的最小值
  • 规避仇恨的方法就是把仇恨的对象的所有敌人都放入同一个监狱,也就是同一个集合
核心代码
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
struct node
{
//表示仇恨对象和仇恨值
int x,y,c;
}data[maxn];
int enemy[maxn]; //表示犯人的第一个仇人
..................
sort(data,data+m,[](node n1,node n2){return n1.c > n2.c;});
for(int i=1;i<=m;i++)
{
if( FindRoot(data[i].x) == FindRoot(data[i].y) ) //找到第一对无法避免的冲突
{
cout<<data[i].c;
break;
}

if(enemy[data[i].x]==0) //输入第一个敌人
enemy[data[i].x] = data[i].y;
else //已经有第一个敌人
root[FindRoot(enemy[data[i].x])] = root[FindRoot(data[i].y)];

if(enemy[data[i].y]==0)
enemy[data[i].y] = data[i].x;
else
root[FindRoot(enemy[data[i].y])] = root[FindRoot(data[i].x)];
}

ST 表

概述

ST 表可以实现离线查询区间最值的功能

代码逻辑

  • ST 表把区间划分为长度为 2 的幂次的子区间,stij表示原数组从 i 到 i+$$2^j-1$$的最值
  • 求任意区间最值时,只需把区间划分为两个长度为 2 的幂次的子区间,查 st 表得最值
  • 任意区间划分原则:长度对半分,断点 k=$$log_2{(R-L+1)}$$

核心代码_生成 ST 表

1
2
3
4
5
for(int j=1;j<=maxj;j++)  //区间长度为2^j,区间长度大的st值由更小的区间得到
{
for(int i=n;i>=1;i--) //区间起点为i,起点小的st值需要依赖起点大的st值获得
st[i][j] = max( st[i][j-1], st[i+(1<<(j-1))][j-1] );
}

核心代码_任意区间查值

1
2
3
4
5
6
7
int query(int L,int R)
{
int k = log(R-L+1) / log(2);
//确保区间被划分为两个长为2^k的区间,所以后一个区间的左端点不是L+(1<<k)
//又为了确保后一个区间的左端点小于等于前一个区间的右端点,计算求得k的值log(R-L+1) / log(2)
return max(st[L][k],st[R-(1<<k)+1][k]);
}

树状数组

概述

  • 树状数组是对原数组更快速的管理方式,普通树状数组可用于单点修改和区间查询,如果引入差分数组就可以实现区间修改、单点查询、区间和查询,这里所有的修改和查询都指对原数组的操作。
  • 普通树状数组是管理原数组的工具
  • 差分树状数组是管理差分数组从而管理原数组的工具
  • 树状数组大小和原数组一样

前置知识

  • lowbit(x):x 二进制表示中最低位 1 代表的数字,lowbit(x) = x&(~x+1)

  • 差分数组:差分数组 data_diffi = datai-datai-1

代码逻辑

  • 树状数组中下标为 x 的节点的父节点为下标为 x+lowbit(x)的节点
  • 每一个节点存的数据是本身数据以及本身的子节点数据的和
  • 求原数组下标 1-x 的和是从树状数组下标为 x 的节点开始加,每次下标减去 lowbit(x)

核心代码_创建树状数组/单点修改

1
2
3
4
5
6
//创建树状数组的过程相当于做单点修改,原数组下标为i的值从0修改为输入的data[i]
void add(int index,int value)
{
for(int i=index;i<=n;i+=lowbit(i)) //回溯每一个父节点
data_tree[i] += value;
}

核心代码_区间和查询

1
2
3
4
5
6
7
8
9
10
11
int query(int L,int R)
{
int ans = 0;
for(int i=R;i>=1;i-=lowbit(i))
ans += data_tree[i];
if(L==1)
return ans;
for(int i=L-1;i>=1;i-=lowbit(i))
ans -= data_tree[i];
return ans;
}

核心代码_差分数组创建树状数组/单点修改

1
2
3
4
5
6
7
//创建树状数组的过程相当于做单点修改,原数组下标为i的值从0修改为输入的data[i]
for(int i=1;i<=n;i++)
{
cin>>data[i];
for(int j=i;j<=n;j+=lowbit(j))
data_tree[j] = data[i] - data[i-1];
}

核心代码_差分树状数组单点查询

1
2
3
4
5
6
7
8
//查询的是差分数组的1-index的和,也就是原数组的单点值
int query(int index)
{
int ans = 0;
for(int i=index;i>=1;i-=lowbit(i))
ans += data_tree[i];
return ans;
}

核心代码_差分树状数组区间修改

1
2
3
4
5
6
7
8
//原数组在区间改值,相当于差分数组在left处+k,在right+1处-k,反映到树状数组就是做两次单点修改
void change(int left,int right,int k)
{
for(int i=left;i<=n;i+=lowbit(i))
data_tree[i] += k;
for(int i=right+1;i<=n;i+=lowbit(i))
data_tree[i] = -k;
}

求和线段树

概述

求和线段树可完成区间修改(加法和乘法)和区间和查询的功能,需要的空间是原数组的 4 倍

代码逻辑

  • pos 表示树上结点,low-hight 表示 pos 结点树控制的原数组的位置
  • 利用 tag 数组延迟完成改值操作,减少修改操作的次数,tag 的值只有 pos 的子结点才会用到
  • x、y、k 是输入的参数,分别表示操作的区间[x,y]以及操作数 k
  • 每次调用 add 或者 mul 时,最终终止的地方,其父结点全都会被及时处理,其子结点会延迟处理,而每一次调用 add、mul、query 都是从 pos=1 开始的,所以 tree[1]的值总是正确的。如果一进 query 就返回了,那么输出的结果是 tree[pos],不然就会先 pushdown 把子结点的值修改正确再调用 query 查询子结点,因此查询值总是正确的。

核心代码_建树

1
2
3
4
5
6
7
8
9
10
11
12
void build(int pos, int low , int hight)  //递归建树
{
if(low == hight)
{
tree[pos] = data[low];
return ;
}
int mid = low + ( (hight - low) >> 1);
build(pos<<1, low, mid);
build( (pos<<1)+1, mid+1, hight);
tree[pos] = tree[pos<<1] + tree[(pos<<1)+1];
}

核心代码_向下传标记(tag)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void pushdown(int pos, int low, int hight)  //向下改值
{
int mid = low + ( ( hight - low) >> 1 );
//修改子结点的值,乘法优先
tree[pos<<1] = tree[pos<<1] * tag_mul[pos] + ( mid - low + 1 ) * tag_add[pos];
tree[(pos<<1)+1] = tree[(pos<<1)+1] * tag_mul[pos] + ( hight - mid ) * tag_add[pos];
//修改子结点的tag,乘法优先
tag_mul[pos<<1] = tag_mul[pos<<1] * tag_mul[pos];
tag_mul[(pos<<1)+1] = tag_mul[(pos<<1)+1] * tag_mul[pos];
tag_add[pos<<1] = tag_add[pos<<1] * tag_mul[pos] + tag_add[pos];
tag_add[(pos<<1)+1] = tag_add[(pos<<1)+1] * tag_mul[pos] + tag_add[pos];
//复原当下结点的tag
tag_mul[pos] = 1;
tag_add[pos] = 0;
}

核心代码_区间改值(加法)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void add(int pos, int low, int hight)
{
if(x<=low && y>=hight) //这个结点控制的区间已经被完全覆盖
{
//修改当下位置树的值并设置tag
tree[pos] = tree[pos] + ( hight - low + 1) * k;
tag_add[pos] = tag_add[pos] + k;
return ;
}
pushdown(pos, low, hight); //递归结束后做回溯的时候及时传递tag标记
int mid = low + ( ( hight - low ) >> 1 );
//如果左右子结点控制的区间有被影响到,那么就对它们调用add函数
if(x<=mid)
add(pos<<1, low, mid);
if(y>=mid+1)
add( (pos<<1)+1, mid+1, hight);
//改完左右结点后,给当下结点重新赋值
tree[pos] = tree[pos<<1] + tree[(pos<<1)+1];
}

核心代码_区间改值(乘法)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void mul(int pos, int low, int hight)
{
if(x<=low && y>=hight)
{
tree[pos] = tree[pos] * k;
tag_mul[pos] = tag_mul[pos] * k;
tag_add[pos] = tag_add[pos] * k; //注意:做乘法操作的时候会影响前面遗留的加法
return ;
}
pushdown(pos, low, hight);
int mid = low + ( ( hight - low ) >> 1 );
if(x<=mid)
mul( pos<<1, low, mid);
if(y>=mid+1)
mul( (pos<<1)+1, mid+1, hight);
tree[pos] = tree[pos<<1] + tree[(pos<<1)+1];
}

核心代码_区间和查询

1
2
3
4
5
6
7
8
9
10
11
12
int query(int pos, int low, int hight)
{
if(x<=low && y>=hight)
return tree[pos];
pushdown(pos,low,hight);
int ans = 0, mid = low + ( ( hight - low ) >> 1 );
if(x<=mid)
ans += query(pos<<1, low, mid);
if(y>=mid+1)
ans += query( (pos<<1)+1, mid+1, hight );
return ans;
}

字典树

概述

字典树对前缀进行复用,查找时可以省时间

代码逻辑

  • 二维数组存三个信息,第一维存起始结点,数据存终止结点,第二维存这两个结点之间的值

例题

1、字符串前缀

问题描述

有 n 个文本串和 m 个模式串,求出各匹配串在文本串的前缀中出现的次数

核心代码_插入字符串
1
2
3
4
5
6
7
8
9
10
void Insert(string s)
{
int x = 1; //从字典树起点开始
for(int i=0;i<s.length();i++)
{
if(!trie[x][s[i]-'a'])
trie[x][s[i]-'a'] = ind++; //字典树数组的栈顶指针
x = trie[x][s[i]-'a'];
}
}
核心代码_查询字符串
1
2
3
4
5
6
7
8
9
10
11
bool check(string s)
{
int x = 1;
for(int i=0;i<s.length();i++)
{
x = trie[x][s[i]-'a'];
if(x==0) //匹配到某个字符时,字典树中无对应的边,说明失配
break;
}
return x;
}

2、异或最大值

问题描述

有 n 个数字,可以任意两两组合做异或,求出可得的最大值

代码逻辑
  • 对每个数字,找到和它和其他数字异或的最大结果,再利用各自的最大值求得总最大值即可
  • 字典树寻找异或结果最大值:利用二进制编码构造 01 字典树,利用贪心思想,每一步都选择和自己对应数位相反的结点
  • 字典树建立:为了统一,所有 int 数都看成 31 位二进制,只忽略了符号位的 0
核心代码_建树
1
2
3
4
5
6
7
8
9
10
11
void Insert(int data)
{
int x = 1;
for(int j=30;j>=0;j--)
{
if(!trie[x][ (data>>j)&1 ])
trie[x][ (data>>j)&1 ] = ind++; //字典树数组的栈顶指针
x = trie[x][ (data>>j)&1 ]
}
val[x] = data; //十进制值与字典树终点建立映射关系,方便查询
}
核心代码_寻找异或最大值
1
2
3
4
5
6
7
8
9
10
11
12
13
int maxEXOR(int data)
{
int x = 1;
for(int j=30;j>=0;j--)
{
//优先选择和自己对应数位数字不同的路径
if(trie[x][ !( (data>>j)&1 ) ])
x = trie[x][ !( (data>>j)&1 ) ];
else
x = trie[x][ (data>>j)&1 ];
}
return data ^ val[x];
}

Manacher算法

概述

利用 O(N)的复杂度求出字符串的最大回文半径

前置知识与预处理

回文中心

对于长度为奇数的回文串而言,其具有回文中心,但如果回文串的长度为偶数,那么其无回文中心。
为了处理方便处理,先将字符串拓展成 2length+3 的长度,在首尾补上两个特殊字符当作终止符,编号 1 至 2length+1 之间奇数编号赋值#,偶数编号从小到大依次赋值为原字符串的字符

图例
A B C C C B A
^ # A # B # C # C # B # A # $

显然,处理后的字符串最大回文半径比原字符串大 1

代码逻辑

如果两个元素处于一个回文区间的对称位置,那么可以用前面的元素的最大回文半径给后面元素的最大回文半径赋值,但是赋值时不能让后面元素的最大回文区间右端点超出当下回文区间的右端点,因为可赋值的性质是在当下回文区间之中的性质,超出当下回文区间之后不具备此条由回文区间带来的性质。

利用最大回文半径的赋值,可以复用比较结果,以此优化时间复杂度

代码实现

从前向后遍历结点,只要当下结点还没有抵达或者超越当下回文区间边界,就可以尝试用其对称结点的最大回文半径赋值。
只要当下回文区间不能包含住结点的回文区间,那么当下的回文区间已经不可能再为当下结点已经后续结点提供回文半径赋值的性质,所以将当下回文区间转移为当下结点的回文区间。

1
2
3
4
5
6
7
8
9
10
11
12
int Center = 0, Right = 0;
for(int i=1;i<=2*lenth+1;i++)
{
if(i<Right) //由于0号为特殊元素不可能加入回文区间,回文左端点最左为1,i<Right时,2*Center-i必然大于0,数组不会越界
r[i] = r[2*Center-i] < Right-i ? r[2*Center-i] : Right-i;
else
r[i] = 1;
while(s[i+r[i]]==s[i-r[i]])
r[i]++;
if(i+r[i]>Right)
Center = i, Right = i + r[i];
}

模式匹配算法

KMP 算法

概述

在 s1 中寻找 s2,暴力算法在遇到字符不匹配的时候会令 s2 回溯到起点,s1 回溯到起点后面一格

A B C A B C D H
A B C E

这里发生失配,然后 j(s2 的元素指针)回溯到 0,i(s1 的元素指针)回溯到 1

A B C A B C D H
A B C E

显然这种回溯方式做了许多多余比较,KMP做法则是根据next数组做回溯

C B C A B C D H
C B C E

发生失配后,j 从 3 回溯到 1

C B C A B C D H
C B C E

前置知识

前后缀

字符串的前缀是从以第一个字符开始,任意元素结尾(除了字符串末尾元素外)组成的字符串的子字符串,字符串的后缀是以最后一个字符为结尾,任意字符(除了字符串起始元素外)开始的子字符串,相等的前缀和后缀的最大长度为最大相等前后缀长度,如果原字符串只有 1 个字符,最大相等前后缀长度视作 0

求 next 数组

从上面的表格可以看出,假如 s2 从 i 号跳转到 j 号,必须保证从 j 向前到开头的这一部分和从 i 向前相同长度的这一部分是完全相同的,也就是说 i 前面的一段字符串的最长相等前后缀的前缀的末尾的后面一位就是 j,由前缀的性质可知,j 同时也表示 i 之前的字符串的最大相等前后缀长度

1
2
3
4
5
6
7
8
9
10
11
12
13
int i = 0, j = -1;
next[0] = -1;
while(i<s2.length()-1)
{
if(j==-1 || s2[i]==s2[j]) //i之前最大相等前后缀长为0,那么j就会为-1
{
i++,j++; //相当于是对进入循环的i+1的回溯数组赋值,所以i只需要遍历到小于s2.length()-1
next[i] = j;
}
else
j = next[j];
//相当于是用j向前一直到起点的字符串来匹配i向前等长的字符串,匹配失败就回溯
}

Kmp 主程序

求出 next 数组之后只需要将 s2 与 s1 逐个字符匹配,如果失配,就让 s2 按照 next 数组回溯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//返回第一次匹配成功的起点
int i = 0,j = 0;
while(i<s1.length())
{
if( j==-1 || s1[i]==s2[j]) //s2中没有元素可以匹配到s1[i]那么j就会为-1
{
i++,j++;
if(j==s2.length())
break;
}
else
j = next[j];
}
if(j==s2.length())
return i - j ;
else
return -1;

瑕疵与优化

考虑 s1 == “aaaaaaaabaaaaac” s2 == “aaaaac”的情况,c 失配后回溯到 4 号 a,又失配,回溯到 3 号 a,然后回溯到 2 号 a…. 一直到 0 号 a 失配,回溯到-1,同一个字符失配过一次后就不需要再尝试匹配,在求 next 的过程中,加入判断语句,判断失配元素与其回溯元素是否相等,若相等,就将回溯元素的回溯元素传递给失配元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int i = 0, j = -1;
next[0] = -1;
while(i<s2.length()-1)
{
if(j==-1 || s2[i]==s2[j])
{
i++,j++;
if(s2[i]!=s2[j])
next[i] = j;
else
next[i] = next[j];
}
else
j = next[j];
}

AC 自动机

概述

字典树与 KMP 的结合,用于模式串过多,字典树运行时间过长的情况

代码逻辑

  • AC 自动机下标 0 为特意设定的头结点
  • 回溯数组的求法:让每个模式串的首字母回溯到 0,每一个结点 x 都回溯到与其存储相同字母的结点 bk,bk 父结点为 x 父结点的回溯结点,因为回溯的结点要么是 0 结点,要么是和自己存储相同字母的结点,所以从 bk 走到 0 的字符串必然和 x 走到 0 过程中经历相同长度的字符串的内容相同

核心代码_自动机结构体

1
2
3
4
5
6
struct node
{
int bk; //回溯结点
int cae; //以此结点为终点的单词个数
int letter[26]; //起始结点为当下结点,下标表示两结点之间对应的字母,值表示终止结点
}AC[maxn];

核心代码_建立字典树

1
2
3
4
5
6
7
8
9
10
11
void BuildTrie(const std::string& s)
{
int x=0;
for(int i=0;i<s.size();i++)
{
if(!AC[x].letter[s[i]-'a'])
AC[x].letter[s[i]-'a'] = ind++; //ind为字典树组栈顶指针
x=AC[x].letter[s[i]-'a'];
}
AC[x].cae++;
}

核心代码_求回溯数组

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
void GetBtk()
{
std::queue<int> q;
for(int i=0;i<26;i++)
{
if(AC[0].letter[i])
{
AC[AC[0].letter[i]].btk=0;
q.push(AC[0].letter[i]);
}
}
while(q.size())
{
int cur=q.front();
q.pop();
for(int i=0;i<26;i++)
{
if(AC[cur].letter[i])
{
AC[AC[cur].letter[i]].btk = AC[AC[cur].btk].letter[i];
q.push(AC[cur].letter[i]);
}
else //防止因为走的路径问题错过本来可以匹配的对象
AC[cur].letter[i] = AC[AC[cur].btk].letter[i];
}
}
}

核心代码_字符串匹配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int AC_Query()
{
int cur=0,ans=0;
for(int i=0;i<s.size();i++) //遍历文本串的每一个字母
{
cur = AC[cur].letter[s[i]-'a'];
for(int t=cur;t&&AC[t].cae!=-1;t=AC[t].btk) //回溯的时候到了0就终止,如果cae等于-1说明此路来过
{
ans += AC[t].cae;
AC[t].cae = -1;
}
}
return ans;
}

javaScript的this

默认绑定

普通函数直接调用则 this 绑定全局变量,严格模式下,this 绑定到 undefined

隐式绑定

函数作为对象的属性调用则会将 this 隐式绑定到这个对象

正常绑定

1
2
3
4
5
6
7
8
function foo() {
console.log(this.a);
}
var obj = {
a: 42,
foo: foo,
};
obj.foo(); // 42

引用导致 this 丢失

在上面的例子中,如果给函数一个别名var bar = obj.foo 这个时候它引用的是函数本身,如果这样调用bar()就相当于在全局的位置调用 foo 函数。

传参过程 this 丢失

1
2
3
4
function doFoo(fn) {
fn();
}
doFoo(foo);

即便是传入 js 内置函数也会发生 this 丢失,比如 setTimeout 等

组件传参防止 this 丢失

传入的函数

1
2
3
const lockedScale = (scale: number) => {
controller!.lockedScale(scale); //在这里确保了是让controller调用这个函数,不会丢失this
};

传入组件

1
<InputSlider draging={lockedScale} />

显示绑定

  • apply 为函数设置绑定的 this,然后调用它
  • bind 为函数设置绑定的 this,然后返回一个新的函数,但是不会调用它

React三大Hook

useState

state的设置是异步的,不能及时获取

如果需要确保随机的两次是完全不同的,需要用 ref

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const preInd = useRef<number>(-1);
const curInd = useRef<number>(0);
const handleRandom = () => {
const n = 11;
const randomTexts = Array.from({ length: n }, (_, index) =>
t(`prompt:prompt_text_random${index + 1}`)
);

curInd.current = Math.floor(Math.random() * n);
while (curInd.current === preInd.current) {
curInd.current = Math.floor(Math.random() * n);
}

textRef.current = randomTexts[curInd.current];
setTextState(randomTexts[curInd.current]);
};

useRef

ref 可以确保变量是最新值,不会重新渲染页面,如果需要获取最新值而且需要实时渲染,那么就要结合useState使用

综合应用

useState 注解

定义:const [textState, setTextState] = useState<string>('')
传入子组件的注解:

1
2
textState: string;
setTextState: React.Dispatch<React.SetStateAction<string>>;

useRef 注解

定义: const textRef = useRef<string>('')
传入子组件的注解:(MutableRefObj 表示这个 ref 是一个可以修改 current 的 ref)

1
textRef: MutableRefObject<string>;

实例

需求:用户输入的文本框实时更新,输入的内容要被用作输入词调用 SD
解决方案:用 state 渲染输入的内容,用 ref 传给 SD

useEffect

用空数组监听的时候常常监听不到,这是因为挂载和卸载的触发比较严苛,用逻辑表达式决定组件出现与否的时候会触发组件的挂载和卸载

组件挂载和卸载只发生在 DOM 结构中添加和删除组件的时候,Dialog 的 open 与否不会导致挂载和卸载。

state 变量改变,以及 zustand 变量改变的时候则会触发整个组件的所有代码重新执行,但是也不会导致挂载和卸载