目录基本概念插入排序各种问题求两个整数集合的交集一个二进制，去掉最低位的1计算32位无符号整数二进制中1的个数：编辑距离和最大的连续子序列：最长递增子序列：最长公共子串&最长公共子序列计算一个正整数各位相加，一直到只有一位时的值：基于比较的排序算法下界的证明图概念 基本概念 插入排序 除了直接的插入排序外，还可以将二分查找应用在插入排序里面，可以在寻找新元素该插入的位置时，减少查找的次数。 希尔排序，利用插入排序在有序的情况下O(n)的特性，将列表分组进行排序，保证列表的元素越来越有序，可以达到O(nlogn)的时间复杂度 各种问题 p问题: 存在多项式时间算法的问题 (P：poly...

本文为"Algorithms"一书的笔记 fibonacci 书上给出了另外一种我想不到的解法： #include <stdio.h> #define MAXN 100 int fib[MAXN]; int get_fib(int num); int main(int argc, char *argv[]) { printf("%d\n", get_fib(10)); return 0; } int get_fib(int num) { int i; fib[0] = 0; fib[1] = 1; ...

最近在看快速求fibonaci数列的方法，需要用到快速求幂法，于是参考了这篇文章 ， 做下笔记。 最直观的方法 如果叫我求一个整数的n次幂，我要么用pow，要么写个循环直接相乘。 比如要求： 5 ^ 55 的结果，很明显，要进行54次乘法。要知道，在目前的计算机体系架构中，乘法的计算 是非常慢的。 效率高的求法 有的聪明人（不是我）就想到了减少乘法次数的方法： 5 ^ 2 = 5 * 5 5 ^ 4 = (5 ^ 2) * (5 ^ 2) 5 ^ 8 = (5 ^ 4) * (5 ^ 4) 5 ^ 16 = (5 ^ 8) * (5 ^ 8) 5 ^ 32 = (5 ^ 16) * (5 ^...

动机 看了一本叫做《C/C++面试题》的电子书，里面提到找子字符串的算法，最好的是KMP， 于是开始了KMP之旅！ 在网上看了好几篇中文文章，没一篇看得懂，最后找到了2篇英文文章，深有启发： searching-for-patterns-set-2-kmp-algorithm the-knuth-morris-pratt-algorithm-in-my-own-words 特别是第2篇，让我深刻理解了KMP中的预处理，而第1篇则让我学会了如何用高效的方法 实现预处理。 于是，我也来写一篇文章，用自己的理解来实现KMP算法。 在哪里优化？ 如果要让我写一个程序来找到子串，唯一能想到的方法就是...

基本代数 加法 十进制有一个很傻逼但是很有趣的性质： 任意3个个位数相加的和最多是两位数 事实上，对于任意进制，都有这个性质。 另外一个很有用的性质： 对于一个基数为b的k位数，它能表示的最大数为bk−1b^{k^ {-1}}bk−1 想要知道一个基数为b的数有多少位k，则： k=logb(N+1)k = log_b(N + 1)k=logb​(N+1) 乘法和除法 这里出现了一种神奇的乘法算法，对于计算机来说效率非常高， 引用wikipedia 的例子： Decimal: Binary: 11 3 1011 11 5 6 101 110 2 ...

There is an interview problem. Given a string without duplicate characters, return all permutations of the string. First Try The straightforward idea is using recursive algorithms. We enum all characters for the first position and concatate the permutations of the rest substring. However, the speed ...