前言
树的广度优先遍历(Breadth-First Search, BFS)是一种用于遍历或搜索树数据结构的算法。
在广度优先遍历中,从根节点开始,按层级顺序逐层访问节点,先访问当前层级的所有节点,然后再访问下一层级的节点。
js代码实现
1 | function bfs(root) { |
go代码实现
1 | package main |
树的广度优先遍历(Breadth-First Search, BFS)是一种用于遍历或搜索树数据结构的算法。
在广度优先遍历中,从根节点开始,按层级顺序逐层访问节点,先访问当前层级的所有节点,然后再访问下一层级的节点。
1 | function bfs(root) { |
1 | package main |
树的深度优先遍历(Depth-First Search, DFS)是一种用于遍历或搜索树数据结构的算法。
在深度优先遍历中,从根节点开始,先访问当前节点,然后递归地访问其子节点,直到到达叶子节点。
然后回溯到上一级节点,继续访问其未被访问的子节点。
1 | const tree = { |
1 | package main |
余弦相似度是一种衡量两个向量之间相似性的度量方法。在向量空间中,给定两个非零向量A和B,它们的余弦相似度定义为它们的内积除以它们的模的乘积。用公式表示为:
cosine_similarity = (A · B) / (||A|| * ||B||)
其中,A · B表示向量A和B的内积,||A||和||B||分别表示向量A和B的模(长度)。
余弦相似度的取值范围在-1到1之间,值越接近1表示两个向量越相似,值越接近-1表示两个向量越不相似,值为0表示两个向量正交(没有相似性)。
在计算机科学和自然语言处理等领域,余弦相似度常用于文本相似度计算、推荐系统、聚类分析等任务
1 | // 计算向量的内积 |
图的深度优先遍历(Depth-First Search,DFS))是一种用于遍历图中所有节点的算法。它从图中的一个起始节点开始,沿着路径尽可能深地访问图中的节点,直到无法继续前进。然后回溯到上一个节点,继续探索其他未访问的节点,直到所有节点都被访问过为止。
1 | // 示例图的邻接表 |
1 | package main |
贪心算法(Greedy Algorithm)是一种常用的优化算法,它在每一步选择中都采取当前状态下最优的选择,以期望达到全局最优解。
假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。
对每个孩子 i,都有一个胃口值 g[i],这是能让孩子们满足胃口的饼干的最小尺寸;并且每块饼干 j,都有一个尺寸 s[j] 。如果 s[j] >= g[i],我们可以将这个饼干 j 分配给孩子 i ,这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子,并输出这个最大数值。
局部最优:既能满足孩子,还消耗最少。
1 | function findContentChildren(g,s) { |
go代码演示:
1 | package main |
假设你是一个贪婪的小偷,背着可装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 | // 吉他15磅 电脑20磅 音响30磅 |
go代码实现:
1 | package main |
学习动态规划之前,我们先来了解一下斐波那契数列。通过解决这个问题,慢慢我们就学会了动态规划的思想。
斐波那契数列是一个经典的数学问题,它的定义是:前两个数字是 0 和 1,之后的每个数字都是前两个数字之和。
因此,斐波那契数列的前几个数字依次是:0、1、1、2、3、5、8、13、21、34,以此类推。
这里就涉及到状态转移了,对于数组,从它的第3项开始满足,f(2) = f(n-1) + f(n - 2)。
可以通过暴力法递归实现相关代码:
1 | function fib(n) { |
这个方法的性能很差,因为它存在许多重复的递归,它的时间复杂度为O(2^n)。为了减少这些重复计算,需要对计算结果进行缓存。
记忆化搜素与暴力法相比,就是多了一个缓存体,记录了子问题的计算结果。我们整个分解问题,成为一个个的子问题。然后找到计算过的子问题的结果进行汇总,最后得到了整个问题的答案。
通常我们使用hash缓存结果,在javascript中对象就是一种hash结构。我们利用javascript的对象来缓存计算的结果,示例如下:
1 | function fib(n) { |
记忆化搜索的效率已经和动态规划一样了。实际上这种解法和动态规划的思想已经差不多了。只不过记忆化搜索是自顶向下(从结果往子问题推导),动态规划是自底向上(从子问题往结果推导)。
动态规划(Dynamic Programming,简称dp)是一种解决多阶段决策问题的数学算法。它通过将复杂问题分解为更简单的子问题,并利用子问题的解来构建原问题的解。
动态规划通常适用于具有重叠子问题和最优子结构性质的问题。其中,重叠子问题表示在解决问题的过程中会多次遇到相同的子问题,而最优子结构表示问题的最优解可以由其子问题的最优解构成。
动态规划的基本思想是将原问题分解为若干个子问题,并按照一定的顺序求解子问题,将子问题的解保存下来,避免重复计算。最终,通过求解子问题得到原问题的解。
在使用动态规划时,一般采用自底向上的方式进行计算。即从最小的子问题开始解决,逐步构建出更大规模的子问题的解,直至解决整个原问题。
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
这个问题其实和斐波那契数列类似,它的状态转移方式是一样的,f(n) = f(n - 1) + f(n -2)。
但是它的初始状态有所不同,f(0) = 1,f(1) = 1。
下面用javascript代码实现一下:
1 | function climbStairs(n) { |
我们可以使用滚动数组思想把空间复杂度优化成O(1)。
1 | function climbStairs2(n) { |
go代码实现
1 | func climbStairs(n int) int { |
迪科斯特拉(Dijkstra)是一种用于解决图中最短路径问题的算法,由计算机科学家艾兹赫尔·迪科斯特拉(Edsger W. Dijkstra)在1956年发明并提出。迪科斯特拉算法可以找到从一个起始顶点到其他所有顶点的最短路径。
迪科斯特拉算法可以应用于带有非负权重的有向图或无向图中。在包含负权边的图中,要找出最短路径,可使用贝尔曼-福特(Bellman-Ford)算法。
基本思想是通过遍历图中的节点来逐步确定起始节点到其他节点的最短路径长度,并记录下最短路径。算法使用了一种贪心的策略,每次选择当前距离起始节点路径长度最短的节点进行扩展。通过不断更新节点的最短路径和最短路径长度,最终得到起始节点到其他节点的最短路径和长度。
具体的算法步骤如下:
为了找到最短路径的具体移动路径,需要一个存储当前节点对应的上个节点的 parents 散列表,找到最短路径后进行回溯。
1 | function dijkstra(graph,startNode) { |
go代码演示,大体思路一致,不过代码使用了邻接矩阵表示图,使用数组记录信息。我相信通过不同的语言和方式来实现同一套算法,更能加深我们的理解
1 | package main |
nestjs是一个功能强大的node框架。其中有很多编程概念,例如:依赖注入(DI)系统、面向切面编程(AOP)支持。本文将带大家了解 IOC 与 DI 的概念。
控制反转(英语:Inversion of Control,缩写为IoC),是面向对象编程中的一种设计原则,可以用来减低计算机代码之间的耦合度。
其中最常见的方式叫做依赖注入(Dependency Injection,简称DI)。
现在我们有一个简单的需求,我们有多个类,需要一个方法,可以获取某个类的实例,从而访问改类内部的方法。
比如,我们需要实现下面这段代码的:
1 | class A { |
我们在上面的例子里看到了 Container 类,首先我们先得知道 Container 需要做什么。
我们觉得它需要分析 A 这个类的属性中依赖了哪些东西,我们一眼就能看出 A 依赖了 B,而 B 依赖了 C,但是程序呢?
为了简化一下,这个地方需要有一个假设,假如我们的属性都是标准的类好了,现在就简单了。
1 | class Container { |
我们使用递归的方式不断的get某一个类的实例,如果对象不存在,则不断的进行创建
现在我们只有3个类,核心功能很快就完成了,下一步我们来想想怎么优化
如果有另一个类,包裹了其他的几个实例怎么办呢。
1 | class A { |
按照我们的核心代码,估计会创建出好几个B实例和C实例。
那么,开始优化吧,我们先加个缓存吧。
1 | class Container { |