最小操作数
##最小操作数 题目描述给定一个单词集合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” -> “dot” -> “dog” -> “cog”； “hit” -> “hot” -> “lot” -> “log” ...
最短摘要的生成
最短摘要的生成题目描述你我在百度或谷歌搜索框中敲入本博客名称的前4个字“结构之法”，便能在第一个选项看到本博客的链接，如下图2所示： 图2 谷歌中搜索关键字“结构之法” 在上面所示的图2中，搜索结果“结构之法算法之道-博客频道-CSDN.NET”下有一段说明性的文字：“程序员面试、算法研究、编程艺术、红黑树4大经典原创系列集锦与总结 作者：July–结构之法算法…”，我们把这段文字称为那个搜索结果的摘要，亦即最短摘要。我们的问题是，请问，这个最短摘要是怎么生成的呢? 分析与解法这个问题比较完整正规的说明是： 给定一段产品的英文描述，包含M个英文字母，每个英文单词以空格分隔，无其他标点符号；再给定N个英文单词关键字，请说明思路并编程实现方法 String extractSummary(String description,String[] key...
最长公共子序列
最长公共子序列问题描述什么是最长公共子序列呢?好比一个数列 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)（前缀） ...
木块砌墙原稿
木块砌墙作者：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,...
矩阵相乘
题目描述请编程实现矩阵乘法，并考虑当矩阵规模较大时的优化方法。 分析与解法根据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 < 2;...
程序员如何准备面试中的算法
备战面试中算法的五个步骤对于立志进一线互联网公司，同时不满足于一辈子干纯业务应用开发，希望在后端做点事情的同学来说，备战面试中的算法，分为哪几个步骤呢？如下： 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 ....