见路不走

摘要： 这个题目比较好理解。在一个n*n的格子中，放尽可能多的碉堡。这个题目开始想的时候，如果就思考深度搜索或者宽度搜索，会得到错误的答案，因为，当两个碉堡之间有墙的时候，它们是可以在同一行，同一列出现的。也就是说，在遍历的过程中，一行一列是否可以放碉堡的状态是可变的。代码如下:import java.util.Scanner;public class P1045 { private static int... 阅读全文

摘要： 1010，1016都可以采用深度优先递归的方法解，比较简单。1240题目看起来很长，不好理解。理解了就是三维空间的搜索。理解了这个，基本就没有问题了。还有一个需要注意的是这道题目应该采用宽度优先的搜索算法，因为， 题目中要取得最短的路径，这个是深度优先搜索的不能够很方便实现的。能够快速的找到最优解，也是深度优先和宽度优先的一个区别，所以，在时间复杂度上，宽度优先搜索方法，要有优势，但是在空间上，则... 阅读全文

摘要： 这道题目和1238同样基本搜索的思路。题目的大意是给定m，a，b三个数，要找到p，q两个质数，满足一下条件： p*q <= m a/b<= p/q <= 1并且要求找着这样的p和q的乘积最接近m的。数值范围规定如下： 4 < m <= 100000 1 <= a <= b <= 1000这类题目的基本思路 缩小搜索范围 确定搜索的顺序 注意剪枝具体做法：第一步就是要缩小素数的范围，第一感觉是可以在... 阅读全文

摘要： 这是一道搜索入门级的题目。题目大意是：有几个字符串，找到一个最长的子串，这个字串满足条件：子串或者子串的逆序是任意一个字符串的子串，两个只要满足一个就行。考察点有字符串排序、求子串、求字符串的逆序等。我用java实现的，要比C++简单一些。代码如下：import java.util.Scanner;public class P1238 { public static int find(String... 阅读全文

摘要： cassandra的优化工作，进入代码实现的阶段了。用eclipse导入cassandra的源码很方便，cassandra源码中的build.xml已经包含了所有需要的构建项，按照如下步骤进行即可：svn checkout https://svn.apache.org/repos/asf/cassandra/trunk cassandra进入Cassandra目录执行antavro-generate执行antgen-thrift-java执行ant generate-eclipse-filesok！然后打开eclipse import即可。 阅读全文

摘要： 当把倍增算法的流程图画出来之后，就可以理解算法的流程。按照这个流程实现，我开始采用treemap来进行排序，10^5的长度的字符串，耗时10秒左右。今天按照某Acmer的代码，实现了java版的。性能提升接近100倍。Acmer写的代码，一般效率很高，但是可读行非常差，阅读代码的人经常绕在里面出不来了。下面，我详细分析一下java版的实现，希望自己加深理解，也能够帮助同学，欢迎指教。代码解释：整体... 阅读全文

摘要： 在上一篇博客中，讲到计数排序的稳定性非常重要，主要可以体现在基数排序中(?)。这一篇，就来分析一下基数排序。看《算法导论》中的图： 对329，457，657，839，436，720，355几个数字进行排序，使用基数排序的方法，从最低有效位开始，即首先根据个位排序，得到720，355，436，457，657，329，839。十位、百位以此类推。最终得到排序的结果。对于基数排序，待排的数字必须... 阅读全文

摘要： 介绍线性时间排序算法，主要是为了实现构建后缀数组的倍增算法，倍增算法性能保证的主要依据就是采用了基数排序，通常，基础排序会使用计数排序作为rank排序子过程。这里，基数排序和计数排序都是线性时间排序算法，线性时间排序算法还有桶排序。性对于快速排序等比较排序算法而言，线性时间排序算法，没有比较运算。下面先介绍计数排序。 计数排序的基本原理是：对于任意待排的数字x，确定小于x的元素个数，然后将x直接放在最终输出数组中的特定位置上。如有10个小于x的元素，在最终的输出数组中，x就排第11，如果数组是从0开始，则在索引为10的位置。下图是从《算法导论》摘下来的，可以帮助理解计数排序。 如何确定小于x. 阅读全文

摘要： Cassandra自从出了几次大的宕机的情况之后，很少有大公司在用了，我目前知道的，就是twitter的抓取服务使用的Cassandra来存储抓取数据元信息，而且，国内某搜索引擎公司，也是这么做的。我最近的工作之一，就是改进Cassandra，选它一方面是公司的要求，另一方面，学习空间、提速空间性能都比较大。 经过一段时间的调研，确认了三个改进方向（由于公司的原因，现在我只说第一个）。第一个就是索引压缩的改进，往大了说，就是要对Cassandra的索引进行重新设计。重新设计的思路，下面会慢慢讨论。 对于kv存储引擎的索引，根据key是否有序，分为两种：一种是key如果无序，则可以采用hash的 阅读全文

摘要： 对于后缀数组的了解，要始于一篇论文，论文中，使用后缀数组的方式存储索引，改进词组检索的效果和性能，相对于倒排索引而言，后缀数组在空间占用上会比较大，但是效果却非常好，这个是倒排索引所无法高效应对的，而且，个人的一个猜想，会有越来越多的内存索引是基于后缀数组实现的，或许，已经有了。 从别的地方转来的几个个概念，我就不重复了： 子串：字符串S的子串r[i..j]，i≤j，表示r串中从i到j这一段，也就是顺次排列r[i]，r[i+1]，...，r[j]形成的字符串。 后缀：后缀是指从某个位置i开始到整个串末尾结束的一个特殊子串。字符串r的从第i个字符开始的后缀表示为Suffix(i)，也就是Suff 阅读全文