刷题总结 3
刷了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保存访问路径,适合返回符合条件的路径。 相关题目:Number of Islands http://www.sunny-song.com/leetcode-number-of-islands/ 2. DP – 动态规划 DFS 和 BFS的复杂度过大,其中一个原因是他们做了过多的重复计算。我们可以通过开辟DP数组,记录历史数据,来避免重复计算。DP的关键是构造状态转移方程。其中有一维DP数组,二维DP数组,根据情况而定。 在复杂的题目中,我们还需要维护两个DP数组,一个为local,储存局部最优解;一个为global,储存全局最优解。 有一个规律,如果题目中出现given you […]