最长公共子序列
最长公共子序列 问题描述 什么是最长公共子序列呢?好比一个数列 S，如果分别是两个或多个已知数列的子序列，且是所有符合此条件序列中最长的，则S 称为已知序列的最长公共子序列。 举个例子，如：有两条随机序列，如 1 3 4 5 5 ，and 2 4 5 5 7 6，则它们的最长公共子序列便是：4 5 5。 分析与解法 解法一 最容易想到的算法是穷举搜索法，即对X的每一个子序列，检查它是否也是Y的子序列，从而确定它是否为X和Y的公共子序列，并且在检查过程中选出最长的公共子序列。X和Y的所有子序列都检查过后即可求出X和Y的最长公共子序列。X的一个子序列相应于下标序列{1, 2, …, m}的一个子序列，因此，X共有2m个不同子序列（Y亦如此，如为2^n），从而穷举搜索法需要指数时间（2^m * 2^n）。 解法二 事实上，最长公共子序列问题也有最优子结构性质。 记： Xi=﹤x1，⋯，xi﹥即X序列的前i个字符 (1≤i≤m)（前缀） Yj=﹤y1，⋯，yj﹥即Y序列的前j个字符 (1≤j≤n)（前缀） 假定Z=﹤z1，⋯，zk﹥∈LCS(X , Y)...
木块砌墙原稿
木块砌墙 作者：July、caopengcs、红色标记。致谢：fuwutu、demo。 时间：二零一三年八月十二日 题目：用 1×1×1, 1×2×1以及2×1×1的三种木块（横绿竖蓝，且绿蓝长度均为2）， 搭建高长宽分别为K × 2^N × 1的墙，不能翻转、旋转（其中，0<=N<=1024，1<=K<=4） 有多少种方案，输出结果 对1000000007取模。 举个例子如给定高度和长度：N=1 K=2，则答案是7，即有7种搭法，如下图所示： 详解：此题很有意思，涉及的知识点也比较多，包括动态规划，快速矩阵幂，状态压缩，排列组合等等都一一考察了个遍。而且跟一个比较经典的矩阵乘法问题类似：即用1 x 2的多米诺骨牌填满M x N的矩形有多少种方案，M<=5，N<2^31，输出答案mod...
求自然数的拆分数
设m,n均为自然数,m可以表示为一些不超过n的自然数之和,试编写函数f(m,n)计算这种表达方式的数目. 123456input: f(5,3)output: 53+2, 3+1+1,2+2+1, 2+1+1+1,1+1+1+1+1 根据题意数据结构用基本数据类型就可以.算法明显使用分治递归最简单. 它只要求数目,不要求列出表达式.找到数目计算方法就行了. 我还是想错了,更方便的方法是使用递归.理解题意也有问题.如果把它当做一个找规律题来做也是可以的,编程实现的运行会非常快,只有O(1)而递归是O($$a^n$$) 分析： 确定递归的终止条件。 第一个终止条件 if (m==1) return 1;这里是说如果m等于1,则函数的返回值为1,显然1只能分解为1,也即表示方式只有一种. 第二个终止条件 if (n==1) return 1;这里是说如果n等于1,则函数的返回值为1,显然无论m多大,n为1时只能表示为m个1之和,也即表示方式只有一种. 当m>n时，f(m,n) 可以递归地分解为两种情况： 当最大加数包含n时，即f(m-n, n) 当最大加数不包含n时，即f(m,...
本章数组和队列的习题
1、不用除法运算 两个数组a[N]，b[N]，其中A[N]的各个元素值已知，现给b[i]赋值，b[i] = a[0]*a[1]*a[2]…*a[N-1]/a[i]； 要求： 1.不准用除法运算 2.除了循环计数值，a[N],b[N]外，不准再用其他任何变量（包括局部变量，全局变量等） 3.满足时间复杂度O(n)，空间复杂度O(1)。 提示：题目要求b[i] = a[0]*a[1]*a[2]…*a[N-1]/a[i] ，相当于求：a[0]*a[1]*a[2]*a[3]…a[i-1]*a[i+1]…*a[N-1]，等价于除掉当前元素a[i]，其他所有元素(a[i]左边部分，和a[i]右边部分)的积。 记left[i]=∏a[k], (k=1…i-1); right=∏a[k], (k=i+1…n)，根据题目描述b[i]=left[i] * right[i]， 对于每一个b[i]初始化为1，left[i]和right[i]两部分可以分开两次相乘，即对于循环变量i=1…n, b[i]=left[i];b[n-i]=right[n-i]，...
矩阵相乘
题目描述 请编程实现矩阵乘法，并考虑当矩阵规模较大时的优化方法。 分析与解法 根据wikipedia上的介绍：两个矩阵的乘法仅当第一个矩阵A的行数和另一个矩阵B的列数相等时才能定义。如A是m×n矩阵，B是n×p矩阵，它们的乘积AB是一个m×p矩阵，它的一个元素其中 1 ≤ i ≤ m, 1 ≤ j ≤ p。 值得一提的是，矩阵乘法满足结合律和分配率，但并不满足交换律，如下图所示的这个例子，两个矩阵交换相乘后，结果变了： 下面咱们来具体解决这个矩阵相乘的问题。 解法一、暴力解法 其实，通过前面的分析，我们已经很明显的看出，两个具有相同维数的矩阵相乘，其复杂度为O(n^3)，参考代码如下： 123456789101112131415//矩阵乘法，3个for循环搞定 void MulMatrix(int** matrixA, int** matrixB, int** matrixC) { for(int i = 0; i < 2; ++i) { for(int j = 0; j <...
程序员如何准备面试中的算法
备战面试中算法的五个步骤 对于立志进一线互联网公司，同时不满足于一辈子干纯业务应用开发，希望在后端做点事情的同学来说，备战面试中的算法，分为哪几个步骤呢？如下： 1、掌握一门编程语言 首先你得确保你已掌握好一门编程语言： C的话，推荐Dennis M. Ritchie & Brian W. Kernighan合著的《C程序设计语言》，和《C和指针》； C++ 则推荐《C++ Primer》，《深度探索C++对象模型》，《Effective C++》； Java推荐《Thinking in Java》，《Core Java》，《Effictive...
算法分析
算法的复杂性体现在时间复杂性和空间复杂性上.一般使用渐进分析法来表达和计算一个算法的复杂性. 渐进分析法 一般表示输入规模与时间关系的函数比较复杂.渐进分析法计算时间时通常只考虑显著改变函数量级的部分,其余部分忽略. 渐进分析法是用另一个（通常更简单的）函数来描述一个函数数量级的渐近上界。 渐进分析法包含三种表示方法:大O表示法,Ω(欧米伽)表示法,Θ(西塔)表示法 大O表示法 对于f(n)，存在正数n0、c，使得当 n>n0 时，始终存在 0 <= f(n) < =c*g(n)，则我们可以用 f(n)=o(g(n))表示。 算法的时间复杂度通常用大O符号表述，定义为T[n] = O(f(n))。称函数T(n)以f(n)为界或者称T(n)受限于f(n)。...
算法概述
从应用范围来看,算法可以分为数值算法和非数值算法.从工作方式来看,算法可以分为串行算法和并行算法. 概念 算法就是对特定问题求解过程的描述. 算法有一下几种性质: 通用性: 对符合输入要求的任意数据能够进行问题求解并能得到正确答案. 有效性 每条指令都能够正确有效的执行,执行结果类型可以预期. 确定性 每一步之后都有关于下一步动作的确切指令 有穷性 算法的执行必须在有限步数内执行完毕. 输入输出性 算法必须要有输入输出,没有输入输出的算法是无意义的. 算法设计 1 ....
线性表
基本概念 线性表是最基本、最简单、也是最常用的一种数据结构。线性表（linear list）是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。这些元素也可称为结点或表目. 在稍复杂的线性表中，一个数据元素可由多个数据项（item）组成，此种情况下常把数据元素称为记录（record），含有大量记录的线性表又称文件（file）。 逻辑结构 用二元组(K,R)来表示线性表,则有: 123K={k0,k1,k2,...,kn-1}R={r}r={<ki,ki+1> |...
荷兰国旗
题目描述 拿破仑席卷欧洲大陆之后，代表自由，平等，博爱的竖色三色旗也风靡一时。荷兰国旗就是一面三色旗（只不过是横向的），自上而下为红白蓝三色。 该问题本身是关于三色球排序和分类的，由荷兰科学家Dijkstra提出。由于问题中的三色小球有序排列后正好分为三类，Dijkstra就想象成他母国的国旗，于是问题也就被命名为荷兰旗问题（Dutch National Flag...