最大连续子数组和
题目描述 输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。 求所有子数组的和的最大值，要求时间复杂度为O(n)。 例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2， 因此输出为该子数组的和18。 分析与解法 解法一 求一个数组的最大子数组和，我想最直观最野蛮的办法便是，三个for循环三层遍历，求出数组中每一个子数组的和，最终求出这些子数组的最大的一个值。 令currSum[i, …, j]为数组A中第i个元素到第j个元素的和（其中0 <= i <= j < n），maxSum为最终求到的最大连续子数组的和。 且当全是负数的情况时，我们可以让程序返回0，也可以让程序返回最大的那个负数，这里，我们让程序返回最大的那个负数。 参考代码如下： 1234567891011121314151617181920int MaxSubArray(int* A, int n){ int maxSum = a[0]; ...
最小操作数
##最小操作数 题目描述 给定一个单词集合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)（前缀） 假定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,...
矩阵相乘
题目描述 请编程实现矩阵乘法，并考虑当矩阵规模较大时的优化方法。 分析与解法 根据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、不用除法运算 两个数组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]，...
程序员如何准备面试中的算法
备战面试中算法的五个步骤 对于立志进一线互联网公司，同时不满足于一辈子干纯业务应用开发，希望在后端做点事情的同学来说，备战面试中的算法，分为哪几个步骤呢？如下： 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)。...