中文JavaBeat

看到一篇文章感觉很不错，可以开阔一下某些思路，转贴在此：

今天碰到一个很有意思的问题：用户在数据库中存有N张照片（照片是有顺序的），然后用户可以任意调整照片之间的顺序，照这样的话，每一次用户调整某一张照 片的顺序后相应地要想多米诺骨牌一样要影响他后面照片的顺序，这样在数据库中有M张照片的顺序编号都需要去Update，这样的话对数据库的压力太大。比 如第8张照片要移动到第二位，那么第7、6、5、4、3、2都要相应地改变，也就是在数据库中有7条记录需要去Update，代价太大。

最后这个问题是这样巧妙解决的：照片在数据库的编号不是1，2，3……这样连续的自然数，而是使用1024、2*1024、3*1024……这样跳跃的数 字来代表，当再有移动的时候，比如把8*1024移动到第二位也就是1024和2*1024之间的话，只需要在数据库中做一次Update，让 8*1024变成（1024+2*1024）/2,后面的那些编号都可以维持不变。这样数据库的压力就小多了！

当然时间久了后可能某一区段的数据编号太密集，甚至都无法插入了，嗯就像女人变老了后连上的皱纹都挤到一起去了，当然就需要去拉皮了，也就是当插入的时候发现没有位置了，这时候可以让前后两个位置向外围扩张一下，恩就像女士拉皮一样，呵呵，很形象吧。

当然要说这种算法怎么想到的，那多看看我们平时的生活，比如我们排队的时候，如果站的非常稀疏插一个人进来的话对整个队伍影响不大，但是如果一个紧靠一个的话，差一个进来大家都要相应地挪动一下，呵呵，所以说很多算法都可以从生活中受到启发的！比如Google的PageRank算法(我的一篇关于PageRank的原理和实现的文章)就是由论文质量的衡量很大程度上是由该论文被其他论文所应用的次数来决定的。

还有那个PK算法（也可以称作是多数派算法），比如一个字符串中一定有一个字符的数量超过了整个字符串长度的一半，怎么样找出这个字符？那么可以你可以在 这个字符串中不断取两个字符不一样的话这两个字符同时删除，一样的话只留下一个，一直到最后，剩下的那个就是所要找的那个（当然有一些的特殊情况需要处 理、优化），这种解决的思想就是非常形象的超女比赛的PK制度，哈哈，太有意思了吧。

所以我很多时候碰到很优美的算法的时候老是在想这个算法人家是怎么想到的？这个算法背后所代表的原理或者思想又是什么？这种思想还能够用在哪里？我觉得这才是最关键，能够让你不断地在算法领域越来越有悟性。

希望这些能对大家有一些启发，也希望大家可以谈谈自己感触很深的算法

LCS(longest common substring)算法,即最大公共子串,它是求两个字符串最长公共子串的问题。大体解法是用一个矩阵来记录两个字符串中所有位置的两个字符之间的匹配情况，若是匹配则为1，否则为0。然后求出对角线最长的1序列，其对应的位置就是最长匹配子串的位置.

例如,有两个字符串:

A= I MISS MY CODE HI

B= One Like MY Code

这里,先忽略掉大小写,通吃,在C#或者PHP中,String.ToLower()或者lower()可以考虑.对于其中的特殊字符,例如空格,可以在比较的时候直接删除.另外,该算法比较与顺序无关,可以随意的翻转字符串.接下来比较.

在上面的矩阵图中,其中的红色就可以看成匹配的字符串.

或者这样标示矩阵会更方便：

原文地址：http://renxijun.blog.sohu.com/60014665.html

喜欢本文吗？那就我吧！
如果你对本文有任何看法或者疑问，欢迎在下面的 评论 中留言，我会在第一时间回复你！