欢迎访问小程序员!

对于一个给定的连通的无向图 G = (V, E),希望找到一个无回路的子集 T,T 是 E 的子集,它连接了所有的顶点,且其权值之和为最小。 因为 T 无回路且连接所有的顶点,所以它必然是一棵树,称为生成树(Spanning Tree),因为它生成了图 G。显然,由于树 T 连接了所有的顶点,所以树 T 有 V – 1 条边。一张图 G 可以有很多棵生成树,而把确定权值最小的树 T 的问题称为最小生成树问题(Minimum Spanning Tree)。术语 “最小生成树” 实际上是 “最小权值生成树” 的 ....

归并排序算法介绍,请参照Wikipeida zh.wikipedia.org/wiki/%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F 基本思想: 大文件分割成行数相等的两个小文件,使用递归一直分割到所有所有小文件低于限制行数 小文件直接排序 两个排序好的小文件归并到大文件 直到最后所有排序好的文件归并到输入的大文件并返回   之前看了网上很多示例代码,写的很不简洁, 引入了过多的临时变量i, j, k等等, 导致程序基本没法看, 只好自己写了一个,没有很关心执行效率, 只求够用, ....

IKAnalyzer中文分词,计算句子相似度 一、简介     IKAnalyzer是一个开源的,基于java语言开发的轻量级的中文分词工具包。以开源项目Luence为应用主体的,结合词典分词和文法分析算法的中文分词组件。独立于Lucene项目,同时提供了对Lucene的默认优化实现。(简介来源:百度百科) 二、准备     项目结构:          IKAnalyzer2012FF_u1.jar 下载     lucene-core-4.6.1.jar 下载     ext.dic     stopw ....

学习编程的时候,经常会看到stack这个词,它的中文名字叫做"栈"。 理解这个概念,对于理解程序的运行至关重要。容易混淆的是,这个词其实有三种含义,适用于不同的场合,必须加以区分。 含义一:数据结构 stack的第一种含义是一组数据的存放方式,特点为LIFO,即后进先出(Last in, first out)。 在这种数据结构中,数据像积木那样一层层堆起来,后面加入的数据就放在最上层。使用的时候,最上层的数据第一个被用掉,这就叫做"后进先出"。 与这种结构配套的,是一 ....

这篇文章也是基于知乎的一个答案。因为前天蛋疼写了个99行蛋疼版2048,所以一时兴起在知乎上搜了搜2048,结果发现了这个问题。看了看,票数最高的两个答案都是错的,所以自己推导了一下。2048的玩法就不赘述了,先来看看相关的规则,因为是Gabriele Cirulli让这个游戏火起来的,以他的源代码为准(Gabriele Cirulli的版本的地址:2048)。 记分规则:在https://github.com/gabrielecirulli/2048/blob/master/js/game_manager ....

本文原始内容来源于 stackexchange,遵循 cc-wiki 协议; 近日 Emanuele Viola 在 Stackexchange 上提了这样的一个问题,他希望有人能够列举一些目前软件、硬件中正在使用的算法的实际案例来证明算法的重要性,对于大家可能给到的回答,他还提出了几点要求: 使用这些算法的软件或者硬件应该是被广泛应用的; 例子需要具体,并给出确切的系统、算法的引用地址; 在经典的本科生或者博士的课程中应该教过这些算法或者数据结构; Vijay D 的回复获得了最佳答案,他的具 ....

以下是在编程面试中排名前10的算法相关的概念,我会通过一些简单的例子来阐述这些概念。由于完全掌握这些概念需要更多的努力,因此这份列表只是作为一个介绍。本文将从Java的角度看问题,包含下面的这些概念: 1. 字符串 2. 链表 3. 树 4. 图 5. 排序 6. 递归 vs. 迭代 7. 动态规划 8. 位操作 9. 概率问题 10. 排列组合 1. 字符串 如果IDE没有代码自动补全功能,所以你应该记住下面的这些方法。 toCharArray() ....

如题,从最大的10000000个元素里面找出最大的前100个,下面是我的代码实现:        import java.util.Comparator; import java.util.PriorityQueue; import java.util.Random; import java.util.logging.Logger; public class FixSizedPriorityQueue<E extends Comparable> { private final sta ....

Apriori算法 优点:易编码实现 缺点:在大数据集上可能较慢 适用数据类型:数值型或者标称型 算法过程: 关联分析是一种在大规模数据集中寻找有意思的关系的任务,这里的有意思的关系有两种:频繁项集(frequent item sets)或关联规则(association rules)。 支持度(support):一个项集的支持度被定义为数据集中该项集的记录所占的比例。 置信度(confidence):关联规则A->B的置信度表示为support(A,B)/support(A) 单纯暴力做的话有2^n ....

引子 机机是个好动又好学的孩子,平日里就喜欢拿着手机地图点点按按来查询一些好玩的东西。某一天机机到北海公园游玩,肚肚饿了,于是乎打开手机地图,搜索北海公园附近的餐馆,并选了其中一家用餐。 饭饱之后机机开始反思了,地图后台如何根据自己所在位置查询来查询附近餐馆的呢?苦思冥想了半天,机机想出了个方法:计算所在位置P与北京所有餐馆的距离,然后返回距离<=1000米的餐馆。小得意了一会儿,机机发现北京的餐馆何其多啊,这样计算不得了,于是想了,既然知道经纬度了,那它应该知道自己在西城区,那应该计算所在位置P与西 ....

1 Lucene字典 使用lucene进行查询不可避免都会使用到其提供的字典功能,即根据给定的term找到该term所对应的倒排文档id列表等信息。实际上lucene索引文件后缀名为tim和tip的文件实现的就是lucene的字典功能。 怎么实现一个字典呢?我们马上想到排序数组,即term字典是一个已经按字母顺序排序好的数组,数组每一项存放着term和对应的倒排文档id列表。每次载入索引的时候只要将term数组载入内存,通过二分查找即可。这种方法查询时间复杂度为Log(N),N指的是term数目,占用的空间 ....

AdaBoost(自适应boosting,adaptive boosting)算法 算法优缺点: 优点:泛化错误率低,易编码,可用在绝大部分分类器上,无参数调整 缺点:对离群点敏感 适用数据类型:数值型和标称型 元算法(meta algorithm) 在分类问题中,我们可能不会只想用一个分类器,我们会考虑将分类器组合起来使用,这种方法称为集成方法(ensemble method)或元算法。元算法有多种形式,既可以是不同算法集成也可以是一种算法不同设置的集成。 两种集成方式(bagging & boo ....

前言 LZ77算法是无损压缩算法,由以色列人Abraham Lempel发表于1977年。LZ77是典型的基于字典的压缩算法,现在很多压缩技术都是基于LZ77。鉴于其在数据压缩领域的地位,本文将结合图片和源码详细介绍其原理。 原理介绍: 首先介绍几个专业术语。 1.lookahead buffer(不知道怎么用中文表述,暂时称为待编码区): 等待编码的区域 2. search buffer: 已经编码的区域,搜索缓冲区 3.滑动窗口: 指定大小的窗,包含“搜索缓冲区”(左) + “待编码区”(右) 接下来, ....

这篇文章尝试使用 Haskhell 来重写常见的排序算法。这里不考虑效率,比如时间和空间上的,所以不会刻意去写成尾递归。 插入排序 插入排序是一种简单易懂的排序。这里分为两个步骤: 将一个元素插入一个已被排序的数列 对一个未排序的数列不停施以步骤 1 首先步骤 1,要插入数 x,当前序列中第一个数为 y。将 x, y 较小的数放在前面,然后对去除第一个数之后的子序列不停重复上述过程。 insert :: Ord a => a -> [a] -> [a] insert x [] = [x] ....

一.前言 一致性哈希(Consistent Hashing),最早由MIT的Karger于1997年提出,主要用于解决易变的分布式Web系统中,由于宕机和扩容导致的服务震荡。现在这个算法思路被大量应用,并且在实践中得到了很大的发展。 二.算法设计 1.问题来源 一个由6台服务器组成的服务,每台Server负责存储1/6的数据,当Server1出现宕机之后,服务重新恢复可用时的场景。 如下表格可以很清楚的看到,当Server1宕机时,Hash1的服务完全不可用了,所以需要ReHash由剩余5台机器提供所有的数 ....

本篇博文将给大家带来几个判断一个字符串中的字符是否都只出现一次的方法。 方法一: 首先将字符串转换成字符数组(char[]), 循环迭代char数组,对于每一个字符c,如果其第一次出现的索引和最后一个出现的索引是不一样的,那么我们可以认为该元素出现多次。 public static boolean isUniqueChars(String str) { char[] chars = str.toCharArray(); for (char c : chars) { if ....

1 概述 本文对比较常用且比较高效的排序算法进行了总结和解析,并贴出了比较精简的实现代码,包括选择排序、插入排序、归并排序、希尔排序、快速排序等。算法性能比较如下图所示: 2 选择排序 选择排序的第一趟处理是从数据序列所有n个数据中选择一个最小的数据作为有序序列中的第1个元素并将它定位在第一号存储位置,第二趟处理从数据序列的n-1个数据中选择一个第二小的元素作为有序序列中的第2个元素并将它定位在第二号存储位置,依此类推,当第n-1趟处理从数据序列的剩下的2个元素中选择一个较小的元素作为有序序列中的最后第2个 ....

说明:本文分为三部分内容,第一部分为一道百度面试题Top K算法的详解;第二部分为关于Hash表算法的详细阐述;第三部分为打造一个最快的Hash表算法。 第一部分:Top K 算法详解 问题描述 百度面试题: 搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来,每个查询串的长度为1-255字节。 假设目前有一千万个记录(这些查询串的重复度比较高,虽然总数是1千万,但如果除去重复后,不超过3百万个。一个查询串的重复度越高,说明查询它的用户越多,也就是越热门。),请你统计最热门的10个查询串,要求使 ....

注意:只是个人理解,可能有不正确的地方 DSA(Digital Signature Algorithm)签名算法是由美国国家标准与技术研究院(NIST, National Institute of Standards and Technology)提出的一个关于数字签名的美国联邦信息处理标准(FIPS, Federal Information Processing Standard)。该标准在1991年8月提出,1993以FIPS 186被采用,作为数字签名(DSS, Digital Signature S ....

注意:只是个人理解,可能有不正确的地方 ElGamal加密算法是一种非对称加密算法,基于Diffie-Hellman密钥交换算法,由Taher Elgamal在1985年提出。 ElGamal加密算法可以应用在任意一个循环群(cyclic group)上。在群中有的运算求解很困难,这些运算通常与求解离散对数(Discrete logarithm)相关,求解的困难程度决定了算法的安全性。 群(Group)的定义: 群是数学中的概念。 一些元素组成的集合,如果元素满足以下条件,则把这些元素组成的集合叫做群: 在 ....