1数据结构
21. 栈
3abstract class Stack<T> {
4 abstract push(value: T): void;
5 abstract pop(): T;
6}
71.1 单调栈
8暂时无法在飞书文档外展示此内容
92. 队列
102.1 单向队列
11 https://github.com/iqseternal/rapid/blob/pre-main-react/packages/libs/structure/Queue/Queue.ts
12abstract class Queue<T> {
13 abstract push(value: T): void;
14 abstract pop(): T;
15}
162.2 双端队列
17 https://github.com/iqseternal/rapid/blob/pre-main-react/packages/libs/structure/Queue/Dequeue.ts
18abstract class Dequeue<T> {
19 abstract push_back(value: T): void;
20 abstract pop_back(): T;
21
22 abstract push_front(value: T): void;
23 abstract pop_front(): T;
24}
252.3 单调队列（优先级队列
26暂时无法在飞书文档外展示此内容
27export interface Comparator<V> {
28 (v1: V, v2: V): number;
29}
30
31export abstract class Vessel<V> {
32 protected comparator: Comparator<V> = (v1, v2) => {
33 if (v1 === v2) return 0;
34 if (typeof v1 !== 'number' || typeof v1 !== 'string') return 1;
35 if (typeof v2 !== 'number' || typeof v2 !== 'string') return 1;
36 if (v1 > v2) return 1;
37 return -1;
38 };
39
40 public abstract [Symbol.iterator](): Iterator<V>;
41 public abstract size(): number;
42 public abstract isEmpty(): boolean;
43 public abstract clear(): void;
44 public abstract contains(value: V): boolean;
45 public setComparator(comparator: Comparator<V>): void { this.comparator = comparator; }
46}
47
48export class PriorityQueue<V> extends Vessel<V> {
49
50 private priorityQueueArr: [undefined, ...V[]] = [void 0];
51 private length: number = 0;
52
53 public override *[Symbol.iterator](): Iterator<V> {
54 while (this.length) {
55 const v = this.pop()!;
56 yield v;
57 }
58 }
59
60 public top(): V | null {
61 if (this.length === 0) return null;
62 return this.priorityQueueArr[1];
63 }
64
65 public push(...values: V[]): void {
66 values.forEach(value => {
67 this.priorityQueueArr[++ this.length] = value;
68 this.swim(this.length);
69 })
70 }
71
72 public pop(): V | null {
73 if (this.length === 0) return null;
74 const value = this.priorityQueueArr[1]!;
75 this.swap(1, this.length);
76 this.length --;
77 this.sink(1);
78 return value;
79 }
80
81 private swim(index: number) {
82 while (index > 1 && this.comparator(this.priorityQueueArr[index]!, this.priorityQueueArr[index >> 1]!) < 0) {
83 this.swap(index, index >> 1);
84
85 index = index >> 1;
86 }
87 }
88
89 private sink(index: number) {
90 if (index <= 0) return;
91
92 while (2 * index <= this.length) {
93 let k = index * 2;
94
95 if (k + 1 <= this.length && this.comparator(this.priorityQueueArr[k + 1]!, this.priorityQueueArr[k]!) < 0) {
96 k ++;
97 }
98
99 if (this.comparator(this.priorityQueueArr[index]!, this.priorityQueueArr[k]!) > 0) {
100 this.swap(index, k);
101 index = k;
102 continue;
103 }
104
105 break;
106 }
107 }
108
109 private swap(i: number, j: number) {
110 if (i <= 0 || i > this.length) return;
111 if (j <= 0 || j > this.length) return;
112 const t = this.priorityQueueArr[i];
113 this.priorityQueueArr[i] = this.priorityQueueArr[j];
114 this.priorityQueueArr[j] = t;
115 }
116
117 public override contains(value: V): boolean {
118 for (let i = 1;i <= this.length;i ++) {
119 const v = this.priorityQueueArr[i];
120 if (this.comparator(v!, value) === 0) return true;
121 }
122 return false;
123 }
124
125 public override clear() {
126 this.priorityQueueArr = [void 0];
127 this.length = 0;
128 }
129
130 public override isEmpty(): boolean {
131 return this.size() === 0;
132 }
133
134 public override size(): number {
135 return this.length;
136 }
137}
1383. 数组（向量。
139abstract class Vector<T> {
140 abstract push_back(value: T): void;
141}
1424. 链表
1434.1 单链表
1444.1.1 带头节点
145暂时无法在飞书文档外展示此内容
146 https://github.com/iqseternal/rapid/blob/pre-main-react/packages/libs/structure/LinkedList/SinglyLinkedList.ts
147头 -> null
148头 -> 元素1 -> 元素2 -> 元素3 -> null
1494.1.2 非带头结点
150null
151元素1 -> null
152元素1 -> 元素2 -> 元素3 -> null
1534.2 双链表
1544.2.1 带头节点
155 https://github.com/iqseternal/rapid/blob/pre-main-react/packages/libs/structure/LinkedList/DoubleLinkedList.ts
156头 -> 元素1 -> 元素2 -> null
157null <- 头 <- 元素1 <- 元素2
1584.2.2 非带头结点
159null
160
161元素1 -> null
162null <- 元素1
163
164元素1 -> 元素2 -> null
165null <- 元素1 <- 元素2
1664.3 循环链表
1674.3.1 循环单链表
1684.3.2 循环双链表
1695. 树
170暂时无法在飞书文档外展示此内容
171declare interface TreeNode<V> {
172 value: V;
173
174 left: TreeNode<V>;
175 right: TreeNode<V>;
176}
1776. 堆
178堆（heap）是一种满足特定条件的完全二叉树。
179小顶堆（min heap）：任意节点的值 <= 其子节点的值。
180大顶堆（max heap）：任意节点的值 >= 其子节点的值。
181[图片]
182优先级队列就是堆的应用：基础数据结构与算法
1837. 图
1847.1 邻接表（散列表
185暂时无法在飞书文档外展示此内容
186const inputs = [
187 [1, 2, 3],
188 [1, 3, 2],
189 [2, 4, 3],
190 [2, 3, 2]
191] as const;
192
193function solution() {
194 const n = 4;
195
196 const head: number[] = new Array(n + 1).fill(-1);
197 const edge: number[] = [];
198 const next: number[] = [];
199 const ver: number[] = [];
200
201 // 边的数量
202 let index = 0;
203
204 for (let i = 0;i < inputs.length;i ++) {
205 const [x, y, cost] = inputs[i];
206 edge[index] = y, ver[index] = cost, next[index] = head[x], head[x] = index ++;
207 }
208
209 const start = 1, end = 4;
210 const flag: boolean[] = new Array(n + 1).fill(false);
211 let canArrive = false;
212
213 function walk(x: number) {
214 flag[x] = true;
215
216 if (x === end) {
217 canArrive = true;
218 return;
219 }
220 if (canArrive) return;
221
222 for (let index = head[x];index != -1 && edge[index] !== -1;index = next[index]) {
223
224 const target = edge[index];
225 const cost = ver[index];
226
227 if (flag[target] === false) {
228 console.log(`${x} => ${edge[index]}`);
229 walk(target);
230 }
231 }
232 }
233
234 walk(start);
235 console.log(`${canArrive ? '' : '不'}能够从点 ${start} 到达点 ${end}`);
236}
237
238solution();
239
2407.2 邻接矩阵
241暂时无法在飞书文档外展示此内容
242
243const inputs = [
244 [1, 2, 3],
245 [1, 4, 2],
246 [2, 4, 3],
247 [1, 3, 2]
248] as const;
249
250function solution() {
251
252 const n = 4;
253 const maps: number[][] = new Array(n + 1).fill(0).map(() => new Array(n + 1).fill(0))
254
255 for (let i = 0;i < inputs.length;i ++) {
256 const [x, y, v] = inputs[i];
257
258 maps[x][y] = v;
259 maps[y][x] = v; // 去掉这一行: 单向图
260 }
261
262 const start = 1, end = 4;
263 const flag = maps.map(() => false);
264
265 let canArrive = false;
266
267 function walk(x: number) {
268 flag[x] = true;
269 if (x === end) {
270 canArrive = true;
271 return;
272 }
273
274 if (canArrive) return;
275
276 for (let i = 1;i <= n;i ++) {
277 if (maps[x][i] !== 0 && flag[i] === false) {
278 walk(i);
279
280 if (canArrive) break;
281 }
282 }
283 }
284
285 walk(start);
286 console.log(`${canArrive ? '' : '不'}能够从点 ${start} 到达点 ${end}`);
287}
288
289solution();
290
291基本算法
2921. 数论
2931.1 质数
294function isPrimeNumber(value: number): boolean {
295 // i * i
296 for (let i = 2;i * i <= value;i ++) {
297 if (value % i === 0) {
298 return false;
299 }
300 }
301
302 return true;
303}
304 简单判别如上，但也确实如此，但如果有条件性：例如，在某个区间范围内需要非常重复的判断一个数是否是质数，如何解决？
305 如果数字较大一些，多轮的判别就会使得这种条件判别造成时间过长，因为每一次都需要去走 for 去除余数。
306
307 打表（如何获得某个范围内的质数集合？ 1-10000000 内。如果用上述方法, 那么运算次数太多了。
308 使用晒素数。利用质数规则，含有因数的数，是合数
309暂时无法在飞书文档外展示此内容
310
311const max = 10000000;
312
313const isPrime = new Array(max + 1).fill(true);
314const primeArr: number[] = [];
315
316function filterPrimeNumber() {
317 isPrime[1] = false;
318
319 for (let i = 2;i <= max;i ++) {
320 if (isPrime[i]) {
321 primeArr.push(i);
322 }
323
324 for (let j = 0;j < primeArr.length;j ++) {
325 if (i * primeArr[j] > max) break;
326 isPrime[i * primeArr[j]] = false;
327 }
328 }
329}
330
331filterPrimeNumber();
332
333console.log(primeArr);
3341.2 快速幂
335/**
336 *
337 * @param a
338 * @param b b >= 0
339 * @returns
340 */
341function binpow(a: number, b: number) {
342 let result = 1;
343 while (b > 0) {
344 if (b & 1) result *= a;
345 a *= a;
346 b = b >> 1;
347 }
348 return result;
349}
350
351console.log(binpow(2, 3));
352
3531.3 x是否2的整数幂
354 判断一个数是否是2的整数幂
355function solution(n: number) {
356 if (n !== ~~n) {
357 throw new Error('Input must be an integer');
358 }
359
360 while (n != 1) {
361 if ((n & 1) !== 0) {
362 return false;
363 }
364 n = n >> 1;
365 }
366
367 return true;
368}
369
370console.log(solution(1));
371console.log(solution(2));
372console.log(solution(3));
373console.log(solution(4));
374console.log(solution(8));
375console.log(solution(16));
376console.log(solution(13));
377console.log(solution(2.2));
378
379
380function solution(n: number) {
381 if (n !== ~~n) {
382 throw new Error('Input must be an integer');
383 }
384 return (n & (n - 1)) === 0;
385}
386
387console.log(solution(1));
388console.log(solution(2));
389
390console.log(solution(3));
391console.log(solution(4));
392console.log(solution(8));
393console.log(solution(16));
394console.log(solution(13));
395
396console.log(solution(2.2));
3972. 博弈论
3981. 摸牌问题
399暂时无法在飞书文档外展示此内容
400 谁能赢？
401const n = 5;
402
403if (n % 3 === 0) {
404 console.log('Cici');
405}
406else {
407 console.log('Kiki');
408}
4093. 排序
4103.1 冒泡
411 依次两两比较，如果满足条件就交换，每一次交换能够保证数组的最右端或者最左端为最大或者最小值。
412
413const arr = [2, 46, 43, 12, 12, 3];
414
415function sort(arr: number[]) {
416
417 for (let i = 0;i < arr.length - 1;i ++) {
418
419 for (let j = 0;j < arr.length - i -1;j ++) {
420
421 if (arr[j] > arr[j + 1]) {
422 let t = arr[j];
423 arr[j] = arr[j + 1];
424 arr[j + 1] = t;
425 }
426 }
427 }
428}
429
430sort(arr);
431
432console.log(arr);;
433
4343.2 快排
435 分治思想，就是把一个大的问题划分为可以直接解决的多个子问题，然后逐个解决这些子问题。
436 假设，数组为一个区间 ————————————————
437 如果有一个定值 x，让这个数组满足 ----------------- x --------------------
438 左侧区间都小于 x，右侧区间都大于 x，那么在宏观来说，区间1 < 区间2 这个整体区间来说就是有序的。
439 那么在逐个解决这两个子区间是否有序的问题，如果这些子区间被逐个递归划分，达到了区间单位长度为 1了，那么这个数组就是有序的了。
440const arr = [1, 2, 9, 3, 5, 4, 1, 12, 546, 1, 2, 9, 3, 5, 4, 1, 12, 546];
441
442function swap<T>(arr: T[], i: number, j: number) {
443 let t = arr[i];
444 arr[i] = arr[j];
445 arr[j] = t;
446}
447
448function quickSort<T>(arr: T[], start: number, end: number, compare: (a: T, b: T) => number) {
449 if (start >= end) return;
450 let i = start - 1, j = end + 1;
451 const x = arr[(start + end) >> 1];
452
453 while (i < j) {
454 do { i ++; } while (compare(x, arr[i]) > 0);
455 do { j --; } while (compare(arr[j], x) > 0);
456 if (i < j) swap(arr, i, j);
457 }
458
459 quickSort(arr, start, j, compare);
460 quickSort(arr, j + 1, end, compare);
461}
462
463quickSort(arr, 0, arr.length - 1, (a, b) => a - b);
464
465console.log(arr);
4663.3 归并
467 分治思想，但是这个思想为先把问题划分下去，逐层解决上来。
468 例如数组arr：先划分区间单位，划分到最小问题上，最小区间单位，也就是长度为1，那么
469 区间 ------------------------------------- 在每个最小单位上它是有序的，宏观上是无序的。
470 那么依次按照划分规则，回传合并。
471 例如：划分区间为 [1, 3, 4] [2, 3, 5]
472 这两个区间，在其子区间内已经回传合并了，然后合并他们。
473 所以合并：[1,2,3,3,4,5] 然后这个区间为有序序列，直到回传到整个数组长度。
474const arr = [1, 2, 9, 3, 5, 4, 1, 12, 546, 1, 2, 9, 3, 5, 4, 1, 12, 546];
475
476function mergeSort<T>(arr: T[], start: number, end: number, compare: (a: T, b: T) => number) {
477 if (start >= end) return;
478
479 const mid = (start + end) >> 1;
480
481 mergeSort(arr, start, mid, compare);
482 mergeSort(arr, mid + 1, end, compare);
483
484 let res: T[] = [];
485 let i = start, j = mid + 1;
486 while (i <= mid && j <= end) {
487 if (compare(arr[i], arr[j]) <= 0) {
488 res.push(arr[i ++]);
489 }
490 else {
491 res.push(arr[j ++]);
492 }
493 }
494 while (i <= mid) res.push(arr[i ++]);
495 while (j <= end) res.push(arr[j ++]);
496 for (let i = 0;i < res.length;i ++) arr[start + i] = res[i];
497}
498
499mergeSort(arr, 0, arr.length - 1, (a, b) => a - b);
500
501console.log(arr);
5024. 前缀/后缀 和 差分
5034.1 前缀和
504 前缀和数组，数组每一项存储原数组下标位置与0下标数组位置之间的和。
505const arr = [1, 2, 3, 4, 5, 6, 7, 8];
506
507function solution() {
508 let fix = 0;
509 const and = arr.map(x => {
510 fix += x;
511 return fix;
512 });
513
514 const searchAnd = (start: number, end: number) => {
515 const safeArea = (index: number, defaultIndex: number) => {
516 if (index < 0 || index >= arr.length) return defaultIndex;
517 return index;
518 }
519
520 const safeStart = safeArea(start - 1, 0), safeEnd = safeArea(end - 1, arr.length - 1);
521
522 return and[safeEnd] - and[safeStart] + arr[safeStart];
523 }
524
525 console.log(searchAnd(1, 1));
526 console.log(searchAnd(1, 3));
527 console.log(searchAnd(3, 7));
528}
529
530solution();
5314.2 后缀和
5324.3 差分
533const arr = [1, 2, 2, 1, 2, 1];
534
535function solution() {
536 // 差分序列
537 const finite = arr.map((x, index) => {
538 if (index === 0) return x;
539 return x - arr[index - 1];
540 });
541
542 console.log(finite);
543}
544
545solution();
546 看起来好像没什么用对吧，上个例子，如上原序列，[1, 2, 2, 1, 2, 1]，现在要进行多次操作，
547 每次会给定区间范围：x -> y, 然后让这个区间内的每一个数都加上 v。
548 问进行 n 次操作后，原序列应该变成了什么样。
549
550 如果用老实的办法，每次都按照操作数对区间元素进行 +v：
551 - 如果 x -> y 区间够长，那么每一次都需要遍历 y-x+1 个元素，也就需要 O(y-x+1), O(n)
552 - 如果 操作次数多，那么会经历多次，如果每次的区间还足够长, 那么足以媲美 O(n^2)
553
554 如下利用差分：
555 1. 得出差分 O(n)
556 2. 走操作 O(n)
557 3. 还原数据 O(n)
558 总的 O(n)
559
560const arr = [1, 2, 2, 1, 2, 1];
561
562// 2 3 3 1 2 1
563// 2 3 3 2 3 2
564// 3 4 4 3 4 3
565
566const operators = [
567 [1, 3, 1],
568 [3, 5, 1],
569 [1, 6, 1]
570] as const;
571
572function solution() {
573 // 差分序列
574 const finite: number[] = arr.map((x, index) => {
575 if (index === 0) return x;
576 return x - arr[index - 1];
577 });
578
579 for (let i = 0;i < operators.length;i++) {
580 const [start, end, v] = operators[i];
581 if (start - 1 >= 0) finite[start - 1] += v;
582 if (end <= finite.length - 1) finite[end] -= v;
583 }
584
585 let fix = 0;
586 const res = finite.map((x, index) => {
587 fix += x;
588 return fix;
589 })
590
591 console.log(res);
592}
593
594solution();
595
5965. 二分查找
597在有序序列中，查找某个数的下标位置，或者查找它存不存在。
598
599const arr = [1, 1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 9, 9, 12];
600
601// 查找 x 第一次出现所在下标, 不存在返回 -1
602function find(x: number): number {
603 let i = 0, j = arr.length - 1;
604
605 while (i < j) {
606 const mid = (i + j) >> 1;
607 if (arr[mid] === x) return mid;
608 if (arr[mid] < x) i = mid + 1;
609 else j = mid;
610 }
611 if (arr[i] === x) return i;
612 return -1;
613}
614
615console.log(find(12), arr[find(12)]);
6166. 递归问题
6176.1 全排列问题
618 全排列问题：有字符 a,b,c,d,e,f,g 需要输出其全排列（可选择排列数
619const arr = ['a', 'b', 'c', 'd'];
620const results: string[] = [];
621
622function arrange(num: number) {
623 const flag = new Array(arr.length).fill(false);
624 const tmp = new Array(num).fill(void 0);
625
626 function rank(position: number) {
627 if (position >= num) {
628 const str = tmp.join('');
629 results.push(str);
630 return;
631 }
632
633 for (let i = 0;i < arr.length;i ++) {
634 if (flag[i]) continue;
635
636 tmp[position] = arr[i];
637 flag[i] = true;
638
639 rank(position + 1);
640
641 tmp[position] = void 0;
642 flag[i] = false;
643 }
644 }
645
646 rank(0);
647}
648
649arrange(3);
650
651console.log(results);
652
6536.2 组合问题
654 组合问题：有字符 a,b,c,d,e,f,g 需要输出其组合 （可选择组合数量
655const arr = ['a', 'b', 'c', 'd'];
656const results: string[] = [];
657
658function combination(num: number) {
659 const flag = new Array(arr.length).fill(false);
660 const tmp = new Array(num).fill(void 0);
661
662 function rank(position: number, n: number) {
663 if (position >= num) {
664 const str = tmp.join('');
665 results.push(str);
666 return;
667 }
668
669 for (let i = n;i < arr.length;i ++) {
670 if (flag[i]) continue;
671
672 tmp[position] = arr[i];
673 flag[i] = true;
674
675 rank(position + 1, i + 1);
676
677 tmp[position] = void 0;
678 flag[i] = false;
679 }
680 }
681
682 rank(0, 0);
683}
684
685combination(3);
686
687console.log(results);
688
6897. 遍历
6907.1 深度优先遍历 dfs
6911. 树
6921. 前序遍历
693暂时无法在飞书文档外展示此内容
694/// 3
695/// / \
696/// 2 5
697/// / \ / \
698/// 1 4 6 7
699interface Tree<T> {
700 value: T;
701 left?: Tree<T>;
702 right?: Tree<T>;
703}
704
705const tree: Tree<number> = {
706 value: 3,
707 left: { value: 2, left: { value: 1 }, right: { value: 4 } },
708 right: { value: 5, left: { value: 6 }, right: { value: 7 } }
709}
710
711let firstStr = ``, midStr = ``, endStr = ``;
712
713function first<T extends Tree<any>>(tree: T) {
714 if (tree.left) first(tree.left);
715 firstStr += `${tree.value}, `;
716 if (tree.right) first(tree.right);
717}
718
719first(tree);
720console.log(firstStr);
721
7222. 中序遍历
723/// 3
724/// / \
725/// 2 5
726/// / \ / \
727/// 1 4 6 7
728interface Tree<T> {
729 value: T;
730 left?: Tree<T>;
731 right?: Tree<T>;
732}
733
734const tree: Tree<number> = {
735 value: 3,
736 left: { value: 2, left: { value: 1 }, right: { value: 4 } },
737 right: { value: 5, left: { value: 6 }, right: { value: 7 } }
738}
739
740let firstStr = ``, midStr = ``, endStr = ``;
741
742function mid<T extends Tree<any>>(tree: T) {
743 midStr += `${tree.value}, `;
744 if (tree.left) mid(tree.left);
745 if (tree.right) mid(tree.right);
746}
747
748mid(tree);
749console.log(midStr);
750
7513. 后序遍历
752/// 3
753/// / \
754/// 2 5
755/// / \ / \
756/// 1 4 6 7
757interface Tree<T> {
758 value: T;
759 left?: Tree<T>;
760 right?: Tree<T>;
761}
762
763const tree: Tree<number> = {
764 value: 3,
765 left: { value: 2, left: { value: 1 }, right: { value: 4 } },
766 right: { value: 5, left: { value: 6 }, right: { value: 7 } }
767}
768
769let firstStr = ``, midStr = ``, endStr = ``;
770
771function end<T extends Tree<any>>(tree: T) {
772 if (tree.left) end(tree.left);
773 if (tree.right) end(tree.right);
774 endStr += `${tree.value}, `;
775}
776
777end(tree);
778console.log(endStr);
779
7802. 图
7812.1 二维矩阵点图
782 判断某个地图能否到达终点，map: 二维空间, 需要从 (0, 0) 到 (n - 1,m - 1) 点，需要判断是否能够到达
783const map = [
784 [0, 0, 0, 0, 0],
785 [0, 0, 0, 1, 0],
786 [1, 0, 0, 0, 0],
787 [0, 0, 0, 1, 1],
788 [0, 1, 0, 0, 0],
789];
790
791function shortestPath(): number {
792 const n = map.length, m = map[n - 1].length;
793
794 const paths: number[][] = new Array(map.length);
795 const rounds: [number, number][][] = new Array(map.length); // 路径
796
797 for (let i = 0; i < map.length; i ++) {
798 paths[i] = new Array(map[i].length);
799 paths[i].fill(-1); // -1 表示不可达
800 rounds[i] = new Array(map[i].length);
801 for (let j = 0;j < rounds[i].length;j ++) rounds[i][j] = [-1, -1];
802 }
803
804 const dx = [0, 1, -1, 0], dy = [1, 0, 0, -1];
805 function checker(x: number, y: number): boolean {
806 if (x < 0 || x >= n || y < 0 || y >= m) return false;
807 return map[x][y] !== 1;
808 }
809
810 const que: [number, number][] = [];
811
812 if (map[0][0] === 0) {
813 que.push([0, 0]);
814 paths[0][0] = 0;
815 }
816
817 while (que.length !== 0) {
818 const [x, y] = que.shift();
819
820 for (let i = 0;i < dx.length && i < dy.length;i ++) {
821 const tx = x + dx[i], ty = y + dy[i];
822
823 if (checker(tx, ty)) {
824 if (paths[tx][ty] === -1) {
825 paths[tx][ty] = paths[x][y] + 1;
826 rounds[tx][ty] = [x, y];
827 que.push([tx, ty]);
828 }
829
830 if (paths[tx][ty] > paths[x][y] + 1) {
831 paths[tx][ty] = paths[x][y] + 1;
832 rounds[tx][ty] = [x, y];
833 }
834 }
835 }
836 }
837
838 return paths[n - 1][m - 1];
839}
840
841console.log(shortestPath()); // true
8422.2 邻接矩阵
843 基础数据结构与算法
8442.3 邻接表
845 基础数据结构与算法
8467.2 广度优先遍历 bfs
847 map: 二维空间, 需要从 (0, 0) 到 (n - 1,m - 1) 点，需要知道最短需要多少步数 （可以涵盖路径）
848
849
850const map = [
851 [0, 0, 0, 0, 0],
852 [0, 0, 0, 1, 0],
853 [1, 0, 0, 0, 0],
854 [0, 0, 0, 1, 1],
855 [0, 1, 0, 0, 0],
856];
857
858function shortestPath(): number {
859 const n = map.length, m = map[n - 1].length;
860
861 const paths: number[][] = new Array(map.length);
862
863 for (let i = 0; i < map.length; i ++) {
864 paths[i] = new Array(map[i].length);
865 paths[i].fill(-1); // -1 表示不可达
866 }
867
868 const dx = [0, 1, -1, 0], dy = [1, 0, 0, -1];
869 function checker(x: number, y: number): boolean {
870 if (x < 0 || x >= n || y < 0 || y >= m) return false;
871 return map[x][y] !== 1;
872 }
873
874 const que: [number, number][] = [];
875
876 if (map[0][0] === 0) {
877 que.push([0, 0]);
878 paths[0][0] = 0;
879 }
880
881 while (que.length !== 0) {
882 const [x, y] = que.shift();
883
884 for (let i = 0;i < dx.length && i < dy.length;i ++) {
885 const tx = x + dx[i], ty = y + dy[i];
886
887 if (checker(tx, ty)) {
888 if (paths[tx][ty] === -1) {
889 paths[tx][ty] = paths[x][y] + 1;
890 que.push([tx, ty]);
891 }
892
893 paths[tx][ty] = Math.min(paths[tx][ty], paths[x][y] + 1);
894 }
895 }
896 }
897
898 return paths[n - 1][m - 1];
899}
900
901console.log(shortestPath()); // true
9027.3 最短路
903暂时无法在飞书文档外展示此内容
904 采用图遍历（上述遍历方式遍历即可，在遍历到达终点的时候，同时记录最小值就行）
9057.3.1 djkstra
906import { PriorityQueue } from '@rapid/libs';
907// 优先级队列，需要自行实现，js 没有现成的。不然去找三方库也可以
908
909const inputs = [
910 [1, 2, 3],
911 [1, 4, 7],
912 [2, 4, 3],
913 [1, 3, 2],
914 [3, 4, 2]
915] as const;
916
917function solution() {
918
919 const n = 4;
920 const maps: number[][] = new Array(n + 1).fill(0).map(() => new Array(n + 1).fill(0))
921
922 for (let i = 0;i < inputs.length;i ++) {
923 const [x, y, v] = inputs[i];
924 maps[x][y] = v;
925 }
926
927 const paths: number[] = new Array(n + 1).fill(Infinity);
928 const sure: boolean[] = new Array(n + 1).fill(false);
929
930 const que = new PriorityQueue<{ j: number;value: number; }>();
931 que.setComparator((node1, node2) => {
932 return node1.value - node2.value;
933 })
934
935 paths[1] = 0;
936 que.push({ j: 1, value: 0 });
937
938 while (!que.isEmpty()) {
939 const top = que.pop();
940 const { j, value } = top;
941
942 if (sure[j]) continue;
943 sure[j] = true;
944
945 for (let y = 1;y <= n;y ++) {
946 // 有路
947 if (maps[j][y] !== 0) {
948 const v = maps[j][y];
949
950 if (paths[j] + v < paths[y]) {
951
952 paths[y] = paths[j] + v;
953
954 que.push({ j: y, value: paths[y] });
955 }
956 }
957 }
958 }
959
960 console.log(paths[n]);
961}
962
963solution();
964
9658. 并查集
966此类算法要和具体的问题结合理解。例如：找亲戚问题。
967有一群人，a - b 是亲戚，b - c 是亲戚, 那么 a - c 就是亲戚。
968那么给出一堆人的两两关系, 要求随机的查找 某两个人是否是亲戚。
969暂时无法在飞书文档外展示此内容
970// 亲戚关系表
971const listOfRelatives: number[] = [];
972// 表长度, 表索引
973let index = 0;
974
975// 通过id标识查找这个人在 关系表中的下标位置
976const idToIndexMap = new Map<string, number>();
977
978// 关系网,
979const arr = [
980 ['a', 'b', 'c'],
981 ['c', 'g', 'f'],
982 ['j', 'k'],
983 ['l', 'm', 'p'],
984 ['p', 'e'],
985 ['e', 'j']
986];
987
988function add(a: string) {
989 if (idToIndexMap.has(a)) return idToIndexMap.get(a)!;
990 idToIndexMap.set(a, index);
991 listOfRelatives[index] = index;
992 index ++;
993 return index - 1;
994}
995
996function find(index: number): number {
997 if (listOfRelatives[index] !== index) listOfRelatives[index] = find(listOfRelatives[index]);
998 return listOfRelatives[index];
999}
1000
1001function findChar(char: string): number {
1002 const index = add(char);
1003 return find(index);
1004}
1005
1006function contain(a: string, b: string) {
1007 listOfRelatives[findChar(a)] = findChar(b);
1008}
1009
1010function init() {
1011 arr.forEach(list => {
1012 for (let i = 0;i < list.length - 1;i ++) {
1013 contain(list[i], list[i + 1]);
1014 }
1015 })
1016}
1017
1018init();
1019
1020console.log('find', findChar('a') === findChar('e'));
10219. 贪心
1022基础数据结构与算法dijkstra就是一个典型的贪心算法应用
102310. 动态规划
102410.1 01背包问题
1025 problem：https://www.acwing.com/problem/content/2/
1026 贪心是不能解决此类问题的。
1027 诸如：贪心解决此类问题的思路为，一直拿取性价比最高的物品，直到装不下。但是可能会出现，拿两个物品组合起来性价比堪比最高性价比的一个物品的情况，那么贪心就出问题了。
1028
1029 如何动态规划？动态规划也就是去找状态转移方程。
10304 5 // 总共有 4件物品，背包体积为 5
10311 2
10322 4
10333 4
10344 5
1035 1. 拿一件物品，那么当然就是有容量的才可以拿。第一件物品的容量 1，价值 2
1036物品 i/体积 j
10370
10381
10392
10403
10414
10425
10431
10440
10452
10462
10472
10482
10492
1050 如果 背包体积 > 物品体积，背包价值 = 物品价值
1051 如果 背包体积为 j < 物品体积, 那么背包价值 = 背包[i][j - 1] 的价值
1052 2. 拿第二件物品，此时背包里面可能已经放置了物品。此时需要取判断。第二件物品容量 2，价值 4
1053物品 i/体积 j
10540
10551
10562
10573
10584
10595
10601
10610
10622
10632
10642
10652
10662
10672
10680
10692
10704
10716
10726
10736
1074 在选择当前背包是否放入当前物品，需要考虑什么？ 该物品是否可以放得下，放下该物品价值是否更高？
1075 该物品是否可以放得下：j >= 物品体积 保证可以放，否则放不下那就只能是背包 [i - 1][j] 的价值 (上一次迭代的价值)
1076 放下该物品价值是否更高：max(原本的背包价值, 放下该物品的后背包的价值)
1077 max(背包[i - 1][j], 背包[i - 1][j - 物品体积] + 物品价值) , 第二项为 在背包能够容纳当前物品时的最大价值加上当前物品的价值
1078 获得最大值后，就是该物品的最大价值。
1079 3. 拿第三/四件物品，第三件容量为 3，价值为 4
1080物品 i/体积 j
10810
10821
10832
10843
10854
10865
10871
10880
10892
10902
10912
10922
10932
10942
10950
10962
10974
10986
10996
11006
11013
11020
11032
11044
11056
11066
11078
11084
11090
11102
11114
11126
11136
11148
1115 所以最大价值就是 8.
1116 按照逻辑推理, 设定 f[N][M] 为背包，v[N] 为物品体积，w[N] 为物品价值
1117 即状态转移方程：
1118 f[i][j] = f[i - 1][j]
1119 f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i])
1120 二维数组
1121#include <bits/stdc++.h>
1122
1123using namespace std;
1124
1125const int N = 1010;
1126
1127int v[N], w[N];
1128int f[N][N];
1129
1130int main() {
1131 int n, m;
1132 cin >> n >> m;
1133
1134 for (int i = 1;i <= n;i ++) cin >> v[i] >> w[i];
1135
1136 for (int i = 1;i <= n;i ++) {
1137 for (int j = 1;j <= m;j ++) {
1138
1139 if (j >= v[i]) {
1140 f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
1141 }
1142 else {
1143 f[i][j] = f[i - 1][j];
1144 }
1145
1146 }
1147 }
1148
1149 cout << f[n][m] << endl;
1150 return 0;
1151}
1152
1153 上面的解决用到了二维数组，但是在推导过程中不难发现：当背包体积为 j 的时候，f[i][j] 的状态推导与 f[i][j - 1], f[i][j - 2], f[i][j - 3]....无关，如果只用一个一维数组，每次拿物品重复迭代这个数组，那么也是可以的。
1154
1155 j的方向需要逆序，因为如果正序迭代背包，那么后面的元素会被前面的影响。
1156
1157 一维数组版本 (滚动数组
1158#include <bits/stdc++.h>
1159
1160using namespace std;
1161
1162const int N = 1010;
1163
1164int v[N], w[N];
1165int f[N];
1166
1167int main() {
1168 int n, m;
1169 cin >> n >> m;
1170
1171 for (int i = 1;i <= n;i ++) cin >> v[i] >> w[i];
1172
1173 for (int i = 1;i <= n;i ++) {
1174 for (int j = m;j >= v[i];j --) {
1175 f[j] = max(f[j], f[j - v[i]] + w[i]);
1176 }
1177 }
1178
1179 cout << f[m] << endl;
1180 return 0;
1181}
118210.2 完全背包问题
1183 与 01 背包问题一致，也就是物品可以无限使用，那么就在放置物品的时候，判断是否可以多次放置该物品即可。然后一次性放置尽可能多的物品，但是状态转移方程基本一致。
1184 K 为放置同一件物品 k 次
1185 f[i][j] = f[i - 1][j]
1186 f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i] * k] + w[i] * k)
118710.3 多重背包问题
118810.3.1 数据量小
1189 对于物品有具体的数量，那么可以把同一种物品看作是多个物品。
1190 例如：1号物品 体积 2，价值 3，数量 3
1191 那么可以放置 3 次一号物品作为不同的物品进行 01背包问题处理。
119210.3.2 数据量大
1193 如果数据量大，利用将多重背包化解为 01 背包问题求解时，可能会导致超时情况出现。那么需要优化。
1194 其根本思路不变，但是进行化解的时候需要进行特定处理。
1195 例如：
1196 3 个物品，我们可以纳入 2 个物品和 1 个物品
1197 7 个物品，我们可以纳入 4 个物品和 2 个物品和 1个物品
1198 6 个物品，我们可以纳入 3 个物品和 2 个物品和1个物品
1199 为什么这么做？为什么这样划分：
1200 因为把 7 划分为 4，2，1
1201 可以利用 4，2，1组合出 1~7 中的所有数字。
1202 1，
1203 2，
1204 3：2 + 1，
1205 4，
1206 5：4 + 1，
1207 6：4 + 2，
1208 7：4 + 2 + 1
1209
1210 为什么？？那么去分析这个数的二进制：7 => 111
1211 我们把 111 分成了 100, 10, 1 显而易见可以组合出自己想要的任何数字。
1212 6 => 110 => 11,10,1
1213
1214
1215数据结构
12161. 栈
1217abstract class Stack<T> {
1218 abstract push(value: T): void;
1219 abstract pop(): T;
1220}
12211.1 单调栈
1222暂时无法在飞书文档外展示此内容
12232. 队列
12242.1 单向队列
1225 https://github.com/iqseternal/rapid/blob/pre-main-react/packages/libs/structure/Queue/Queue.ts
1226abstract class Queue<T> {
1227 abstract push(value: T): void;
1228 abstract pop(): T;
1229}
12302.2 双端队列
1231 https://github.com/iqseternal/rapid/blob/pre-main-react/packages/libs/structure/Queue/Dequeue.ts
1232abstract class Dequeue<T> {
1233 abstract push_back(value: T): void;
1234 abstract pop_back(): T;
1235
1236 abstract push_front(value: T): void;
1237 abstract pop_front(): T;
1238}
12392.3 单调队列（优先级队列
1240暂时无法在飞书文档外展示此内容
1241export interface Comparator<V> {
1242 (v1: V, v2: V): number;
1243}
1244
1245export abstract class Vessel<V> {
1246 protected comparator: Comparator<V> = (v1, v2) => {
1247 if (v1 === v2) return 0;
1248 if (typeof v1 !== 'number' || typeof v1 !== 'string') return 1;
1249 if (typeof v2 !== 'number' || typeof v2 !== 'string') return 1;
1250 if (v1 > v2) return 1;
1251 return -1;
1252 };
1253
1254 public abstract [Symbol.iterator](): Iterator<V>;
1255 public abstract size(): number;
1256 public abstract isEmpty(): boolean;
1257 public abstract clear(): void;
1258 public abstract contains(value: V): boolean;
1259 public setComparator(comparator: Comparator<V>): void { this.comparator = comparator; }
1260}
1261
1262export class PriorityQueue<V> extends Vessel<V> {
1263
1264 private priorityQueueArr: [undefined, ...V[]] = [void 0];
1265 private length: number = 0;
1266
1267 public override *[Symbol.iterator](): Iterator<V> {
1268 while (this.length) {
1269 const v = this.pop()!;
1270 yield v;
1271 }
1272 }
1273
1274 public top(): V | null {
1275 if (this.length === 0) return null;
1276 return this.priorityQueueArr[1];
1277 }
1278
1279 public push(...values: V[]): void {
1280 values.forEach(value => {
1281 this.priorityQueueArr[++ this.length] = value;
1282 this.swim(this.length);
1283 })
1284 }
1285
1286 public pop(): V | null {
1287 if (this.length === 0) return null;
1288 const value = this.priorityQueueArr[1]!;
1289 this.swap(1, this.length);
1290 this.length --;
1291 this.sink(1);
1292 return value;
1293 }
1294
1295 private swim(index: number) {
1296 while (index > 1 && this.comparator(this.priorityQueueArr[index]!, this.priorityQueueArr[index >> 1]!) < 0) {
1297 this.swap(index, index >> 1);
1298
1299 index = index >> 1;
1300 }
1301 }
1302
1303 private sink(index: number) {
1304 if (index <= 0) return;
1305
1306 while (2 * index <= this.length) {
1307 let k = index * 2;
1308
1309 if (k + 1 <= this.length && this.comparator(this.priorityQueueArr[k + 1]!, this.priorityQueueArr[k]!) < 0) {
1310 k ++;
1311 }
1312
1313 if (this.comparator(this.priorityQueueArr[index]!, this.priorityQueueArr[k]!) > 0) {
1314 this.swap(index, k);
1315 index = k;
1316 continue;
1317 }
1318
1319 break;
1320 }
1321 }
1322
1323 private swap(i: number, j: number) {
1324 if (i <= 0 || i > this.length) return;
1325 if (j <= 0 || j > this.length) return;
1326 const t = this.priorityQueueArr[i];
1327 this.priorityQueueArr[i] = this.priorityQueueArr[j];
1328 this.priorityQueueArr[j] = t;
1329 }
1330
1331 public override contains(value: V): boolean {
1332 for (let i = 1;i <= this.length;i ++) {
1333 const v = this.priorityQueueArr[i];
1334 if (this.comparator(v!, value) === 0) return true;
1335 }
1336 return false;
1337 }
1338
1339 public override clear() {
1340 this.priorityQueueArr = [void 0];
1341 this.length = 0;
1342 }
1343
1344 public override isEmpty(): boolean {
1345 return this.size() === 0;
1346 }
1347
1348 public override size(): number {
1349 return this.length;
1350 }
1351}
13523. 数组（向量。
1353abstract class Vector<T> {
1354 abstract push_back(value: T): void;
1355}
13564. 链表
13574.1 单链表
13584.1.1 带头节点
1359暂时无法在飞书文档外展示此内容
1360 https://github.com/iqseternal/rapid/blob/pre-main-react/packages/libs/structure/LinkedList/SinglyLinkedList.ts
1361头 -> null
1362头 -> 元素1 -> 元素2 -> 元素3 -> null
13634.1.2 非带头结点
1364null
1365元素1 -> null
1366元素1 -> 元素2 -> 元素3 -> null
13674.2 双链表
13684.2.1 带头节点
1369 https://github.com/iqseternal/rapid/blob/pre-main-react/packages/libs/structure/LinkedList/DoubleLinkedList.ts
1370头 -> 元素1 -> 元素2 -> null
1371null <- 头 <- 元素1 <- 元素2
13724.2.2 非带头结点
1373null
1374
1375元素1 -> null
1376null <- 元素1
1377
1378元素1 -> 元素2 -> null
1379null <- 元素1 <- 元素2
13804.3 循环链表
13814.3.1 循环单链表
13824.3.2 循环双链表
13835. 树
1384暂时无法在飞书文档外展示此内容
1385declare interface TreeNode<V> {
1386 value: V;
1387
1388 left: TreeNode<V>;
1389 right: TreeNode<V>;
1390}
13916. 堆
1392堆（heap）是一种满足特定条件的完全二叉树。
1393小顶堆（min heap）：任意节点的值 <= 其子节点的值。
1394大顶堆（max heap）：任意节点的值 >= 其子节点的值。
1395[图片]
1396优先级队列就是堆的应用：基础数据结构与算法
13977. 图
13987.1 邻接表（散列表
1399暂时无法在飞书文档外展示此内容
1400const inputs = [
1401 [1, 2, 3],
1402 [1, 3, 2],
1403 [2, 4, 3],
1404 [2, 3, 2]
1405] as const;
1406
1407function solution() {
1408 const n = 4;
1409
1410 const head: number[] = new Array(n + 1).fill(-1);
1411 const edge: number[] = [];
1412 const next: number[] = [];
1413 const ver: number[] = [];
1414
1415 // 边的数量
1416 let index = 0;
1417
1418 for (let i = 0;i < inputs.length;i ++) {
1419 const [x, y, cost] = inputs[i];
1420 edge[index] = y, ver[index] = cost, next[index] = head[x], head[x] = index ++;
1421 }
1422
1423 const start = 1, end = 4;
1424 const flag: boolean[] = new Array(n + 1).fill(false);
1425 let canArrive = false;
1426
1427 function walk(x: number) {
1428 flag[x] = true;
1429
1430 if (x === end) {
1431 canArrive = true;
1432 return;
1433 }
1434 if (canArrive) return;
1435
1436 for (let index = head[x];index != -1 && edge[index] !== -1;index = next[index]) {
1437
1438 const target = edge[index];
1439 const cost = ver[index];
1440
1441 if (flag[target] === false) {
1442 console.log(`${x} => ${edge[index]}`);
1443 walk(target);
1444 }
1445 }
1446 }
1447
1448 walk(start);
1449 console.log(`${canArrive ? '' : '不'}能够从点 ${start} 到达点 ${end}`);
1450}
1451
1452solution();
1453
14547.2 邻接矩阵
1455暂时无法在飞书文档外展示此内容
1456
1457const inputs = [
1458 [1, 2, 3],
1459 [1, 4, 2],
1460 [2, 4, 3],
1461 [1, 3, 2]
1462] as const;
1463
1464function solution() {
1465
1466 const n = 4;
1467 const maps: number[][] = new Array(n + 1).fill(0).map(() => new Array(n + 1).fill(0))
1468
1469 for (let i = 0;i < inputs.length;i ++) {
1470 const [x, y, v] = inputs[i];
1471
1472 maps[x][y] = v;
1473 maps[y][x] = v; // 去掉这一行: 单向图
1474 }
1475
1476 const start = 1, end = 4;
1477 const flag = maps.map(() => false);
1478
1479 let canArrive = false;
1480
1481 function walk(x: number) {
1482 flag[x] = true;
1483 if (x === end) {
1484 canArrive = true;
1485 return;
1486 }
1487
1488 if (canArrive) return;
1489
1490 for (let i = 1;i <= n;i ++) {
1491 if (maps[x][i] !== 0 && flag[i] === false) {
1492 walk(i);
1493
1494 if (canArrive) break;
1495 }
1496 }
1497 }
1498
1499 walk(start);
1500 console.log(`${canArrive ? '' : '不'}能够从点 ${start} 到达点 ${end}`);
1501}
1502
1503solution();
1504
1505基本算法
15061. 数论
15071.1 质数
1508function isPrimeNumber(value: number): boolean {
1509 // i * i
1510 for (let i = 2;i * i <= value;i ++) {
1511 if (value % i === 0) {
1512 return false;
1513 }
1514 }
1515
1516 return true;
1517}
1518 简单判别如上，但也确实如此，但如果有条件性：例如，在某个区间范围内需要非常重复的判断一个数是否是质数，如何解决？
1519 如果数字较大一些，多轮的判别就会使得这种条件判别造成时间过长，因为每一次都需要去走 for 去除余数。
1520
1521 打表（如何获得某个范围内的质数集合？ 1-10000000 内。如果用上述方法, 那么运算次数太多了。
1522 使用晒素数。利用质数规则，含有因数的数，是合数
1523暂时无法在飞书文档外展示此内容
1524
1525const max = 10000000;
1526
1527const isPrime = new Array(max + 1).fill(true);
1528const primeArr: number[] = [];
1529
1530function filterPrimeNumber() {
1531 isPrime[1] = false;
1532
1533 for (let i = 2;i <= max;i ++) {
1534 if (isPrime[i]) {
1535 primeArr.push(i);
1536 }
1537
1538 for (let j = 0;j < primeArr.length;j ++) {
1539 if (i * primeArr[j] > max) break;
1540 isPrime[i * primeArr[j]] = false;
1541 }
1542 }
1543}
1544
1545filterPrimeNumber();
1546
1547console.log(primeArr);
15481.2 快速幂
1549/**
1550 *
1551 * @param a
1552 * @param b b >= 0
1553 * @returns
1554 */
1555function binpow(a: number, b: number) {
1556 let result = 1;
1557 while (b > 0) {
1558 if (b & 1) result *= a;
1559 a *= a;
1560 b = b >> 1;
1561 }
1562 return result;
1563}
1564
1565console.log(binpow(2, 3));
1566
15671.3 x是否2的整数幂
1568 判断一个数是否是2的整数幂
1569function solution(n: number) {
1570 if (n !== ~~n) {
1571 throw new Error('Input must be an integer');
1572 }
1573
1574 while (n != 1) {
1575 if ((n & 1) !== 0) {
1576 return false;
1577 }
1578 n = n >> 1;
1579 }
1580
1581 return true;
1582}
1583
1584console.log(solution(1));
1585console.log(solution(2));
1586console.log(solution(3));
1587console.log(solution(4));
1588console.log(solution(8));
1589console.log(solution(16));
1590console.log(solution(13));
1591console.log(solution(2.2));
1592
1593
1594function solution(n: number) {
1595 if (n !== ~~n) {
1596 throw new Error('Input must be an integer');
1597 }
1598 return (n & (n - 1)) === 0;
1599}
1600
1601console.log(solution(1));
1602console.log(solution(2));
1603
1604console.log(solution(3));
1605console.log(solution(4));
1606console.log(solution(8));
1607console.log(solution(16));
1608console.log(solution(13));
1609
1610console.log(solution(2.2));
16112. 博弈论
16121. 摸牌问题
1613暂时无法在飞书文档外展示此内容
1614 谁能赢？
1615const n = 5;
1616
1617if (n % 3 === 0) {
1618 console.log('Cici');
1619}
1620else {
1621 console.log('Kiki');
1622}
16233. 排序
16243.1 冒泡
1625 依次两两比较，如果满足条件就交换，每一次交换能够保证数组的最右端或者最左端为最大或者最小值。
1626
1627const arr = [2, 46, 43, 12, 12, 3];
1628
1629function sort(arr: number[]) {
1630
1631 for (let i = 0;i < arr.length - 1;i ++) {
1632
1633 for (let j = 0;j < arr.length - i -1;j ++) {
1634
1635 if (arr[j] > arr[j + 1]) {
1636 let t = arr[j];
1637 arr[j] = arr[j + 1];
1638 arr[j + 1] = t;
1639 }
1640 }
1641 }
1642}
1643
1644sort(arr);
1645
1646console.log(arr);;
1647
16483.2 快排
1649 分治思想，就是把一个大的问题划分为可以直接解决的多个子问题，然后逐个解决这些子问题。
1650 假设，数组为一个区间 ————————————————
1651 如果有一个定值 x，让这个数组满足 ----------------- x --------------------
1652 左侧区间都小于 x，右侧区间都大于 x，那么在宏观来说，区间1 < 区间2 这个整体区间来说就是有序的。
1653 那么在逐个解决这两个子区间是否有序的问题，如果这些子区间被逐个递归划分，达到了区间单位长度为 1了，那么这个数组就是有序的了。
1654const arr = [1, 2, 9, 3, 5, 4, 1, 12, 546, 1, 2, 9, 3, 5, 4, 1, 12, 546];
1655
1656function swap<T>(arr: T[], i: number, j: number) {
1657 let t = arr[i];
1658 arr[i] = arr[j];
1659 arr[j] = t;
1660}
1661
1662function quickSort<T>(arr: T[], start: number, end: number, compare: (a: T, b: T) => number) {
1663 if (start >= end) return;
1664 let i = start - 1, j = end + 1;
1665 const x = arr[(start + end) >> 1];
1666
1667 while (i < j) {
1668 do { i ++; } while (compare(x, arr[i]) > 0);
1669 do { j --; } while (compare(arr[j], x) > 0);
1670 if (i < j) swap(arr, i, j);
1671 }
1672
1673 quickSort(arr, start, j, compare);
1674 quickSort(arr, j + 1, end, compare);
1675}
1676
1677quickSort(arr, 0, arr.length - 1, (a, b) => a - b);
1678
1679console.log(arr);
16803.3 归并
1681 分治思想，但是这个思想为先把问题划分下去，逐层解决上来。
1682 例如数组arr：先划分区间单位，划分到最小问题上，最小区间单位，也就是长度为1，那么
1683 区间 ------------------------------------- 在每个最小单位上它是有序的，宏观上是无序的。
1684 那么依次按照划分规则，回传合并。
1685 例如：划分区间为 [1, 3, 4] [2, 3, 5]
1686 这两个区间，在其子区间内已经回传合并了，然后合并他们。
1687 所以合并：[1,2,3,3,4,5] 然后这个区间为有序序列，直到回传到整个数组长度。
1688const arr = [1, 2, 9, 3, 5, 4, 1, 12, 546, 1, 2, 9, 3, 5, 4, 1, 12, 546];
1689
1690function mergeSort<T>(arr: T[], start: number, end: number, compare: (a: T, b: T) => number) {
1691 if (start >= end) return;
1692
1693 const mid = (start + end) >> 1;
1694
1695 mergeSort(arr, start, mid, compare);
1696 mergeSort(arr, mid + 1, end, compare);
1697
1698 let res: T[] = [];
1699 let i = start, j = mid + 1;
1700 while (i <= mid && j <= end) {
1701 if (compare(arr[i], arr[j]) <= 0) {
1702 res.push(arr[i ++]);
1703 }
1704 else {
1705 res.push(arr[j ++]);
1706 }
1707 }
1708 while (i <= mid) res.push(arr[i ++]);
1709 while (j <= end) res.push(arr[j ++]);
1710 for (let i = 0;i < res.length;i ++) arr[start + i] = res[i];
1711}
1712
1713mergeSort(arr, 0, arr.length - 1, (a, b) => a - b);
1714
1715console.log(arr);
17164. 前缀/后缀 和 差分
17174.1 前缀和
1718 前缀和数组，数组每一项存储原数组下标位置与0下标数组位置之间的和。
1719const arr = [1, 2, 3, 4, 5, 6, 7, 8];
1720
1721function solution() {
1722 let fix = 0;
1723 const and = arr.map(x => {
1724 fix += x;
1725 return fix;
1726 });
1727
1728 const searchAnd = (start: number, end: number) => {
1729 const safeArea = (index: number, defaultIndex: number) => {
1730 if (index < 0 || index >= arr.length) return defaultIndex;
1731 return index;
1732 }
1733
1734 const safeStart = safeArea(start - 1, 0), safeEnd = safeArea(end - 1, arr.length - 1);
1735
1736 return and[safeEnd] - and[safeStart] + arr[safeStart];
1737 }
1738
1739 console.log(searchAnd(1, 1));
1740 console.log(searchAnd(1, 3));
1741 console.log(searchAnd(3, 7));
1742}
1743
1744solution();
17454.2 后缀和
17464.3 差分
1747const arr = [1, 2, 2, 1, 2, 1];
1748
1749function solution() {
1750 // 差分序列
1751 const finite = arr.map((x, index) => {
1752 if (index === 0) return x;
1753 return x - arr[index - 1];
1754 });
1755
1756 console.log(finite);
1757}
1758
1759solution();
1760 看起来好像没什么用对吧，上个例子，如上原序列，[1, 2, 2, 1, 2, 1]，现在要进行多次操作，
1761 每次会给定区间范围：x -> y, 然后让这个区间内的每一个数都加上 v。
1762 问进行 n 次操作后，原序列应该变成了什么样。
1763
1764 如果用老实的办法，每次都按照操作数对区间元素进行 +v：
1765 - 如果 x -> y 区间够长，那么每一次都需要遍历 y-x+1 个元素，也就需要 O(y-x+1), O(n)
1766 - 如果 操作次数多，那么会经历多次，如果每次的区间还足够长, 那么足以媲美 O(n^2)
1767
1768 如下利用差分：
1769 1. 得出差分 O(n)
1770 2. 走操作 O(n)
1771 3. 还原数据 O(n)
1772 总的 O(n)
1773
1774const arr = [1, 2, 2, 1, 2, 1];
1775
1776// 2 3 3 1 2 1
1777// 2 3 3 2 3 2
1778// 3 4 4 3 4 3
1779
1780const operators = [
1781 [1, 3, 1],
1782 [3, 5, 1],
1783 [1, 6, 1]
1784] as const;
1785
1786function solution() {
1787 // 差分序列
1788 const finite: number[] = arr.map((x, index) => {
1789 if (index === 0) return x;
1790 return x - arr[index - 1];
1791 });
1792
1793 for (let i = 0;i < operators.length;i++) {
1794 const [start, end, v] = operators[i];
1795 if (start - 1 >= 0) finite[start - 1] += v;
1796 if (end <= finite.length - 1) finite[end] -= v;
1797 }
1798
1799 let fix = 0;
1800 const res = finite.map((x, index) => {
1801 fix += x;
1802 return fix;
1803 })
1804
1805 console.log(res);
1806}
1807
1808solution();
1809
18105. 二分查找
1811在有序序列中，查找某个数的下标位置，或者查找它存不存在。
1812
1813const arr = [1, 1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 9, 9, 12];
1814
1815// 查找 x 第一次出现所在下标, 不存在返回 -1
1816function find(x: number): number {
1817 let i = 0, j = arr.length - 1;
1818
1819 while (i < j) {
1820 const mid = (i + j) >> 1;
1821 if (arr[mid] === x) return mid;
1822 if (arr[mid] < x) i = mid + 1;
1823 else j = mid;
1824 }
1825 if (arr[i] === x) return i;
1826 return -1;
1827}
1828
1829console.log(find(12), arr[find(12)]);
18306. 递归问题
18316.1 全排列问题
1832 全排列问题：有字符 a,b,c,d,e,f,g 需要输出其全排列（可选择排列数
1833const arr = ['a', 'b', 'c', 'd'];
1834const results: string[] = [];
1835
1836function arrange(num: number) {
1837 const flag = new Array(arr.length).fill(false);
1838 const tmp = new Array(num).fill(void 0);
1839
1840 function rank(position: number) {
1841 if (position >= num) {
1842 const str = tmp.join('');
1843 results.push(str);
1844 return;
1845 }
1846
1847 for (let i = 0;i < arr.length;i ++) {
1848 if (flag[i]) continue;
1849
1850 tmp[position] = arr[i];
1851 flag[i] = true;
1852
1853 rank(position + 1);
1854
1855 tmp[position] = void 0;
1856 flag[i] = false;
1857 }
1858 }
1859
1860 rank(0);
1861}
1862
1863arrange(3);
1864
1865console.log(results);
1866
18676.2 组合问题
1868 组合问题：有字符 a,b,c,d,e,f,g 需要输出其组合 （可选择组合数量
1869const arr = ['a', 'b', 'c', 'd'];
1870const results: string[] = [];
1871
1872function combination(num: number) {
1873 const flag = new Array(arr.length).fill(false);
1874 const tmp = new Array(num).fill(void 0);
1875
1876 function rank(position: number, n: number) {
1877 if (position >= num) {
1878 const str = tmp.join('');
1879 results.push(str);
1880 return;
1881 }
1882
1883 for (let i = n;i < arr.length;i ++) {
1884 if (flag[i]) continue;
1885
1886 tmp[position] = arr[i];
1887 flag[i] = true;
1888
1889 rank(position + 1, i + 1);
1890
1891 tmp[position] = void 0;
1892 flag[i] = false;
1893 }
1894 }
1895
1896 rank(0, 0);
1897}
1898
1899combination(3);
1900
1901console.log(results);
1902
19037. 遍历
19047.1 深度优先遍历 dfs
19051. 树
19061. 前序遍历
1907暂时无法在飞书文档外展示此内容
1908/// 3
1909/// / \
1910/// 2 5
1911/// / \ / \
1912/// 1 4 6 7
1913interface Tree<T> {
1914 value: T;
1915 left?: Tree<T>;
1916 right?: Tree<T>;
1917}
1918
1919const tree: Tree<number> = {
1920 value: 3,
1921 left: { value: 2, left: { value: 1 }, right: { value: 4 } },
1922 right: { value: 5, left: { value: 6 }, right: { value: 7 } }
1923}
1924
1925let firstStr = ``, midStr = ``, endStr = ``;
1926
1927function first<T extends Tree<any>>(tree: T) {
1928 if (tree.left) first(tree.left);
1929 firstStr += `${tree.value}, `;
1930 if (tree.right) first(tree.right);
1931}
1932
1933first(tree);
1934console.log(firstStr);
1935
19362. 中序遍历
1937/// 3
1938/// / \
1939/// 2 5
1940/// / \ / \
1941/// 1 4 6 7
1942interface Tree<T> {
1943 value: T;
1944 left?: Tree<T>;
1945 right?: Tree<T>;
1946}
1947
1948const tree: Tree<number> = {
1949 value: 3,
1950 left: { value: 2, left: { value: 1 }, right: { value: 4 } },
1951 right: { value: 5, left: { value: 6 }, right: { value: 7 } }
1952}
1953
1954let firstStr = ``, midStr = ``, endStr = ``;
1955
1956function mid<T extends Tree<any>>(tree: T) {
1957 midStr += `${tree.value}, `;
1958 if (tree.left) mid(tree.left);
1959 if (tree.right) mid(tree.right);
1960}
1961
1962mid(tree);
1963console.log(midStr);
1964
19653. 后序遍历
1966/// 3
1967/// / \
1968/// 2 5
1969/// / \ / \
1970/// 1 4 6 7
1971interface Tree<T> {
1972 value: T;
1973 left?: Tree<T>;
1974 right?: Tree<T>;
1975}
1976
1977const tree: Tree<number> = {
1978 value: 3,
1979 left: { value: 2, left: { value: 1 }, right: { value: 4 } },
1980 right: { value: 5, left: { value: 6 }, right: { value: 7 } }
1981}
1982
1983let firstStr = ``, midStr = ``, endStr = ``;
1984
1985function end<T extends Tree<any>>(tree: T) {
1986 if (tree.left) end(tree.left);
1987 if (tree.right) end(tree.right);
1988 endStr += `${tree.value}, `;
1989}
1990
1991end(tree);
1992console.log(endStr);
1993
19942. 图
19952.1 二维矩阵点图
1996 判断某个地图能否到达终点，map: 二维空间, 需要从 (0, 0) 到 (n - 1,m - 1) 点，需要判断是否能够到达
1997const map = [
1998 [0, 0, 0, 0, 0],
1999 [0, 0, 0, 1, 0],
2000 [1, 0, 0, 0, 0],
2001 [0, 0, 0, 1, 1],
2002 [0, 1, 0, 0, 0],
2003];
2004
2005function shortestPath(): number {
2006 const n = map.length, m = map[n - 1].length;
2007
2008 const paths: number[][] = new Array(map.length);
2009 const rounds: [number, number][][] = new Array(map.length); // 路径
2010
2011 for (let i = 0; i < map.length; i ++) {
2012 paths[i] = new Array(map[i].length);
2013 paths[i].fill(-1); // -1 表示不可达
2014 rounds[i] = new Array(map[i].length);
2015 for (let j = 0;j < rounds[i].length;j ++) rounds[i][j] = [-1, -1];
2016 }
2017
2018 const dx = [0, 1, -1, 0], dy = [1, 0, 0, -1];
2019 function checker(x: number, y: number): boolean {
2020 if (x < 0 || x >= n || y < 0 || y >= m) return false;
2021 return map[x][y] !== 1;
2022 }
2023
2024 const que: [number, number][] = [];
2025
2026 if (map[0][0] === 0) {
2027 que.push([0, 0]);
2028 paths[0][0] = 0;
2029 }
2030
2031 while (que.length !== 0) {
2032 const [x, y] = que.shift();
2033
2034 for (let i = 0;i < dx.length && i < dy.length;i ++) {
2035 const tx = x + dx[i], ty = y + dy[i];
2036
2037 if (checker(tx, ty)) {
2038 if (paths[tx][ty] === -1) {
2039 paths[tx][ty] = paths[x][y] + 1;
2040 rounds[tx][ty] = [x, y];
2041 que.push([tx, ty]);
2042 }
2043
2044 if (paths[tx][ty] > paths[x][y] + 1) {
2045 paths[tx][ty] = paths[x][y] + 1;
2046 rounds[tx][ty] = [x, y];
2047 }
2048 }
2049 }
2050 }
2051
2052 return paths[n - 1][m - 1];
2053}
2054
2055console.log(shortestPath()); // true
20562.2 邻接矩阵
2057 基础数据结构与算法
20582.3 邻接表
2059 基础数据结构与算法
20607.2 广度优先遍历 bfs
2061 map: 二维空间, 需要从 (0, 0) 到 (n - 1,m - 1) 点，需要知道最短需要多少步数 （可以涵盖路径）
2062
2063
2064const map = [
2065 [0, 0, 0, 0, 0],
2066 [0, 0, 0, 1, 0],
2067 [1, 0, 0, 0, 0],
2068 [0, 0, 0, 1, 1],
2069 [0, 1, 0, 0, 0],
2070];
2071
2072function shortestPath(): number {
2073 const n = map.length, m = map[n - 1].length;
2074
2075 const paths: number[][] = new Array(map.length);
2076
2077 for (let i = 0; i < map.length; i ++) {
2078 paths[i] = new Array(map[i].length);
2079 paths[i].fill(-1); // -1 表示不可达
2080 }
2081
2082 const dx = [0, 1, -1, 0], dy = [1, 0, 0, -1];
2083 function checker(x: number, y: number): boolean {
2084 if (x < 0 || x >= n || y < 0 || y >= m) return false;
2085 return map[x][y] !== 1;
2086 }
2087
2088 const que: [number, number][] = [];
2089
2090 if (map[0][0] === 0) {
2091 que.push([0, 0]);
2092 paths[0][0] = 0;
2093 }
2094
2095 while (que.length !== 0) {
2096 const [x, y] = que.shift();
2097
2098 for (let i = 0;i < dx.length && i < dy.length;i ++) {
2099 const tx = x + dx[i], ty = y + dy[i];
2100
2101 if (checker(tx, ty)) {
2102 if (paths[tx][ty] === -1) {
2103 paths[tx][ty] = paths[x][y] + 1;
2104 que.push([tx, ty]);
2105 }
2106
2107 paths[tx][ty] = Math.min(paths[tx][ty], paths[x][y] + 1);
2108 }
2109 }
2110 }
2111
2112 return paths[n - 1][m - 1];
2113}
2114
2115console.log(shortestPath()); // true
21167.3 最短路
2117暂时无法在飞书文档外展示此内容
2118 采用图遍历（上述遍历方式遍历即可，在遍历到达终点的时候，同时记录最小值就行）
21197.3.1 djkstra
2120import { PriorityQueue } from '@rapid/libs';
2121// 优先级队列，需要自行实现，js 没有现成的。不然去找三方库也可以
2122
2123const inputs = [
2124 [1, 2, 3],
2125 [1, 4, 7],
2126 [2, 4, 3],
2127 [1, 3, 2],
2128 [3, 4, 2]
2129] as const;
2130
2131function solution() {
2132
2133 const n = 4;
2134 const maps: number[][] = new Array(n + 1).fill(0).map(() => new Array(n + 1).fill(0))
2135
2136 for (let i = 0;i < inputs.length;i ++) {
2137 const [x, y, v] = inputs[i];
2138 maps[x][y] = v;
2139 }
2140
2141 const paths: number[] = new Array(n + 1).fill(Infinity);
2142 const sure: boolean[] = new Array(n + 1).fill(false);
2143
2144 const que = new PriorityQueue<{ j: number;value: number; }>();
2145 que.setComparator((node1, node2) => {
2146 return node1.value - node2.value;
2147 })
2148
2149 paths[1] = 0;
2150 que.push({ j: 1, value: 0 });
2151
2152 while (!que.isEmpty()) {
2153 const top = que.pop();
2154 const { j, value } = top;
2155
2156 if (sure[j]) continue;
2157 sure[j] = true;
2158
2159 for (let y = 1;y <= n;y ++) {
2160 // 有路
2161 if (maps[j][y] !== 0) {
2162 const v = maps[j][y];
2163
2164 if (paths[j] + v < paths[y]) {
2165
2166 paths[y] = paths[j] + v;
2167
2168 que.push({ j: y, value: paths[y] });
2169 }
2170 }
2171 }
2172 }
2173
2174 console.log(paths[n]);
2175}
2176
2177solution();
2178
21798. 并查集
2180此类算法要和具体的问题结合理解。例如：找亲戚问题。
2181有一群人，a - b 是亲戚，b - c 是亲戚, 那么 a - c 就是亲戚。
2182那么给出一堆人的两两关系, 要求随机的查找 某两个人是否是亲戚。
2183暂时无法在飞书文档外展示此内容
2184// 亲戚关系表
2185const listOfRelatives: number[] = [];
2186// 表长度, 表索引
2187let index = 0;
2188
2189// 通过id标识查找这个人在 关系表中的下标位置
2190const idToIndexMap = new Map<string, number>();
2191
2192// 关系网,
2193const arr = [
2194 ['a', 'b', 'c'],
2195 ['c', 'g', 'f'],
2196 ['j', 'k'],
2197 ['l', 'm', 'p'],
2198 ['p', 'e'],
2199 ['e', 'j']
2200];
2201
2202function add(a: string) {
2203 if (idToIndexMap.has(a)) return idToIndexMap.get(a)!;
2204 idToIndexMap.set(a, index);
2205 listOfRelatives[index] = index;
2206 index ++;
2207 return index - 1;
2208}
2209
2210function find(index: number): number {
2211 if (listOfRelatives[index] !== index) listOfRelatives[index] = find(listOfRelatives[index]);
2212 return listOfRelatives[index];
2213}
2214
2215function findChar(char: string): number {
2216 const index = add(char);
2217 return find(index);
2218}
2219
2220function contain(a: string, b: string) {
2221 listOfRelatives[findChar(a)] = findChar(b);
2222}
2223
2224function init() {
2225 arr.forEach(list => {
2226 for (let i = 0;i < list.length - 1;i ++) {
2227 contain(list[i], list[i + 1]);
2228 }
2229 })
2230}
2231
2232init();
2233
2234console.log('find', findChar('a') === findChar('e'));
22359. 贪心
2236基础数据结构与算法dijkstra就是一个典型的贪心算法应用
223710. 动态规划
223810.1 01背包问题
2239 problem：https://www.acwing.com/problem/content/2/
2240 贪心是不能解决此类问题的。
2241 诸如：贪心解决此类问题的思路为，一直拿取性价比最高的物品，直到装不下。但是可能会出现，拿两个物品组合起来性价比堪比最高性价比的一个物品的情况，那么贪心就出问题了。
2242
2243 如何动态规划？动态规划也就是去找状态转移方程。
22444 5 // 总共有 4件物品，背包体积为 5
22451 2
22462 4
22473 4
22484 5
2249 1. 拿一件物品，那么当然就是有容量的才可以拿。第一件物品的容量 1，价值 2
2250物品 i/体积 j
22510
22521
22532
22543
22554
22565
22571
22580
22592
22602
22612
22622
22632
2264 如果 背包体积 > 物品体积，背包价值 = 物品价值
2265 如果 背包体积为 j < 物品体积, 那么背包价值 = 背包[i][j - 1] 的价值
2266 2. 拿第二件物品，此时背包里面可能已经放置了物品。此时需要取判断。第二件物品容量 2，价值 4
2267物品 i/体积 j
22680
22691
22702
22713
22724
22735
22741
22750
22762
22772
22782
22792
22802
22812
22820
22832
22844
22856
22866
22876
2288 在选择当前背包是否放入当前物品，需要考虑什么？ 该物品是否可以放得下，放下该物品价值是否更高？
2289 该物品是否可以放得下：j >= 物品体积 保证可以放，否则放不下那就只能是背包 [i - 1][j] 的价值 (上一次迭代的价值)
2290 放下该物品价值是否更高：max(原本的背包价值, 放下该物品的后背包的价值)
2291 max(背包[i - 1][j], 背包[i - 1][j - 物品体积] + 物品价值) , 第二项为 在背包能够容纳当前物品时的最大价值加上当前物品的价值
2292 获得最大值后，就是该物品的最大价值。
2293 3. 拿第三/四件物品，第三件容量为 3，价值为 4
2294物品 i/体积 j
22950
22961
22972
22983
22994
23005
23011
23020
23032
23042
23052
23062
23072
23082
23090
23102
23114
23126
23136
23146
23153
23160
23172
23184
23196
23206
23218
23224
23230
23242
23254
23266
23276
23288
2329 所以最大价值就是 8.
2330 按照逻辑推理, 设定 f[N][M] 为背包，v[N] 为物品体积，w[N] 为物品价值
2331 即状态转移方程：
2332 f[i][j] = f[i - 1][j]
2333 f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i])
2334 二维数组
2335#include <bits/stdc++.h>
2336
2337using namespace std;
2338
2339const int N = 1010;
2340
2341int v[N], w[N];
2342int f[N][N];
2343
2344int main() {
2345 int n, m;
2346 cin >> n >> m;
2347
2348 for (int i = 1;i <= n;i ++) cin >> v[i] >> w[i];
2349
2350 for (int i = 1;i <= n;i ++) {
2351 for (int j = 1;j <= m;j ++) {
2352
2353 if (j >= v[i]) {
2354 f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
2355 }
2356 else {
2357 f[i][j] = f[i - 1][j];
2358 }
2359
2360 }
2361 }
2362
2363 cout << f[n][m] << endl;
2364 return 0;
2365}
2366
2367 上面的解决用到了二维数组，但是在推导过程中不难发现：当背包体积为 j 的时候，f[i][j] 的状态推导与 f[i][j - 1], f[i][j - 2], f[i][j - 3]....无关，如果只用一个一维数组，每次拿物品重复迭代这个数组，那么也是可以的。
2368
2369 j的方向需要逆序，因为如果正序迭代背包，那么后面的元素会被前面的影响。
2370
2371 一维数组版本 (滚动数组
2372#include <bits/stdc++.h>
2373
2374using namespace std;
2375
2376const int N = 1010;
2377
2378int v[N], w[N];
2379int f[N];
2380
2381int main() {
2382 int n, m;
2383 cin >> n >> m;
2384
2385 for (int i = 1;i <= n;i ++) cin >> v[i] >> w[i];
2386
2387 for (int i = 1;i <= n;i ++) {
2388 for (int j = m;j >= v[i];j --) {
2389 f[j] = max(f[j], f[j - v[i]] + w[i]);
2390 }
2391 }
2392
2393 cout << f[m] << endl;
2394 return 0;
2395}
239610.2 完全背包问题
2397 与 01 背包问题一致，也就是物品可以无限使用，那么就在放置物品的时候，判断是否可以多次放置该物品即可。然后一次性放置尽可能多的物品，但是状态转移方程基本一致。
2398 K 为放置同一件物品 k 次
2399 f[i][j] = f[i - 1][j]
2400 f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i] * k] + w[i] * k)
240110.3 多重背包问题
240210.3.1 数据量小
2403 对于物品有具体的数量，那么可以把同一种物品看作是多个物品。
2404 例如：1号物品 体积 2，价值 3，数量 3
2405 那么可以放置 3 次一号物品作为不同的物品进行 01背包问题处理。
240610.3.2 数据量大
2407 如果数据量大，利用将多重背包化解为 01 背包问题求解时，可能会导致超时情况出现。那么需要优化。
2408 其根本思路不变，但是进行化解的时候需要进行特定处理。
2409 例如：
2410 3 个物品，我们可以纳入 2 个物品和 1 个物品
2411 7 个物品，我们可以纳入 4 个物品和 2 个物品和 1个物品
2412 6 个物品，我们可以纳入 3 个物品和 2 个物品和1个物品
2413 为什么这么做？为什么这样划分：
2414 因为把 7 划分为 4，2，1
2415 可以利用 4，2，1组合出 1~7 中的所有数字。
2416 1，
2417 2，
2418 3：2 + 1，
2419 4，
2420 5：4 + 1，
2421 6：4 + 2，
2422 7：4 + 2 + 1
2423
2424 为什么？？那么去分析这个数的二进制：7 => 111
2425 我们把 111 分成了 100, 10, 1 显而易见可以组合出自己想要的任何数字。
2426 6 => 110 => 11,10,1此页上