求编辑距离

定义

编辑距离又称Leveinshtein距离，是由俄罗斯科学家Vladimir Levenshtein在1965年提出。编辑距离是计算两个文本相似度的算法之一，以字符串为例，字符串a和字符串b的编辑距离是将a转换成b的最小操作次数，这里的操作包括三种：

• 插入一个字符
• 删除一个字符
• 替换一个字符

举个例子，kitten和sitting的编辑距离是3，kitten -> sitten(k替换为s) -> sittin(e替换为i) -> sitting(插入g)，至少要做3次操作。

求素数个数

我最近在leetcode上撸了一个小算法，虽然已经工作了五年，当看到每次代码提交后排名的提升，内心依然很有成就感。题目比较简单，求小于n的素数个数，素数也叫质数，具有以下特点：

• 正整数
• 只能被1和本身整除
• 1既不是素数也不是合数，所以最小的素数是2

根据上面的特点，我们还可以推断出：

• 除了2，其它的素数都是奇数