刷了Leetcode 308道题和lintcode的一些题，有一些总结和经验，写在这里。

0. General Sense

Trade off between space and time

如果时间复杂度要求更高的话，我们就要尝试开辟更多的空间来做trade off。比如从DFS改到DP，开辟DP数组；或者由linear search改成hash table。

Corner cases

Overflow, duplicate, negative integers in array, empty input, off-by-one error, etc..

1. BFS & DFS – 广度优先搜索，深度优先搜索

任何问题都可以用BFS或DFS来解，因为两者的本质是遍历解空间，尝试所有的可能的组合，简单粗暴。但是它们的复杂度会很大，最坏可能达到n^n。

两个算法最终都会遍历整个解空间，不同点在于遍历顺序。BFS会由中心向四周扩散来遍历，适合寻找最短路径的长度；DFS会先一条路走到底，并通过call stack保存访问路径，适合返回符合条件的路径。

BFS & DFS in graph

BFS & DFS in matrix

2. DP – 动态规划

DFS 和 BFS的复杂度过大，其中一个原因是他们做了过多的重复计算。我们可以通过开辟DP数组，记录历史数据，来避免重复计算。DP的关键是构造状态转移方程。其中有一维DP数组，二维DP数组，根据情况而定。

在复杂的题目中，我们还需要维护两个DP数组，一个为local，储存局部最优解；一个为global，储存全局最优解。

有一个规律，如果题目中出现given you an array of numbers/a string/a matrix. 多半是可以用DP来解的。因为DP在数组和矩阵中是比较好找到状态转移方程的。相反地，在图中和树中找状态转移方程就比较困难。

相关题目：Buy and Sell Stock IV http://www.sunny-song.com/leetcode-best-time-to-buy-and-sell-stock-iv/

3. Binary Search

Binary Search的前提是输入数据必须是sort过的。其实Binary Search很容易写出bug，陷入死循环或run time error。这里给出一个Binary Search的模板

int binarySearch(vector<int>& nums, int target){
    int low = 0;
    int high = nums.size() - 1; // both low and high are inclusive
    while(low < high){
        int mid = low + (high - low) / 2; // avoid overflow
        if(nums[mid] < target){
            low = mid + 1; // mid may be equal to low, so we set low to mid + 1
        }else{
            high = mid;
        }
    }
    return high;
}

上述代码中，我们返回target在nums array中的index，如果target不存在的话，返回小于并最接近target的数字（极端情况下返回大于且最接近target的数字，如果数组中所有数都比target大的话）。

这个循环中有几个invariant：

1. low和high指针指向的元素都一直有效，inclusive。不会数组越界
2. 由于int除法的特性，mid有可能等于low，为了避免陷入死循环，我们让low=mid+1。如果反过来，我们让high=mid-1; low = mid的话，就会陷入死循环。
3. 退出循环时，low==high

验证一个binarysearch是否是bugfree的，可以check if there is only one element in the array/ only two elements in the array. These two kinds of checking would cover all possibilities in run time, since all of the possible inputs would lead to one or two elements situation.

相关题目： Search 2D Matrix II http://www.sunny-song.com/leetcode-search-2d-matrix-ii/

4. Greedy – 贪心算法

贪婪算法每步找寻局部最优解，然后进行下一步搜索。这样的算法是冒险的，因为很有可能最终找到的结果只是局部最优解，而不是全局最优解。K-means聚类就有这样的问题，所以工业中往往run K-means algorithm for several hundred times希望通过大力出奇迹的方式避免陷入局部最优解。

但有时，Greedy也会得到最优解，比如这题：http://www.sunny-song.com/leetcode-jump-game/

5. Topological Sort – 拓扑排序

course selection

Alien Dictionary

6. 递归调用改成循环

参见：http://www.sunny-song.com/convert-recursion-algorithms-iteration-version/

6. Leetcode所不能cover的topic

概率相关的问题，因为OJ比较难判断涉及随机数的算法。比如蒙特卡洛(Monte Carlo method)，Reservoir Sampling，Shuffle Deck等。