leetcode题解


刷题总结 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 […]


[leetcode] Additive Number

Additive number is a positive integer whose digits can form additive sequence. A valid additive sequence should contain at least three numbers. Except for the first two numbers, each subsequent number in the sequence must be the sum of the preceding two. For example: “112358” is an additive number because […]