From Zero to Hero

最近公共祖先LCA问题 问题描述 求有根树的任意两个节点的最近公共祖先。 分析与解法 解答这个问题之前，咱们得先搞清楚到底什么是最近公共祖先。最近公共祖先简称LCA（Lowest Common Ancestor），所谓LCA，是当给定一个有根树T时，对于任意两个结点u、v，找到一个离根最远的结点x，使得x同时是u和v的祖先，x 便是u、v的最近公共祖先。（参见：http://en.wikipedia.org/wiki/Lowest_common_ancestor ）原问题涵盖一般性的有根树，本文为了简化，多使用二叉树来讨论。 举个例子，如针对下图所示的一棵普通的二叉树来讲： 结点3和结点4的最近公共祖先是结点2，即LCA（3 4）=2 。在此，需要注意到当两个结点在同一棵子树上的情况，如结点3和结点2的最近公共祖先为2，即...

R树：处理空间存储问题 R树简介 984年，加州大学伯克利分校的Guttman发表了一篇题为“R-trees: a dynamic index structure for spatial...

本章堆栈树图相关的习题 1、附近地点搜索 找一个点集中与给定点距离最近的点，同时，给定的二维点集都是固定的，查询可能有很多次，例如，坐标(39.91, 116.37)附近500米内有什么餐馆，那么让你来设计，该怎么做？ 提示：可以建立R树进行二维搜索，或使用GeoHash算法解决。 2、最小操作数 给定一个单词集合Dict，其中每个单词的长度都相同。现从此单词集合Dict中抽取两个单词A、B，我们希望通过若干次操作把单词A变成单词B，每次操作可以改变单词的一个字母，同时，新产生的单词必须是在给定的单词集合Dict中。求所有行得通步数最少的修改方法。 举个例子如下： Given: A = “hit” B = “cog” Dict = [“hot”,“dot”,“dog”,“lot”,“log”] Return [ [“hit”,“hot”,“dot”,“dog”,“cog”], [“hit”,“hot”,“lot”,“log”,“cog”] ] 即把字符串A = "hit"转变成字符串B = “cog”，有以下两种可能： “hit” -> “hot”...

有序数组的查找 题目描述 给定一个有序的数组，查找某个数是否在数组中，请编程实现。 分析与解法 一看到数组本身已经有序，我想你可能反应出了要用二分查找，毕竟二分查找的适用条件就是有序的。那什么是二分查找呢？ 二分查找可以解决（预排序数组的查找）问题：只要数组中包含T（即要查找的值），那么通过不断缩小包含T的范围，最终就可以找到它。其算法流程如下： 一开始，范围覆盖整个数组。 将数组的中间项与T进行比较，如果T比数组的中间项要小，则到数组的前半部分继续查找，反之，则到数组的后半部分继续查找。 如此，每次查找可以排除一半元素，范围缩小一半。就这样反复比较，反复缩小范围，最终就会在数组中找到T，或者确定原以为T所在的范围实际为空。 对于包含N个元素的表，整个查找过程大约要经过log(2)N次比较。 此时，可能有不少读者心里嘀咕，不就二分查找么，太简单了。 然《编程珠玑》的作者Jon...

...

出现次数超过一半的数字 题目描述 题目：数组中有一个数字出现的次数超过了数组长度的一半，找出这个数字。 分析与解法 一个数组中有很多数，现在我们要找出其中那个出现次数超过总数一半的数字，怎么找呢？大凡当我们碰到某一个杂乱无序的东西时，我们人的内心本质期望是希望把它梳理成有序的。所以，我们得分两种情况来讨论，无序和有序。 解法一 如果无序，那么我们是不是可以先把数组中所有这些数字先进行排序（至于排序方法可选取最常用的快速排序）。排完序后，直接遍历，在遍历整个数组的同时统计每个数字的出现次数，然后把那个出现次数超过一半的数字直接输出，题目便解答完成了。总的时间复杂度为O(nlogn +...

本章导读 学习一个算法，可分为3个步骤：首先了解算法本身解决什么问题，然后学习它的解决策略，最后了解某些相似算法之间的联系。例如图算法中， 广搜是一层一层往外遍历，寻找最短路径，其策略是采取队列的方法。 最小生成树是最小代价连接所有点，其策略是贪心，比如Prim的策略是贪心+权重队列。 Dijkstra是寻找单源最短路径，其策略是贪心+非负权重队列。 Floyd是多结点对的最短路径，其策略是动态规划。 而贪心和动态规划是有联系的，贪心是“最优子结构+局部最优”，动态规划是“最优独立重叠子结构+全局最优”。一句话理解动态规划，则是枚举所有状态，然后剪枝，寻找最优状态，同时将每一次求解子问题的结果保存在一张“表格”中，以后再遇到重叠的子问题，从表格中保存的状态中查找（俗称记忆化搜索）。

字符串编辑距离 题目描述 给定一个源串和目标串，能够对源串进行如下操作： 在给定位置上插入一个字符 替换任意字符 删除任意字符 写一个程序，返回最小操作数，使得对源串进行这些操作后等于目标串，源串和目标串的长度都小于2000。 分析与解法 此题常见的思路是动态规划，假如令dp[i][j] 表示源串S[0…i] 和目标串T[0…j] 的最短编辑距离，其边界：dp[0][j] = j，dp[i][0] = i，那么我们可以得出状态转移方程： dp[i][j] =min{ dp[i-1][j] + 1 , S[i]不在T[0…j]中 dp[i-1][j-1] + 1/0 , S[i]在T[j] dp[i][j-1] + 1 , S[i]在T[0…j-1]中 } 接下来，咱们重点解释下上述3个式子的含义 关于dp[i-1][j] + 1, s.t....

格子取数问题 题目描述 有n*n个格子，每个格子里有正数或者0，从最左上角往最右下角走，只能向下和向右，一共走两次（即从左上角走到右下角走两趟），把所有经过的格子的数加起来，求最大值SUM，且两次如果经过同一个格子，则最后总和SUM中该格子的计数只加一次。 分析与解法 初看到此题，因为要让两次走下来的路径总和最大，读者可能最初想到的思路可能是让每一次的路径都是最优的，即不顾全局，只看局部，让第一次和第二次的路径都是最优。 但问题马上就来了，虽然这一算法保证了连续的两次走法都是最优的，但却不能保证总体最优，相应的反例也不难给出，请看下图： 上图中，图一是原始图，那么我们有以下两种走法可供我们选择： 如果按照上面的局部贪优走法，那么第一次势必会如图二那样走，导致的结果是第二次要么取到2，要么取到3， 但若不按照上面的局部贪优走法，那么第一次可以如图三那样走，从而第二次走的时候能取到2 4...

交替字符串 题目描述 输入三个字符串s1、s2和s3，判断第三个字符串s3是否由前两个字符串s1和s2交错而成，即不改变s1和s2中各个字符原有的相对顺序，例如当s1 = “aabcc”，s2 = “dbbca”，s3 =...