4.01
有序数组的查找 题目描述 给定一个有序的数组，查找某个数是否在数组中，请编程实现。 分析与解法 一看到数组本身已经有序，我想你可能反应出了要用二分查找，毕竟二分查找的适用条件就是有序的。那什么是二分查找呢？ 二分查找可以解决（预排序数组的查找）问题：只要数组中包含T（即要查找的值），那么通过不断缩小包含T的范围，最终就可以找到它。其算法流程如下： 一开始，范围覆盖整个数组。 将数组的中间项与T进行比较，如果T比数组的中间项要小，则到数组的前半部分继续查找，反之，则到数组的后半部分继续查找。 如此，每次查找可以排除一半元素，范围缩小一半。就这样反复比较，反复缩小范围，最终就会在数组中找到T，或者确定原以为T所在的范围实际为空。 对于包含N个元素的表，整个查找过程大约要经过log(2)N次比较。 此时，可能有不少读者心里嘀咕，不就二分查找么，太简单了。 然《编程珠玑》的作者Jon...
行列递增矩阵的查找
...
4.03
出现次数超过一半的数字 题目描述 题目：数组中有一个数字出现的次数超过了数组长度的一半，找出这个数字。 分析与解法 一个数组中有很多数，现在我们要找出其中那个出现次数超过总数一半的数字，怎么找呢？大凡当我们碰到某一个杂乱无序的东西时，我们人的内心本质期望是希望把它梳理成有序的。所以，我们得分两种情况来讨论，无序和有序。 解法一 如果无序，那么我们是不是可以先把数组中所有这些数字先进行排序（至于排序方法可选取最常用的快速排序）。排完序后，直接遍历，在遍历整个数组的同时统计每个数字的出现次数，然后把那个出现次数超过一半的数字直接输出，题目便解答完成了。总的时间复杂度为O(nlogn +...
5
本章导读 学习一个算法，可分为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....
5.03
格子取数问题 题目描述 有n*n个格子，每个格子里有正数或者0，从最左上角往最右下角走，只能向下和向右，一共走两次（即从左上角走到右下角走两趟），把所有经过的格子的数加起来，求最大值SUM，且两次如果经过同一个格子，则最后总和SUM中该格子的计数只加一次。 分析与解法 初看到此题，因为要让两次走下来的路径总和最大，读者可能最初想到的思路可能是让每一次的路径都是最优的，即不顾全局，只看局部，让第一次和第二次的路径都是最优。 但问题马上就来了，虽然这一算法保证了连续的两次走法都是最优的，但却不能保证总体最优，相应的反例也不难给出，请看下图： 上图中，图一是原始图，那么我们有以下两种走法可供我们选择： 如果按照上面的局部贪优走法，那么第一次势必会如图二那样走，导致的结果是第二次要么取到2，要么取到3， 但若不按照上面的局部贪优走法，那么第一次可以如图三那样走，从而第二次走的时候能取到2 4...
5.04
交替字符串 题目描述 输入三个字符串s1、s2和s3，判断第三个字符串s3是否由前两个字符串s1和s2交错而成，即不改变s1和s2中各个字符原有的相对顺序，例如当s1 = “aabcc”，s2 = “dbbca”，s3 =...
5.06
最长递增子序列 题目描述 给定一个长度为N的数组a0,a1,a2…,an-1，找出一个最长的单调递增子序列（注：递增的意思是对于任意的i<j，都满足ai<aj，此外子序列的意思是不要求连续，顺序不乱即可）。例如：给定一个长度为6的数组A{5， 6， 7， 1， 2， 8}，则其最长的单调递增子序列为{5，6，7，8}，长度为4。 分析与解法 解法一：转换为最长公共子序列问题 比如原数组为 A{5， 6， 7， 1， 2， 8}， 当我们对这个数组进行排序后，排序后的数组为： A‘{1， 2， 5， 6， 7，...
5.1
本章动态规划的习题 1.子序列个数 子序列的定义：对于一个序列a=a[1],a[2],…a[n]，则非空序列a’=a[p1],a[p2]…a[pm]为a的一个子序列 其中1<=p1<p2<…<pm<=n。 例如：4,14,2,3和14,1,2,3都为4,13,14,1,2,3的子序列。 对于给出序列a，有些子序列可能是相同的，这里只算做1个。 要求输出a的不同子序列的数量。 2.数塔取数问题 一个高度为N的由正整数组成的三角形，从上走到下，求经过的数字和的最大值。 每次只能走到下一层相邻的数上，例如从第3层的6向下走，只能走到第4层的2或9上。 5 8 4 3 6 9 7 2 9 5 例子中的最优方案是：5 + 8 + 6 + 9 = 28。 3.最长公共子序列 什么是最长公共子序列呢?好比一个数列 S，如果分别是两个或多个已知数列的子序列，且是所有符合此条件序列中最长的，则S 称为已知序列的最长公共子序列。 举个例子，如：有两条随机序列，如 1 3 4 5 5 ，and 2 4 5 5 7 6，则它们的最长公共子序列便是：4 5...
6
...