霍夫曼树和霍夫曼编码

一、定义

霍夫曼树

又称最优二叉树,是一种带权路径长度最短的二叉树。所谓树的带权路径长度,就是树中所有的叶结点的权值乘上其到根结点的路径长度(若根结点为0层,叶结点到根结点的路径长度为叶结点的层数)。树的路径长度是从树根到每一结点的路径长度之和,记为 WPL =(W1*L1 + W2*L2 +[......]

阅读全文

二叉堆计算动态中位数

要求

最近在刷算法,遇到一个有意思的题,要求如下:

设计一个数据结构,可随时插入节点,且随时查询节点集合的中位数,要求插入节点的时间复杂度为 O(logN),查询中位数的时间复杂度为 O(1)。

中位数定义:节点个数为奇数个时,为有序情况下集合的中间节点;偶数时,为中间两节点的平均值。

[……]

阅读全文

算法复杂度和大O表示法

概念

SICP算法复杂度是算法分析里的概念(对应到SICP里的增长阶),是衡量计算资源消耗数量(例如计算时间,存储器使用等)的指标。

算法的复杂度在理论上表示为一个函数:其定义域是输入数据的长度(通常考虑任意大的输入,没有上界),值域通常是执行步骤数量(时间复杂度)或者存储器位置数量(空间复杂度)。[……]

阅读全文

八皇后问题的Julia实现

问题

八皇后问题是一个以国际象棋为背景的问题:如何能够在8×8的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后?

尝试使用Julia实现一个回溯解:

实现

回溯法进行暴力查找:

很可惜,我[……]

阅读全文

对称加密、公钥加密和RSA

引子

对于加解密,我一直处于一种知其然不知其所以然的状态,项目核心部分并不倚重加解密算法时,可以勉强对付过去,一旦需要频繁应用诸如 AES/RSA等算法,这种状态就颇令人捉急了。

是时候了解一下原理了,所以找来了这本图解密码技术 给自己补补课:

图解密码技术

在该书深入浅出的指引下 ,补充了[……]

阅读全文

哈希函数

最近参加了一次面试,虽无笔试环节,几位考官却都在算法和思路题上大作文章,颇为受益

有这么几个问题印象深刻:

  1. 自创数据结构存储一些字符串,如何快速匹配用户输入(包含或者相等)?
  2. 若干memcached分布式的组成集群,有什么办法均匀的分布存储?
  3. 爬虫的排重怎么快又省(布隆过滤器原[……]

阅读全文