franki Blog

make a small progress every day

数据结构-图-find a path

图的深度优先遍历通过 dfs 得到每个顶点经过的路径，然后通过遍历得到结果代码实现 class Path { constructor(g, s) { this.g = g; this.s = s; this.from = new Array(g.V()).fill(-1); this.visited = new Array(g.V()).fill...

Posted by franki on September 26, 2022

数据结构-图-dfs

图的深度优先遍历图的 dfs 跟树的 dfs 类似，都是从一个顶点一直遍历到不可遍历为止，通过 dfs 可以求出图的联通分量，每个顶点的联通分量代码实现 class DFSComponent { constructor(g) { this.g = g; this.visited = new Array(g.V()).fill(false); this....

Posted by franki on September 25, 2022

数据结构-图-read graph

读取一张图使用 nodejs 本身自带的文件读取模块 read-line 代码实现 const fs = require('fs'); const readline = require('readline'); // const DenseGraph = require('./dense-graph'); const SparseGraph = require('./sparse-g...

Posted by franki on September 24, 2022

数据结构-图-sparse graph

图论基础-稀疏图稀疏图实现过程定义一个 n * x 的数组，x 表示每一个顶点里面相连顶点的集合注意：稀疏图存在平行边，也就是 1 - 2 可能出现多次代码实现 // 稀疏图 class SparseGraph { constructor(n, directed) { this.n = n; // 表示顶点个数 this.m = 0; // 表示边的个数...

Posted by franki on September 23, 2022

数据结构-图-dense graph

图论基础-稠密图稠密图实现过程使用一个 n*n 的矩阵，一开始矩阵里面的元素都是 false 应用场景是：数据较多，场景复杂的图代码实现 // 稠密图 class DenseGraph { constructor(n, directed) { this.n = n; // 图的顶点数 this.m = 0; // 图的边数 this.directed ...

Posted by franki on September 22, 2022

数据结构-图-mind

图 - mind 从今天开始继续温习数据结构与算法，把之前对于图的部分进行代码实现，对于图的里面包括算法需要的数据结构进行融会贯通，争取对于运用到的数据结构理解更加透彻。图的分类及其使用

Posted by franki on September 21, 2022

leetcode 235题

leetcode 235题二叉搜索树的最近公共祖先给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。” 例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null...

Posted by franki on January 13, 2022

leetcode 234题

leetcode 234题回文链表给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。示例 1：输入：head = [1,2,2,1] 输出：true 示例 2：输入：head = [1,2] 输出：false 提示：链表中节点数目在范围[1, 105] 内 0 <= Node.val <...

Posted by franki on January 12, 2022

leetcode 232题

leetcode 232题 2 的幂请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：实现 MyQueue 类： void push(int x) 将元素 x 推到队列的末尾 int pop() 从队列的开头移除并返回元素 int peek() 返回队列开头的元素 boolean empty() 如果队列为空，返回 tr...

Posted by franki on January 11, 2022

leetcode 231题

leetcode 231题 2 的幂给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。如果存在一个整数 x 使得 n == 2x ，则认为 n 是 2 的幂次方示例 1：输入：n = 1 输出：true 解释：20 = 1 示例 2：输入：n = 16 输出：true 解释：24 = 16 示例 3：输入...

Posted by franki on January 11, 2022