春夏秋冬

宽度优先搜索

通常使用queue来实现BFS，在python中是collections中的deque

什么时候用BFS

图的遍历 traversal in graph

• 层级遍历 level order traversal （树）

  • 102.二叉树层序遍历

  • 103.二叉树的锯齿层遍历

  • 107.二叉树的层次遍历 II

  • 114.

  • 297.Serialize and Deserialize Binary Tree

• 由点及面 connected component （图，矩阵）

• 拓扑排序 topological sorting

简单图的最短路径 shortest path in simple graph

复杂图应该用→ Dijkstra, SPFA, Floyd.最长路径的话如果图能分层用DP，不能用DFS

分为：求具体的path 或者 求最短的值

• 111.二叉树的最小深度
• 542.01 矩阵
• 1091. Shortest Path in Binary Matrix
• Web Crawler Multithreaded
• Web Crawler

非递归的方式找所有方案Iteration solution for all possible results

BFS可以用来做序列化

什么是序列化？

将“内存”中结构化的数据变成“字符串”的过程

序列化：object to string 反序列化：string to object

什么时候序列化？

1. 将内存中的数据持久化存储时： 内存中重要的数据不能只是呆在内存里，这样断电就没有了，所需需要用一种方式写入硬盘，在需要 的时候，能否再从硬盘中读出来在内存中重新创建
2. 网络传输时：机器与机器之间交换数据的时候，不可能互相去读对方的内存。只能讲数据变成字符流数据（字符串） 后通过网络传输过去。接受的一方再将字符串解析后到内存中。

序列化的手段

• XML
• Json

不同数据结构做BFS的注意点

拓扑排序

当图中存在依赖关系时往往会用到拓扑排序。拓扑排序能用BFS也能用DFS。不过一般能用BFS解决就用BFS解决

• 求任意1个拓扑序（Topological Order）
• 问是否存在拓扑序（是否可以被拓扑排序）
• 求所有的拓扑序 （需要使用DFS）
• 求是否存在且仅存在一个拓扑序 Queue中最多同时只有1个节点

live2d

live2d是一种将静态2d图片，通过将一系列的2D图像进行平移、旋转和变形等操作，生成一个具有自然动画效果的可动人物模型。

在hexo配置live2d，使用了这个教程。

根据教程的说法，完全可以自己创建一个live2d model。不过为了省时间，这里就直接npm安装现有的一个叫wanko的模型。

vasline 评论系统

之前使用了gittalk作为评论系统，可惜bug很多而且评论需要注册github账户。所以转用vasline，不需要账户就能评论还支持markdown。需要注意的是，hexo自带了vasline，所以不需要再用npm安装包了。不过由于vasline使用了leanclud的服务。要使用vasline，还是需要先注册LeanCloud的账号来获得id和key。并把得到的id和key设置在_config.yml 里。

vasline也支持文章阅读量统计。 在hexo中只需要在_config.yml 里的vasline项把visitor设置为true即可。

机器学习：data，model，learning

我们需要将数据（data）数字化，具体的说是向量（vector）化。 因此研究线性代数是很有必要的。

Rabin-Karp算法，是由M.O.Rabin和R.A.Karp发明的一种基于哈希函数的字符串查找算法。

近期在leetcode遇到的一道hard题 ，了解到了Rabin-Karp算法。原题如下：

给出一个字符串 S，考虑其所有重复子串（S 的连续子串，出现两次或多次，可能会有重叠）。返回任何具有最长可能长度的重复子串。（如果 S 不含重复子串，那么答案为 “”。）

一个很自然的想法是假设一个长度为L的子串，然后查找这个长度的子串是否是重复的。由于如果L长度子串有重复的，则L-1也必定满足拥有重复的字串。我们可以使用二分查找来寻找最大的长度。这样，问题就变成了寻找一个长度为L的子串在S中是否有相同的子串。

如果不使用Rabin-Karp算法，遍历字符串需要 $O(n)$的时间，而每一次的比较又需要$O(n)$的时间，这样一来一次验证需要$O(n^2)$的时间。Rabin-Karp算法的思想很简单：不去直接比较字符串是否相等，而是去比较字符串的哈希值，相等则认为是一致的。（其实因为哈希是不可逆的，在实际情况数据很大的时候有时会不一致，这时需要再比较下字符串验证。）

Rabin-Karp使用的哈希方法如下：

字母$a-z$分别对应数字$1-26$，这样我们就可以把字符串转换成26进制的数字了。例如abc可以转换成：
$$
abc = 1 \times 26^2 + 2 \times 26^1 + 3 \times 26^0
$$
更广泛的说一个长度为$L$ 字符串的哈希函数为：
$$
H_i = S[i] \times 26^{L-1} + S[i+1] \times 26^{L-2} + …+ S[i+L-1] \times 26^{0}
$$

如果是直接比较哈希值的话则没有意义（因为计算这个公式的哈希值就和直接比较字符串复杂度一样了）但是如果考虑到$H_{i+1}$ 和 $H_i$ 有方程关系，我们不需要每次去重新计算子串哈希值，只要再原来基础上加上右边新加入的字符哈希值，减去左边的字符哈希值就可以去比较了。这样一来计算哈希值的时间复杂度就是$O(1)$。这个思想有点类似slide-window。

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

def RabinKarp(self, L, S):
    '''
    input:
    L: pattern length
    S: target string
    output:
    tuple: (bool, aim string)
    '''
    a = 26
    n = len(S)
    h = 0
    nums = [ord(S[i]) - ord('a') for i in range(n)]
    for i in range(L):
        h = (h * a + nums[i]) % (2**32 - 1)
    
    aL = pow(a, L, 2**32)
    seen = {h}
    for start in range(1, n - L + 1):
        # compute rolling hash in O(1) time
        h = (h * a - nums[start - 1] * aL + nums[start + L - 1]) % (2**32 - 1)
        if h in seen:
            return (True, S[start: start+L])
        else:
            seen.add(h)
    return (False, '')

注意事项

由于代码里有指数运算，数字会变得很大，所以在进行哈希值求解后要进行取模运算。

这是我得用Hexo写的第一篇博客，感谢Hexo官网的教程。下面是一些简单使用Hexo的方法。会随着我对Hexo的了解不断更新。

快速开始

创建一篇新文章

1

$ hexo new "Hello-world"

运行服务器

1

$ hexo server

生成静态文件

1

$ hexo generate

部署网站

1

$ hexo deploy

使用数学公式

Hexo并不原生支持数学公式，需要安装插件mathjax。

1

$ npm install hexo-math --save

在站点配置文件 _config.yml 中添加：

1
2
3
4
5
6

math:
  engine: 'mathjax' # or 'katex'
  mathjax:
    # src: custom_mathjax_source
    config:
      # MathJax config