关于最长公共子序列（LCS） 最长公共子序列和最长公共子串是有区别的，之前我一直把它们混淆。 最长公共子串举例：假设S1={A,D,C,B,E,X,Q}，S2={H,P,D,C,B,E,M,L} 那么它们的最长公共子串就是{D,C,B,E}。这是我通常理解的东西。 最长公共子序列。 最长公共子序列举例：假设S1={A,B,C,A,D,A,B}，S2={B,A,C,D,B,A}，那么它们的LCS就是{B,A,D,B}。 求解最长公共子序列 这是一个动态规划问题。如何求解最长公共子序列（以下用LCS代替）呢？我们假设已…

题目1 滑动窗口的最大值 题目描述 给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， …

大整数乘法 1.算法原理 如果我们想要计算两个较大的数字相乘的时候，由于计算机硬件限制可能无法计算，因此我们可以将每个乘数用加法和乘法做分解，当分解到每个因子只是一位数的时候，乘法就很简单了，这也是一种分治法。 （1）分解：首先将2个大整数a（n位）、b（m位）分解为两部分： ah al   bh bl 然后， 其中ah、al为n/2位，bh、bl为m/2位。两个大整数a、b相乘转换成了4个乘法运算，而乘数的位数变为了原来的一半。 （2）求解子问题。继续分解每个乘法运算，直到分解有一个乘数为1位数时停止分…

二分法 1.算法设计 用一维数组S[]存储该有序序列，设变量low和high表示查找范围的下界和上界，middle表示查找范围的中间位置，x为特定的查找元素。 （1）初始化。令low=0，high=n-1。 （2）middle=(high-low)/2。 （3）判断low<=high是否成立，若成立，到第4步，否则算法结束。 （4）判断S[middle]与x的关系：若S[middle]>x，则x位于low~middle之间，令high=middle-1,；若S[middle]<x，则x位于midd…

  1.若一个字符串长度为n，那么它的子串数目有n(n+1)/2+1个。 2.设S为一个长度为n的字符串,其中的字符各不相同,则S中的互异的非平凡子串(非空且不同于S本身)的个数为(n²/2)+(n/2)-1 3.关于puts和putchar （1）puts()函数用来向标准输出设备（屏幕）输出字符串并换行，具体为：把字符串输出到标准输出设备，将'\0'转换为回车换行。其调用方式为，puts(s)；其中s为字符串字符（字符串数组名或字符串指针）。 （2）.putchar()函数作用是向终端输出一个字符。其…

Dijkstra算法 待后续补充 哈夫曼编码 1.算法介绍 哈夫曼编码采取的贪心策略是每次从树的集合中取出没有双亲且权值最小的两个树为左右子树，构造一棵新树，新树根结点的权值为其左右孩子的结点权值之和，将新树插入到树的集合之中。 求解步骤如下： （1）确定合适的数据结构，编写程序前要考虑： ①哈夫曼树中没有度为1的结点，则一棵有n个叶子结点的哈夫曼树共有2n-1个结点（n-1次合并，每次产生一个结点）； ②构成哈夫曼树后，为求编码，需从叶子结点除法走一条从叶子到根的路径。 译码需要从跟除法走一条从根到叶子的路径，那…

1.修改程序清单11.15，使之将一系列连续的随机漫步者位置写入到文件中。对于每个位置，用步号进行标示。另外，让该程序将初始条件（目标距离和步长）以及结果小结写入到该文件中。 #include <iostream> #include <cstdlib> #include <ctime> #include <fstream> #include "vector.h" using namespace std; using VECTOR::Vector; int main()…