- 博客(142)
- 资源 (9)
- 收藏
- 关注
RSS订阅原创 求二进制最低位1和最高位1的方法，以及反转二进制，复杂度O(1)
本文主要对三个二进制操作算法进行介绍，它们都是O(1)的。相对于暴力移位去计算，效率会高很多。这三个算法分别是 获取最低的1的比特位、获取最高1的比特位，反转二进制。
2023-10-29 22:20:45
1388
2
原创 最长公共子序列（LCS）与最长上升子序列（LIS）问题的相互转换
本文展示了如可把LCS问题转换为LIS问题，以及如何把LIS问题转换为LCS问题。在此只做直观理解，不做严格证明。同时对这两个问题给出了对应的解法。最后以一个leetcode题目作为LIS问题的应用。
2023-10-28 11:48:57
259
原创 KMPBC：KMP算法及其改进（kmp with bad character）
最近在看字符串匹配算法，突然灵光一闪有了想法，可以把kmp算法时间效率提高，同时保持最坏时间复杂度O(n+m)不变。其中n为主串长度，m为模式串长度，经测试可以块3-10倍，以为发现了新大陆，但是查阅文献后发现已经有了类似了改进。所以发表在CSDN上就算成功！
2023-08-17 17:03:44
196
原创 KMP算法浅浅实现
不用多说，KMP算法老经典了。秋招笔试很爱考，没办法，为了饭碗，学它！可以参考这位up主的教程：最浅显易懂的 KMP 算法讲解。
2023-08-16 23:55:51
85
原创 更快的求最近公共祖先（LCA）的算法-倍增法求LCA
假定要求x和y两个结点的最近公共祖先，那么通过fa快速把x,y调整到一样的高度。首先，通过树的深度优先遍历，计算fa和dep数组。查找：从上到下调平以从下到上找第一个共公祖先，最多。个父节点，因此时间复杂度为。预处理：每个节点至多有。次，因此时间复杂度为。
2023-08-16 22:40:46
139
原创 多路归并的实现，以leecode题目为例
假设有k个有序链表（以递增为例）需要进行归并成一个有序链表，总结点个数为nnn。基本思想是使用一个优先队列（小顶堆），首先k个有序链表链表的第一个结点放入队列中，每次从优先队列中取出最小的结点即可。每取一个结点就从原来的链表中补充一个结点到队列中。
2023-07-29 20:40:42
174
原创 块状链表实现BigString大字符串操作（golang）
块状链表是介于链表和数组之间的数据结构，能够在On时间内完成插入、删除、访问操作。数据结构如图所示。假设最大容量为n, 则它有一个长度为sn的链表。链表中每个结点是一个长度为2×n的数组。实现时，有两个细节需要注意：初始时，只有一个链表结点。随着数据越来越多，当某个结点内数组装满后，将分裂成两个结点。删除数据后，如果数据所在结点为空，则需要删除结点（链表首元结点不用删除）。本文以BigString为例进行实现。
2023-05-05 15:48:37
677
原创 分块思想（Sqrt Decomposition）的实现（golang）
Sqrt Decomposition 是一种数据结构，能够在O(1)时间复杂度内完成数组元素值的查询和更新，在On时间复杂度内完成的查询和批量更新某个区间的值。这里的属性可以是区间的和、最小值、最大值等。说到区间的和，你可能会想到前缀和，能够在O(1)时间复杂度内查询区间的和，明显比本文要说的Sqrt Decomposition 更快。但是它不支持数据的更新，因为更新后需要重新计算前缀和。Sqrt Decomposition 来自于分块思想的启发，把数组分成若干的长度相等的区块（最后一块除外）
2023-05-04 15:51:12
427
原创 一种具有O(1)复杂度的LFU算法实现（java 实现）
当缓存不足时，将优先淘汰访问频次最小的。可以从head开始查找，将找到的第一个从链表中删除即可。即会把a删除，删除后如图。此时聪明的你应该想到如何实现了！下面以一个例子说明其原理。当加入值时，都默认放在这个频次为0的链表中。比如添加a, b, c后。当获取值时，会把它的频次加1，以b为例，即会把b移动到一个新的链表。最近在做一些数据缓存方面的工作。研究了LRU算法和LFU算法。无论是加入、获取、淘汰，操作的复杂度都是O(1)的。
2023-03-17 15:48:36
519
原创 数据分析之数据相关性分析
本文介绍相关性分析的方法和工具。从三个常用相关系数（pearson,spearman,kendall）的定义出发，说明相关性分析的原理和作用。
2023-01-07 14:51:33
2818
原创 左倾红黑树的go语言实现
红黑树经常能在计算机底层代码中见到，比如C++的map，multimap, set, multisetLinux中rdtree用以管理内存和进程Java中的HashMap左倾红黑树是对红黑树的一种改进，在保持红黑树的优良性能情况下使得实现更加的容易。本文解释其原理并使用GO语言对它进行了实现。无论左倾红黑树还是红黑树都是对它们的原型2-3-4树的一种实现。2-3-4树有一个非常好的性质：树上所有从根结点到叶子结点的路径都是等长的。这意味着查找、插入、删除这三种操作时间复杂度都是O(l。
2022-10-22 14:19:24
404
原创 堆排序（简单版和通行版本）
通行版：初始时是一个不符合定义的堆，从最后一个非叶结点开始调整堆。计算量比简单版少一半。简单版：使用暴力建堆，初始为空堆，每个元素依次加入堆中。
2022-10-15 20:33:58
135
翻译 一种基于AVL树的Map实现（使用golang）
AVL树是以其发明者Adelson-Velskii和Landis命名的一种二叉查找树。均衡因子-1、0、1代表每个节点的均衡状态。为了更简单的实现，我们记录底板的高度并动态计算其平衡系数。向左旋转和向右旋转。对于向右旋转，假设我们有一棵以R为根节点的树，我们将整棵树右转90度，然后将其调整为有效的树。对于向左旋转，假设L是树的根节点，我们将整个树向左旋转90度，最后将其调整为有效的树。
2022-10-11 21:19:44
174
转载 树选择排序的实现（python）
本文使用python对树选择排序算法进行了原理介绍和实现。树选择排序是一种非常容易实现和易于理解的算法。关键是它的时间复杂度还是最优的。
2022-09-27 11:38:16
242
原创 基于CRC64的通用哈希表(HashMap)的实现（使用golang）
本文就现有哈希博文的两个典型问题进行解决，首先是使用泛型来支持任意类型，然后使用CRC64散列函数将任意二进制数据散列到64位整数再对数组长度取模。由于CRC64具有良好的散列性质，因此实现的哈希表不容易出现冲突。
2022-09-16 15:01:43
1808
原创 快速排序与归并排序的链式实现（golang）
基于链表的排序算法鲜有人提及，本文使用golang实现了基于链表的快速排序算法和归并排序算法。结果表明，本文的实现不仅高效，且相比数组的实现方式更易于理解、实现。
2022-09-13 15:30:11
642
原创 一种基于堆的链式优先队列实现（使用golang）
传统的堆使用的是数组实现方式。众所周知数组是定长的，因此给堆的实际使用带来了限制与不便。本文使用基于链式的实现方式。
2022-09-10 22:12:12
276
原创 元宇宙离我们有多远
元宇宙离我们有多远杨圆飞202128015029001No.145元宇宙（Metaverse）即数字虚拟世界。电影《头号玩家》中的游戏“绿洲”、《黑客帝国》中的“矩阵”就是这样一个数字虚拟世界。因为这两个电影，人们对元宇宙有了具象化的认识。人们可以在元宇宙中像现实世界一样交友、恋爱、旅游、结婚，仿佛穿梭在一个平行于现实世界的宇宙，此外还可以自由地在两个宇宙中切换。虽然2020年元宇宙才新兴并进入普通大众视野，但是早在1992年这个概念就已经诞生，2003年已经有人围绕元宇宙一词展开讨论，二三十年
2022-04-28 16:33:47
615
原创 一种旅行商问题（TSP）具有高近似比的启发式解法的python实现
简介文本实现了一个自研的TSP问题近似解法。在规模5～100的问题上近似比在1.1左右。另外在规模为1000的一个测试用例上测得近似比为：1.0742784198679693。时间复杂度O(n^3)。基本思想：基于最近邻的思想，每次选择一个最近且加入后不会产生边交叉的顶点。但是有可能不存在这样的顶点。所以当不存在时，选择最近的顶点，且把该顶点加入后，去除边交叉。直到所有顶点都被选择为止。注意：这里的边交叉是指：路径中存在一条子路径，可以通过翻转该子路径后使得原路径变短。如下图。实验结果本文对
2022-02-19 15:05:00
541
原创 使用pyconcorde计算二维平面的旅行商问题（TSP）
简介众所周知，TSP问题是一个NP问题，至今只能通过近似的方法来求解。即使使用分支限界方法等非近似算法算得依然很慢。比较好的近似算法有：Lin–Kernighan 在100以内几乎可以得到最优解，速度很快，时间复杂度O(n2.2)O(n^{2.2})O(n2.2)Christofides 理论最坏情况可以达到1.5倍的近似比，时间复杂度O(n3)O(n^3)O(n3)但是代码...
2022-02-18 10:13:18
2544
10
原创 神经网络机器翻译简单模型参考实现
简介本文实现了一个把阿拉伯数字转换成中文表达的神经网络翻译模型(NMT)。例如，输入 504，输出 “五百零四”例如，输入出 4021，输出“四千零二十一”由于本人快期末了，时间有限，暂时只支持数字 0~9999。实现都在代码中，有详细注释。安装paddle 2.x 后。可直接运行。import numpy as npfrom typing import *import paddledef dict_zh(x:str): """ 中文数字字符到id的映射 :p
2021-12-05 20:49:47
1360
原创 词法分析总结
词法分析词法分析是对自然语言进行较浅层次处理的过程。中文分词英文有空格可以将单词分开。但是中文都是连续的字串，因此将中文切分成词，面临着困难。主要有：交集型歧义：例如 下雨天地面积水。可以分成下雨天/地面/积水。也可以分成下雨/天地/面积/水。组合型歧义：例如门把手弄坏了。可以分成 门/把/手/弄/坏/了。或门/把手/弄/坏/了。在分词实践中，会出现词典或样本数据中没有出现过的新词，这些词称为集外词。分词错误中 98.33%由集外词导致。而由歧义导致的只占1.67%。因此在中文自动分词中能
2021-10-29 23:12:42
1332
原创 图卷积网络原理及其基于paddlepaddle的实现
图卷积网络这里的图是指Graph，一种数据结构。图卷积网络关键问题在于如何定义在图上的卷积操作。目前有两种方法：谱方法空间方法已经证明，谱方法是空间方法的一种特例。本文将简要介绍目前关于图卷积操作的基本方法，以其基于paddlepaddle平台实现了其中一种称为GCN的图卷积网络。由于图像可以视为一种特殊的Graph。因此图卷积网络也可以处理图像的数据。将实现后的网络用于MNIST数据集做图的分类，实验结果表明，图卷积网络具有很强的表达能力。谱方法对于一个图G=(V,E,W)G=(V,E,
2021-10-23 21:07:56
516
原创 语言模型总结
语言模型概述语言模型是一个用于判断句子出现概率的数学模型。假设我们有一个句子s=(w1,w2,...,wm)s=(w_1,w_2,...,w_m)s=(w1,w2,...,wm)。其中wiw_iwi为句子中的第i个词语。根据古典概型，那么语言模型可表示为：P(s)=人类说过的所有句子中s的个数人类说过的所有句子个数P(s) = \frac{人类说过的所有句子中s的个数}{人类说过的所有句子个数}P(s)=人类说过的所有句子个数人类说过的所有句子中s的个数统计语言模型显然，上述语言模型公
2021-10-16 16:17:59
946
原创 受限玻尔兹曼机的python参考实现
简介众所周知，玻尔兹曼机好是好，但是太复杂了，所以在实际应用中不会使用。而受限玻尔兹曼机（Restricted Boltzmann machine, RBM）是它的一个带约束的版本，因此模型变得更加简单。受限玻尔兹曼机是一种生成式的机器学习模型，能够学习样本的概率分布。根据学到的概率分布，可生成符合分布的样本。例如可以用它学习人脸图片的概率分布，然后用它学到的概率分布来生成一张这个世界不存在的人脸。总而言之，RBM是通过输入数据集学习概率分布的随机生成神经网络。它把网络中的节点分为两层：可见层隐藏
2021-10-09 15:51:36
1795
1
原创 插入排序的新视角
很久以前就实现过插入排序，基本是照着书上的标准过程实现的。这个算法的思想也很简单。以从小到大排序为例，就是从第一个元素开始，往后依次选择一个元素插入到合适的位置。算法时间复杂度为O(N2)O(N^2)O(N2)。例如排序这几个数字： 3→2→1→5→43 \rightarrow 2 \rightarrow 1 \rightarrow 5 \rightarrow 43→2→1→5→4首先选择3，确定其位置 : 3→3 \rightarrow3→然后选择2，确定其位置，因为2比3小，所以应该放在3的前面
2021-09-19 11:32:14
56
原创 关系数据库重点关系运算的形式化表述
补关系模式R(A1,A2,...,An)R(A_1, A_2,...,A_n)R(A1,A2,...,An),RRR上的关系rrr。如果dom(R)dom(R)dom(R)表示关系RRR上所有无组的集合。则：rˉ=dom(R)−r\bar{r} = dom(R) -rrˉ=dom(R)−r设R(A,B),dom(A)=a1,a2,a3,dom(B)=b1,b2,r={(a1,b1),(a1,b2),(s2,b1)}R(A,B),dom(A)={a_1,a_2,a_3},dom(B)={b_1
2021-09-14 09:26:33
107
原创 三句话，完成英文语料的词频统计
简介有时候有必要对一个英文语料进行统计，以便发现其中的规律。例如，统计词频从而知道哪些词使用得比较频繁。本文实现了三个函数完成英文语料的统计功能，重点研究在什么条件下能够使语料中90%单词能被人读懂。数据集本文使用MASC数据集，下载地址：https://www.anc.org/data/masc/该数据集是一个开放的社区资源，从更大的语料集Open American National Corpus (OANC)上抽取而成， 由500,000多个单词组成。统计代码代码由js写成。对数据集中的每一
2021-09-13 23:15:29
747
原创 Json解析器的设计与实现
简介本文设计并实现了一个简化版的json解析器。可解析json中的对象、数组和字符串。同时解析器还可把对象编码成json的格式。实现采用C++语言。需要前置知识：编译原理文法根据旧版json的文法规则，可反推出如下上下文无关文法，并使用EBNF表示：其中 \uxxxx 表示除了 \ 和 " 以外的字符<json> -> <object> | <array> | <string><object> -> '{'
2021-09-10 13:32:36
899
原创 隐式马尔可夫模型（HMM）的Python实现
原理请参考 《自然语言处理入门》 作者何晗 第129页代码隐式马尔可夫模型可由λ=(π,A,B)\lambda=(\pi, A,B)λ=(π,A,B) 完全描述。代码首先实现了接口HMM，该接口定义了隐式马尔可夫模型的一些公共操作。其次定义了专门用于文本序列标注的隐式马尔可夫模型 TextSequence， 实现了对文本的操作。最后实现了维特比算法(viterbi)对隐式马尔可夫模型进行解码，根据输入序列预测状态序列。TextSequence 可用于分词、实体识别、事件抽取等自然语言处理任务。
2021-07-15 13:45:39
6100
2
原创 js实现快速排序和归并排序
引言突发奇想使用js来实现这两个经典的排序算法。由于JavaScript高度方便的数据结构，因此相比C版本的代码，此版本更加容易理解！快速排序/** 快速排序（函数思想） * @param {Object} list 要排序的列表 * @return {Array} 已经排序的数组 */function quikSort(list){ if(! (list instanceof Array)){ throw (new Error("错误的列表")); } if(list.len
2021-04-30 21:23:58
207
1
原创 新技术分享：在浏览器中使用ES6的import和export
前言之前一直通过node使用ES6的import和export，但是没想到现在浏览器也支持了。迫不及特地写了一个小示例体验了一把，觉得还可以。详细可以见这篇博文： https://segmentfault.com/a/1190000014342718 。’像传统js的加载方式一样，模块化的js也可以有2种使用方式，如下所示。但注意这里的 type=“module”， 这是传统加载方式和按模块方式加载的区别。（1）第一种：引入外部js <script src="xxx.js" ty
2020-12-13 23:19:38
572
1
原创 用C模拟面向对象2(模拟OOP)
前言随着编程经验逐渐丰富，我发现编程的思想并不局限于任何一种语言，比如我们就可以使用C语言去实现类似于C++和Java的面向对象（OOP）编程。我惊讶于C语言的强大，因为它可能写出像linux这样庞大的系统。对于现在的大型工程来说，面向对象是发不可少的一种东西了。因此本篇博文详细介绍如何使用C这样一种简单语言去实现复杂的面向对象编程。之前我的一篇博文已经介绍了如何使用C语言来模拟面向对象的编程范式，但是那篇其实也是借鉴了其实人的博客内容，而且思路有写混乱。现在，我从工程角度再次梳理这个问题，并举了一个设
2020-11-14 15:00:56
7294
gvim82.rar
2020-04-19
RStudio-1.2.5033.rar
2020-02-14
R-3.6.2-win.rar
2020-02-14
软著代码整理工具V1.0.exe
2020-02-11
StarUML Setup 3.1.1.exe
2019-11-15
iris.rar-经典数据集
2019-10-24
postgresql 11.1 windows x64
2018-11-10
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人