转载请注明作者： phylips@bmy 出处： http://duanple.blog.163.com/blog/static/7097176720098283597120/

对于通常的尾递归很容易转换成循环。通过手工模拟我们基本上就可以确定如何进行转换。实际上尾递归的转换也可以看成是下面这种模式的特殊情况，在这种模式下，尾递归只是一个这样的递归树。 read more

转载请注明作者： phylips@bmy 出处： http://duanple.blog.163.com/blog/static/70971767200982584340501/

1.求最长回文子串。
[解法]：
将整个字 符串反过来写在原字符串后面，中间用一个特殊的字符隔开。这样就把问题变为了
求这个新的字符串的某两个后缀的最长公共前缀。而某两个后缀的lcs的计算利用后缀数组，可以O(1),这样总的复杂度就可以降为O(n)。
eg：aabebf  —->   aabebf&fbebaa read more

转载请注明作者： phylips@bmy 出处： http://duanple.blog.163.com/blog/static/7097176720098311658625/

RSA加密系统，实际上基于这样一个基本事实。大数的素性测试要比因子分解简单的多，因子分解是一个难问题。

如何测试一个数n是不是素数呢？简单的办法就是试一下它能否整除比它小的那些数，当然可以优化只检测小于sqare(n),但是无论如何优化，需要检测的数的个数都将不会小于小于sqare(n)的素数的个数。根据拉格朗日定理，小于n的素数的个数大概=n/ln(n)，也就是说这个数目很大，数量级上很接近n了。所以这个路子实际上很难降低复杂度。 read more

转载请注明作者： phylips@bmy 出处： http://duanple.blog.163.com/blog/static/7097176720098210128972/

欧几里德算法

用来求两个数的最大公约数的算法。具体如下
int gcd(int a,int b){
if(b == 0) return a;
return gcd(b,a%b);
}

首先看正确性证明，实际上需要证明gcd(a,b)=gcd(b,a%b),我们只要证明gcd(a,b)=gcd(a-b,b)即可，因为可以由此逐步扩展为gcd(a,b) = gcd(a-k*b,b),而 gcd(a-k*b,b)=gcd(a%b,b)。
因为a,b的公约数必然是a-b,b的公约数故 gcd(a,b) <= gcd(a-b,b);另a-b b的公约数也必然是a b的公约数，gcd(a,b) >= gcd(a-b,b).所以gcd(a,b) = gcd(a-b,b)。证明完毕。 read more

转载请注明作者： phylips@bmy 出处： http://duanple.blog.163.com/blog/static/70971767200953105952749/

对于字符串处理，常用的有这么几个工具，kmp，trie树，trie图，后缀树，后缀数组，正则表达式，DFA，NFA。下面就这些算法，数据结果及模型进行下简要的说明，并研究下它们之间的联系。 read more

转载请注明作者： phylips@bmy 出处： http://duanple.blog.163.com/blog/static/7097176720094279641210/

有关各种排序问题的稳定性，时间复杂度，比较次数大概是最经常问到的问题了。另外对于某些公司，对于大数据量的排序问题也会涉及，这样就可能牵扯到外排序。所以这里一并将外排序一般归并过程中所使用的败者树和胜者树，以及置换选择排序大概的描述一下。 read more

1.枚举int值，统计二进制bit中1的个数

1.1记忆化统计1的个数，x^(x-1)直接统计

//enum int comb
int count(unsigned int x){
int i = 0;
while(x != 0){
x = x&(x-1);
i++;
}
return i;
}
void enumComb(int N,int M){
int one[1<<15];
for(int i = 0 ; i < (1 << (N+1)/2) ; i++){
one[i] = count(i);
}
int half = N/2;
for(int i = 1 ; i < (1 << half) ; i++){
for(int j = 1 ; j < (1 << N-half) ; j++){
if(one[i] + one[j] == M){
cout << i << " " << j << endl;
}
}
}
} read more

转载请注明作者： phylps@bmy

出处： http://duanple.blog.163.com/blog/static/70971767200922110494318/

线段树的本质在于将一条线段区间分成一些小的子段，树状数组可以看成一种线段树。对于该区间内的一些线段便可以用这样的一些子段来表示，同时有这样的定理。任何一个长为L的线段都可以用不超过2*logL个子段表示。这样对于插入一个线段便可以在logn时间内解决。而线段树，则是通过这样的使用线段子段的组合，来表示现在出现的线段，而具体的方式则是通过对于一个子段的cout计数来表示的。同时一条线段在树中，只会被真实的表达一次，即只有真正组成它的那些子段会被计数，而当子段已经计数，就可以结束，而子段下的子段不会被重复计数。 read more

线段树就像树状数组一样，通过将一个长为n的段落，划分为O(logn)个子段落，这样就可以通过维护子段落的属性，来求得整个段落的属性。可以证明，任何一个子段在一颗线段树上不会被划分为超过2logn个子段。

一个典型的线段树如下： read more

历史上，Knuth在其<<Sorting and Searching>>一书的第6.2.1节指出：尽管第一个二分搜索算法于1946年就出现，然而第一个完全正确的二分搜索算法直到1962年才出现。

而不经仔细斟酌而写出的一个二分查找经常遭遇off by one或者无限循环的错误。下面将讨论二分查找的理论基础，实现应用，及如何采用何种技术保证写出一个正确的二分程序，让我们免于思考麻烦的边界及结束判断问题。 read more