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
...
6.01
关联式容器 一般来说，STL容器分为： 序列式容器(vector/list/deque/stack/queue/heap)，和关联式容器。 其中，关联式容器又分为set(集合)和map(映射表)两大类，以及这两大类的衍生体multiset(多键集合)和multimap(多键映射表)，这些容器均以RB-tree（red-black tree,...
5.01
最大连续乘积子串 题目描述 给一个浮点数序列，取最大乘积连续子串的值，例如 -2.5，4，0，3，0.5，8，-1，则取出的最大乘积连续子串为3，0.5，8。也就是说，上述数组中，3 0.5 8这3个数的乘积30.58=12是最大的，而且是连续的。 分析与解法 此最大乘积连续子串与最大乘积子序列不同，请勿混淆，前者子串要求连续，后者子序列不要求连续。也就是说，最长公共子串（Longest CommonSubstring）和最长公共子序列（LongestCommon Subsequence，LCS）是： 子串（Substring）是串的一个连续的部分， 子序列（Subsequence）则是从不改变序列的顺序，而从序列中去掉任意的元素而获得的新序列； 更简略地说，前者（子串）的字符的位置必须连续，后者（子序列LCS）则不必。比如字符串“ acdfg ”同“ akdfc ”的最长公共子串为“ df ”，而它们的最长公共子序列LCS是“ adf...
6.03
simhash算法 方法介绍 背景 如果某一天，面试官问你如何设计一个比较两篇文章相似度的算法？可能你会回答几个比较传统点的思路： 一种方案是先将两篇文章分别进行分词，得到一系列特征向量，然后计算特征向量之间的距离（可以计算它们之间的欧氏距离、海明距离或者夹角余弦等等），从而通过距离的大小来判断两篇文章的相似度。 另外一种方案是传统hash，我们考虑为每一个web文档通过hash的方式生成一个指纹（finger print）。 下面，我们来分析下这两种方法。 采取第一种方法，若是只比较两篇文章的相似性还好，但如果是海量数据呢，有着数以百万甚至亿万的网页，要求你计算这些网页的相似度。你还会去计算任意两个网页之间的距离或夹角余弦么？想必你不会了。 而第二种方案中所说的传统加密方式md5，其设计的目的是为了让整个分布尽可能地均匀，但如果输入内容一旦出现哪怕轻微的变化，hash值就会发生很大的变化。 举个例子，我们假设有以下三段文本： the cat sat on the mat the cat sat on a mat we all scream for ice...
6.02
...
6.04
外排序 方法介绍 所谓外排序，顾名思义，即是在内存外面的排序，因为当要处理的数据量很大，而不能一次装入内存时，此时只能放在读写较慢的外存储器（通常是硬盘）上。 外排序通常采用的是一种“排序-归并”的策略。 在排序阶段，先读入能放在内存中的数据量，将其排序输出到一个临时文件，依此进行，将待排序数据组织为多个有序的临时文件； 尔后在归并阶段将这些临时文件组合为一个大的有序文件，也即排序结果。 假定现在有20个数据的文件A：{5 11 0 18 4 14 9 7 6 8 12 17 16 13 19 10 2 1 3 15}，但一次只能使用仅装4个数据的内容，所以，我们可以每趟对4个数据进行排序，即5路归并，具体方法如下述步骤： 我们先把“大”文件A，分割为a1，a2，a3，a4，a5等5个小文件，每个小文件4个数据 a1文件为：5 11 0 18 a2文件为：4 14 9 7 a3文件为：6 8 12 17 a4文件为：16 13 19 10 a5文件为：2 1 3 15 然后依次对5个小文件分别进行排序 a1文件完成排序后：0 5 11...