求编辑距离

定义

编辑距离又称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，其它的素数都是奇数

服务化架构下的数据一致性如何保证

在系统服务化的过程中，我们不得不面临的一个问题是多个子系统间业务数据的一致性如何保证，解决这个问题有多种方式。

XA

可能很多人首先会想到XA规范中定义的分布式事务，下图是XA规范中定义的DTP(Distributed Transaction Processing)模型：

但该模式并不适用于如今的互联网应用，主要有以下几点问题：

1. XA采用2PC，并不能完全保证一致性；
2. 2PC有同步阻塞问题，并且增加了2次RTTs(round trip times)，性能低下；
3. 服务化架构天然与DTP模型相悖，服务化架构显然是面向服务的，为了解决数据一致性，直接向对方暴露数据库，这还是服务化吗？