霍夫曼树和霍夫曼编码

一、定义

霍夫曼树

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

二叉堆计算动态中位数

要求

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

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

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

[……]

算法复杂度和大O表示法

概念

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

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

八皇后问题的Julia实现

问题

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

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

实现

回溯法进行暴力查找：

function find_safe_coord(board::Array{Int}, curr_row, n; trace_back=false)
    start = 1
    if trace_back
        start = board[curr_row] + 1
    end
    for col = start : n
        has_menace = false
        for row = 1 : curr_row - 1
            prev = board[row]
            if prev == col || curr_row - row  == abs(col - prev)
                has_menace = true
            end
        end
        !has_menace && return col
    end
    nothing
end

function n_queens_puzzle(n)
    board = zeros(Int, n)
    curr_row = 1
    while curr_row <= n
        coord = find_safe_coord(board, curr_row, n)
        if coord != nothing
            board[curr_row] = coord
            curr_row == n && produce(copy(board))
        end
        if coord == nothing || curr_row == n
            while true
                curr_row -= 1
                curr_row == 0 && return produce(nothing)
                coord = find_safe_coord(board, curr_row, n, trace_back=true)
                if coord != nothing
                    board[curr_row] = coord
                    break
                end
            end
        end
        curr_row += 1
    end
end

# 逐行输出[x,y]
solutions = @task n_queens_puzzle(8)
for solution in solutions
    if solution != nothing
        for row in eachindex(solution)
            print("[$row,$(solution[row])] ")
        end
        println()
    end
end

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

function find_safe_coord(board::Array{Int}, curr_row, n; trace_back=false)

start = 1

if trace_back

start = board[curr_row] + 1

end

for col = start : n

has_menace = false

for row = 1 : curr_row - 1

prev = board[row]

if prev == col || curr_row - row == abs(col - prev)

has_menace = true

end

end

!has_menace && return col

end

nothing

end

function n_queens_puzzle(n)

board = zeros(Int, n)

curr_row = 1

while curr_row <= n

coord = find_safe_coord(board, curr_row, n)

if coord != nothing

board[curr_row] = coord

curr_row == n && produce(copy(board))

end

if coord == nothing || curr_row == n

while true

curr_row -= 1

curr_row == 0 && return produce(nothing)

coord = find_safe_coord(board, curr_row, n, trace_back=true)

if coord != nothing

board[curr_row] = coord

break

end

end

end

curr_row += 1

end

end

# 逐行输出[x,y]

solutions = @task n_queens_puzzle(8)

for solution in solutions

if solution != nothing

for row in eachindex(solution)

print("[$row,$(solution[row])] ")

end

println()

end

end

很可惜，我[……]

对称加密、公钥加密和RSA

引子

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

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

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

DSL in action

最近看了本有意思的书，受到了一些启发，在此记录一下：

DSLs in action

DSL是什么

即 domain-specific language ，是指和业务域模型相关的语言，粗糙的说法：行（业黑）话。关于什么是DSL，见仁见智，比如我认为SQL是一种DSL，有人却认为不是。

用途[……]

Node + Redis 实现分布式Session方案

Session是什么？

Session 是面向连接的状态信息，是对 Http 无状态协议的补充。

Session 怎么工作？

Session 数据保留在服务端，而为了标识具体 Session 信息指向哪个连接，需要客户端传递向服务端发送一个连接标识，比如存在Cookies 中的session_[……]

哈希函数

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

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

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