白筱汐

想都是问题,做都是答案

0%

前言

树的广度优先遍历(Breadth-First Search, BFS)是一种用于遍历或搜索树数据结构的算法。
在广度优先遍历中,从根节点开始,按层级顺序逐层访问节点,先访问当前层级的所有节点,然后再访问下一层级的节点。

js代码实现

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
function bfs(root) {
let queue = [root];
while (queue.length) {
let node = queue.shift();
console.log(node.val);
if (node.children) {
node.children.forEach(child => {
queue.push(child);
})
}
}
}

const tree = {
val: 'a',
children: [
{
val: 'b',
children: [
{
val: 'd'
},
{
val: 'e'
}
]
},
{
val: 'c',
children: [
{
val: 'f'
},
{
val: 'g'
}
]
}
]
}

bfs(tree); // a b c d e f g

go代码实现

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
package main

import "fmt"

type Node struct {
Val string
Child []*Node
}

func newNode(val string) *Node {
return &Node{
Val: val,
Child: make([]*Node, 0),
}
}

func (n *Node) AddChild(children ...*Node) {
n.Child = append(n.Child, children...)
}

func Bfs(root *Node) {
queue := make([]*Node, 0)
queue = append(queue, root)
for len(queue) > 0 {
node := queue[0]
queue = queue[1:]
fmt.Println(node.Val)
if len(node.Child) > 0 {
for _, child := range node.Child {
queue = append(queue, child)
}
}
}
}

func main() {
a := newNode("a")
b := newNode("b")
c := newNode("c")
d := newNode("d")
e := newNode("e")
f := newNode("f")
g := newNode("g")
a.AddChild(b, c)
b.AddChild(d, e)
c.AddChild(f, g)

Bfs(a) // a b c d e f g
}

前言

树的深度优先遍历(Depth-First Search, DFS)是一种用于遍历或搜索树数据结构的算法。
在深度优先遍历中,从根节点开始,先访问当前节点,然后递归地访问其子节点,直到到达叶子节点。
然后回溯到上一级节点,继续访问其未被访问的子节点。

js代码实现

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
const tree = {
val: 'a',
children: [
{
val: 'b',
children: [
{
val: 'd'
},
{
val: 'e'
}
]
},
{
val: 'c',
children: [
{
val: 'f'
},
{
val: 'g'
}
]
}
]
}

// 递归实现
function dfs(root) {
console.log(root.val);
if (root.children) {
root.children.forEach(child => {
dfs(child);
})
}
}

// 栈实现
function dfsStack(root) {
let stack = [root];
while (stack.length > 0) {
let node = stack.pop();
console.log(node.val);
if (node.children) {
const children = node.children;
// 为了保证和递归的访问顺序一致,反向遍历
for (let i = children.length - 1; i >= 0; i--) {
stack.push(children[i]);
}
}
}
}

go代码实现

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
package main

import "fmt"

type Node struct {
Val string
Child []*Node
}

func newNode(val string) *Node {
return &Node{
Val: val,
Child: make([]*Node, 0),
}
}

func (n *Node) AddChild(children ...*Node) {
n.Child = append(n.Child, children...)
}

func Dfs(root *Node) {
fmt.Println(root.Val)
if len(root.Child) > 0 {
for _, child := range root.Child {
Dfs(child)
}
}
}

func DfsStack(root *Node) {
stack := make([]*Node, 0)
stack = append(stack, root)
for len(stack) > 0 {
node := stack[len(stack)-1]
stack = stack[:len(stack)-1]
fmt.Println(node.Val)
if len(node.Child) > 0 {
for i := len(node.Child) - 1; i >= 0; i-- {
stack = append(stack, node.Child[i])
}
}
}
}

func main() {
a := newNode("a")
b := newNode("b")
c := newNode("c")
d := newNode("d")
e := newNode("e")
f := newNode("f")
g := newNode("g")
a.AddChild(b, c)
b.AddChild(d, e)
c.AddChild(f, g)

Dfs(a) // a b d e c f g

fmt.Println("--------------")

DfsStack(a) // a b d e c f g
}

前言

余弦相似度是一种衡量两个向量之间相似性的度量方法。在向量空间中,给定两个非零向量A和B,它们的余弦相似度定义为它们的内积除以它们的模的乘积。用公式表示为:
cosine_similarity = (A · B) / (||A|| * ||B||)
其中,A · B表示向量A和B的内积,||A||和||B||分别表示向量A和B的模(长度)。
余弦相似度的取值范围在-1到1之间,值越接近1表示两个向量越相似,值越接近-1表示两个向量越不相似,值为0表示两个向量正交(没有相似性)。
在计算机科学和自然语言处理等领域,余弦相似度常用于文本相似度计算、推荐系统、聚类分析等任务

js代码实现

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
// 计算向量的内积
// A · B = a1 * b1 + a2 * b2 + ... + an * bn
function dotProduct(vector1, vector2) {
let result = 0;
for (let i = 0; i < vector1.length; i++) {
result += vector1[i] * vector2[i];
}
return result;
}

// 计算向量的模
// ||V|| = sqrt(v1^2 + v2^2 + ... + vn^2)
function vectorNorm(vector) {
let squaredSum = 0;
for (let i = 0; i < vector.length; i++) {
squaredSum += vector[i] * vector[i];
}
return Math.sqrt(squaredSum);
}

// 计算余弦相似度
function cosineSimilarity(vector1, vector2) {
const dot = dotProduct(vector1, vector2);
const norm1 = vectorNorm(vector1);
const norm2 = vectorNorm(vector2);

const similarity = (norm1 !== 0 && norm2 !== 0) ? dot / (norm1 * norm2) : 0;
return similarity;
}

// 示例向量
const vectorA = [1, 2, 3];
const vectorB = [4, 5, 6];

// 计算余弦相似度
const similarity = cosineSimilarity(vectorA, vectorB);

console.log("余弦相似度:", similarity);

前言

图的深度优先遍历(Depth-First Search,DFS))是一种用于遍历图中所有节点的算法。它从图中的一个起始节点开始,沿着路径尽可能深地访问图中的节点,直到无法继续前进。然后回溯到上一个节点,继续探索其他未访问的节点,直到所有节点都被访问过为止。

js代码实现

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
// 示例图的邻接表
const graph = {
1: [2, 3],
2: [4, 5],
3: [6, 7],
4: [8],
5: [9],
6: [10],
};

// 递归实现
const visited = new Set();

function dfs(n) {
console.log(n)
visited.add(n)

const neighbors = graph[n];
if (neighbors) {
for (let i = 0; i < neighbors.length; i++) {
if (!visited.has(neighbors[i])) {
dfs(neighbors[i])
}
}
}
}

// 栈实现
function dfs2(start) {
const stack = [start]
const visited = new Set()
while (stack.length) {
const n = stack.pop()
console.log(n)
visited.add(n)

const neighbors = graph[n]
if (neighbors) {
for (let i = neighbors.length - 1; i >= 0; i--) {
if (!visited.has(neighbors[i])) {
stack.push(neighbors[i])
}
}
}
}
}

go代码实现

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
package main

import "fmt"

// 图的深度优先遍历(Depth-First Search,DFS)

// 递归
func dfs(n int, visited map[int]bool) {
visited[n] = true
fmt.Println(n)
for _, c := range graph[n] {
if !visited[c] {
dfs(c, visited)
}
}
}

// 栈
func dfs2(n int) {
visited := make(map[int]bool)
stack := []int{n}
for len(stack) > 0 {
n := stack[len(stack)-1]
stack = stack[:len(stack)-1]
visited[n] = true
fmt.Println(n)

neighbors := graph[n]
for i := len(neighbors) - 1; i >= 0; i-- {
if !visited[neighbors[i]] {
stack = append(stack, neighbors[i])
}
}
}
}

// 定义图的邻接表表示
var graph = map[int][]int{
1: {2, 3},
2: {4, 5},
3: {6, 7},
4: {8},
5: {9},
6: {10},
}

func main() {
visited := make(map[int]bool)
dfs(1, visited) // 1 2 4 8 5 9 3 6 10 7

fmt.Println("======")
dfs2(1) // 1 2 4 8 5 9 3 6 10 7
}

前言

贪心算法(Greedy Algorithm)是一种常用的优化算法,它在每一步选择中都采取当前状态下最优的选择,以期望达到全局最优解。

分发饼干

leetcode-455 简单

假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。

对每个孩子 i,都有一个胃口值 g[i],这是能让孩子们满足胃口的饼干的最小尺寸;并且每块饼干 j,都有一个尺寸 s[j] 。如果 s[j] >= g[i],我们可以将这个饼干 j 分配给孩子 i ,这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子,并输出这个最大数值。

局部最优:既能满足孩子,还消耗最少。

  1. 对饼干数组和胃口数组升序排序。
  2. 遍历饼干数组,找到能满足第一个孩子的饼干。
  3. 然后继续遍历饼干数组,找到满足第二、三、……、n个孩子的饼干。
1
2
3
4
5
6
7
8
9
10
11
12
13
function findContentChildren(g,s) {
// 升序排序
const sort = (a,b) => a - b;
g.sort(sort);
s.sort(sort);
let i = 0;
s.forEach(n => {
if (n >= g[i]) {
i++;
}
})
return i
}

go代码演示:

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
package main

import (
"fmt"
"sort"
)

// 分饼干
func findContentChildren(g, s []int) int {
sort.Ints(g)
sort.Ints(s)
i := 0
for n := range s {
if n >= g[i] {
i++
}
}
return i
}

func main() {
g := []int{1, 2}
s := []int{1, 1, 3}

n := findContentChildren(g, s)
fmt.Println(n)
}

经典背包问题

假设你是一个贪婪的小偷,背着可装35磅重的背包,在商场伺机盗窃各种可装入背包的商品。吉他-1500$-15磅 笔记本电脑-2000$-20磅 音响-3000$-30磅。怎么选择商品,才能利益最大化呢?

如果使用贪心算法,每一步都选择最优解,第一次就偷了30磅的音响。虽然第一个操作是最优解,但是从全局来看,我们浪费了5磅的重量,因为没有小于等于5磅重量的商品可以偷了。

此时我们偷盗了价值3000$的商品,显然这不是利益最大化的选择。因为问题比较简单,我们很容易得出结果,偷取吉他和笔记本电脑是最优选择,可以偷到总价值3500$的商品。

我们需要使用动态规划(不懂的可以查看我写的爬楼梯问题文章),先解决子问题,再解决原来的问题。

我们需要建立一个二位数组dp网格。每一行描述当前商品,每一列描述当前可装重量。初始化所有单元格的值都为0,对于 i >= 1 && j >= 1 的每个单元格dp[i][j]都使用相同的计算公式:

dp[i][j] = Math.max(dp[i-1][j],dp[i - 1][j - weight[i - 1]] + value[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
// 吉他15磅 电脑20磅 音响30磅
const weight = [15,20,30]
// 吉他1500$ 电脑2000$ 音响3000$
const values = [1500,2000,3000]
const totalWeight = 35 // 总重量35磅

function maxValue(weight, value, totalWeight) {
const n = weight.length // n为物品个数
// 创建一个二位数组来保存状态转移的结果
// 注意数组的下标从0开始,需要对比上个单元格的值,所以二维数组的行数量为 n + 1,列数量为 totalWeight + 1
const dp = new Array(n + 1).fill(0).map(() => new Array(totalWeight + 1).fill(0))

for (let i = 1; i <= n; i++) {
for (let j = 1; j <= totalWeight; j++) {
// 如果当前物品小于等于剩余空间
if (weight[i - 1] <= j) {
// 比较(上一个单元格的值)和(当前物品的重量 + 剩余空间的价值)两者中较大的那个
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i - 1]] + value[i - 1])
} else {
// 当前物品大于剩余空间
dp[i][j] = dp[i - 1][j]
}
}
}
return dp[n][totalWeight];
}

go代码实现:

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
package main

import "fmt"

func maxValue(weight []int, value []int, totalWeight int) int {
n := len(weight)
dp := make([][]int, n+1)
for i := range dp {
dp[i] = make([]int, totalWeight+1)
}
for i := 1; i <= n; i++ {
for j := 1; j <= totalWeight; j++ {
if weight[i-1] <= j {
// 比较(上一个单元格的值)和(当前物品的重量 + 剩余空间的价值)两者中较大的那个
dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i-1]]+value[i-1])
} else {
// 当前物品大于剩余空间
dp[i][j] = dp[i-1][j]
}
}
}
return dp[n][totalWeight]
}

// 比较函数 返回两者中的较大者
func max(a, b int) int {
if a > b {
return a
}
return b
}

func main() {
weight := []int{15, 20, 30}
value := []int{1500, 2000, 3000}
totalWeight := 35

total := maxValue(weight, value, totalWeight)
fmt.Println(total)
}

前言

学习动态规划之前,我们先来了解一下斐波那契数列。通过解决这个问题,慢慢我们就学会了动态规划的思想。

斐波那契数列

斐波那契数列是一个经典的数学问题,它的定义是:前两个数字是 0 和 1,之后的每个数字都是前两个数字之和。

因此,斐波那契数列的前几个数字依次是:0、1、1、2、3、5、8、13、21、34,以此类推。

这里就涉及到状态转移了,对于数组,从它的第3项开始满足,f(2) = f(n-1) + f(n - 2)。

暴力法

可以通过暴力法递归实现相关代码:

1
2
3
4
5
6
7
8
9
function fib(n) {
if (n === 0) {
return 0
} else if (n === 1) {
return 1
} else {
return fib(n - 1) + fib(n - 2)
}
}

这个方法的性能很差,因为它存在许多重复的递归,它的时间复杂度为O(2^n)。为了减少这些重复计算,需要对计算结果进行缓存。

记忆化搜素

记忆化搜素与暴力法相比,就是多了一个缓存体,记录了子问题的计算结果。我们整个分解问题,成为一个个的子问题。然后找到计算过的子问题的结果进行汇总,最后得到了整个问题的答案。

通常我们使用hash缓存结果,在javascript中对象就是一种hash结构。我们利用javascript的对象来缓存计算的结果,示例如下:

1
2
3
4
5
6
7
8
9
10
function fib(n) {
if (fib.cache[n]) {
return fib.cache[n]
}
return fib.cache[n] = fib(n - 1) + fib(n -2)
}
fib.cache = {
0:1,
1:1
}

记忆化搜索的效率已经和动态规划一样了。实际上这种解法和动态规划的思想已经差不多了。只不过记忆化搜索是自顶向下(从结果往子问题推导),动态规划是自底向上(从子问题往结果推导)。

动态规划

动态规划(Dynamic Programming,简称dp)是一种解决多阶段决策问题的数学算法。它通过将复杂问题分解为更简单的子问题,并利用子问题的解来构建原问题的解。

动态规划通常适用于具有重叠子问题和最优子结构性质的问题。其中,重叠子问题表示在解决问题的过程中会多次遇到相同的子问题,而最优子结构表示问题的最优解可以由其子问题的最优解构成。

动态规划的基本思想是将原问题分解为若干个子问题,并按照一定的顺序求解子问题,将子问题的解保存下来,避免重复计算。最终,通过求解子问题得到原问题的解。

在使用动态规划时,一般采用自底向上的方式进行计算。即从最小的子问题开始解决,逐步构建出更大规模的子问题的解,直至解决整个原问题。

基本步骤

  1. 设计状态
  2. 确定状态转移方程
  3. 确定初始状态
  4. 执行状态转移
  5. 计算最终的解

爬楼梯

leetcode-70 简单

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?

这个问题其实和斐波那契数列类似,它的状态转移方式是一样的,f(n) = f(n - 1) + f(n -2)。

但是它的初始状态有所不同,f(0) = 1,f(1) = 1。

下面用javascript代码实现一下:

1
2
3
4
5
6
7
8
function climbStairs(n) {
if (n < 2) return 1
const dp = [1,1]
for (let i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i -2]
}
return dp[n]
}

我们可以使用滚动数组思想把空间复杂度优化成O(1)。

1
2
3
4
5
6
7
8
9
10
11
function climbStairs2(n) {
if (n < 2) return 1
let p = 1,q = 1
for (let i = 2; i <= n; i++) {
// 通过一个临时变量来转移状态,优化空间复杂度
const temp = p
p = q
q = temp + q
}
return q
}

go代码实现

1
2
3
4
5
6
7
8
9
10
func climbStairs(n int) int {
if n < 2 {
return 1
}
p, q := 1, 1
for i := 2; i <= n; i++ {
p, q = q, p+q
}
return q
}

前言

迪科斯特拉(Dijkstra)是一种用于解决图中最短路径问题的算法,由计算机科学家艾兹赫尔·迪科斯特拉(Edsger W. Dijkstra)在1956年发明并提出。迪科斯特拉算法可以找到从一个起始顶点到其他所有顶点的最短路径。

迪科斯特拉算法可以应用于带有非负权重的有向图或无向图中。在包含负权边的图中,要找出最短路径,可使用贝尔曼-福特(Bellman-Ford)算法

基本思想是通过遍历图中的节点来逐步确定起始节点到其他节点的最短路径长度,并记录下最短路径。算法使用了一种贪心的策略,每次选择当前距离起始节点路径长度最短的节点进行扩展。通过不断更新节点的最短路径和最短路径长度,最终得到起始节点到其他节点的最短路径和长度。

具体的算法步骤如下:

  1. 初始化:将起始节点的最短路径长度设为0,其他节点的最短路径长度设为正无穷大。
  2. 选择当前最短路径长度最小的节点,并标记为已访问。
  3. 更新与该节点相邻节点的最短路径长度:如果经过当前节点到达相邻节点的路径比已记录的最短路径更短,则更新最短路径长度。
  4. 重复步骤2和步骤3,直到所有节点都被访问过或者不存在从起始节点到未访问的节点的路径。

为了找到最短路径的具体移动路径,需要一个存储当前节点对应的上个节点的 parents 散列表,找到最短路径后进行回溯

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
function dijkstra(graph,startNode) {
const visited = new Set() // 保存访问过的节点
const distance = {} // 记录起始节点到各个节点的最短距离
const parents = {} // 记录每个节点对应的前一个节点

// 初始化起始节点到其他节点的距离为正无穷大
for (const node in graph) {
distance[node] = Infinity
}

// 起始节点到自身的距离为0
distance[startNode] = 0

// 遍历所有节点
while(visited.size < Object.keys(graph).length) {
let minDistance = Infinity
let closestNode = null;
// 选择当前距离最小且未被访问过的节点
for (const node in distance) {
if (!visited.has(node) && distance[node] < minDistance) {
minDistance = distance[node]
closestNode = node
}
}

// 标记选择的节点为已访问
visited.add(closestNode);

// 更新与选择节点相邻节点的最短距离和前驱节点
for (const neighbor in graph[closestNode]) {
const weight = graph[closestNode][neighbor];
const newDistance = distance[closestNode] + weight;
if (newDistance < distance[neighbor]) {
distance[neighbor] = newDistance;
parents[neighbor] = closestNode;
}
}
}

return { distance, parents }
}

// 回溯最短路径
function shortestPaths(parents,startNode,endNode) {
const path = [endNode];
let currentNode = endNode;

// 从终点往前遍历最短路径
while (currentNode !== startNode) {
currentNode = parents[currentNode];
path.unshift(currentNode); // 在数组开头添加节点
}

return path;
}


// 示例数据
const graph = {
A: { B: 5, C: 2 },
B: { A: 5, C: 2, D: 3 },
C: { A: 2, B: 2, D: 1 },
D: { B: 3, C: 1 },
};

const startNode = 'A';
const endNode = 'D';

const { distance, parents } = dijkstra(graph, startNode);
console.log(distance)
console.log(shortestPaths(parents, startNode,endNode));

go代码演示,大体思路一致,不过代码使用了邻接矩阵表示图,使用数组记录信息。我相信通过不同的语言和方式来实现同一套算法,更能加深我们的理解

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
package main

import (
"fmt"
"math"
)

const INF = math.MaxInt32 // 正无穷大,表示两个节点之间没有直接连接的边

func dijkstra(graph [][]int, start, end int) ([]int, []int) {
numVertices := len(graph) // 顶点的数量
distances := make([]int, numVertices) // 记录起点到每个节点的最短距离
visited := make([]bool, numVertices) // 记录每个节点是否被访问
parents := make([]int, numVertices) // 记录最短路径上的每个节点的父节点

// 初始化起点到其他节点的距离为正无穷大
// 所有节点的上一个节点是顶点
for i := range distances {
distances[i] = INF
parents[i] = -1
}
// 起始节点到自身的距离为0
distances[start] = 0

// 重复执行直到找到目标节点或所有节点都被访问过
for !visited[end] {
// 找到距离起点最近的并且未被访问过的节点
min := INF
minIndex := -1
for v := 0; v < numVertices; v++ {
if !visited[v] && distances[v] <= min {
min = distances[v]
minIndex = v
}
}
if minIndex == -1 {
break
}
// 将最近的节点设置为已访问
visited[minIndex] = true
for v := 0; v < numVertices; v++ {
// 更新与选择节点相邻节点的最短距离和前驱节点
if !visited[v] && graph[minIndex][v] != INF && distances[minIndex]+graph[minIndex][v] < distances[v] {
distances[v] = distances[minIndex] + graph[minIndex][v]
parents[v] = minIndex
}
}
}
// 回溯最短路径
path := make([]int, 0)
node := end // 终点
for node != -1 {
path = append(path, node)
node = parents[node]
}

// 反转数组
i, j := 0, len(path)-1
for i < j {
path[i], path[j] = path[j], path[i]
i++
j--
}

return distances, path
}

func main() {
graph := [][]int{
// A -> B -> C ->D
{INF, 5, 2, INF}, // A
{5, INF, 2, 3}, // B
{2, 2, INF, 1}, // C
{INF, 3, 1, INF}, // D
}
start := 0
end := 3
distances, path := dijkstra(graph, start, end)
fmt.Println("distances:", distances)
fmt.Println("parents:", path)
}

前言

nestjs是一个功能强大的node框架。其中有很多编程概念,例如:依赖注入(DI)系统、面向切面编程(AOP)支持。本文将带大家了解 IOC 与 DI 的概念。

IOC 与 DI

控制反转(英语:Inversion of Control,缩写为IoC),是面向对象编程中的一种设计原则,可以用来减低计算机代码之间的耦合度。
其中最常见的方式叫做依赖注入(Dependency Injection,简称DI)。

现在我们有一个简单的需求,我们有多个类,需要一个方法,可以获取某个类的实例,从而访问改类内部的方法。
比如,我们需要实现下面这段代码的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class A {
b: B;
}
class B {
c: C;
}
class C {
hello() {
console.log('hello world');
}
}

const container = new Container();
const a = container.get(A);
// a.b.c.hello() === 'hello world'

第一步

我们在上面的例子里看到了 Container 类,首先我们先得知道 Container 需要做什么。

我们觉得它需要分析 A 这个类的属性中依赖了哪些东西,我们一眼就能看出 A 依赖了 B,而 B 依赖了 C,但是程序呢?

为了简化一下,这个地方需要有一个假设,假如我们的属性都是标准的类好了,现在就简单了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Container {

get(Module) {
// 创建对象
const obj = new Module();
// 拿到属性
const properties = Object.getOwnPropertyNames(obj);
for(let p of properties) {
if (!obj[p]) {
// 如果对象不存在,就往下创建
if (p === 'b') {
obj[p] = this.get(B);
} else if (p === 'c') {
obj[p] = this.get(C);
} else {}
}
}
}
}

我们使用递归的方式不断的get某一个类的实例,如果对象不存在,则不断的进行创建

第二步

现在我们只有3个类,核心功能很快就完成了,下一步我们来想想怎么优化
如果有另一个类,包裹了其他的几个实例怎么办呢。

1
2
3
4
5
6
7
8
9
10
11
class A {
b: B;
d: D;
}
class B {
c: C;
}
class D {
b: B;
c: C;
}

按照我们的核心代码,估计会创建出好几个B实例和C实例。

那么,开始优化吧,我们先加个缓存吧。

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
class Container {

cachae = {};

getName(Module) {
return Module.Name.toLowerCase();
}

get(Module) {
// 弄个缓存
if (this.cachae[this.getName(Module)]) {
return this.cachae[this.getName(Module)];
}

// 创建对象
const obj = new Module();
// 缓存起来下次