数据结构概述
数据结构就是按一定的逻辑关系组织起来的待处理数据元素的表示和相关操作,包含数据的逻辑结构,存储结构和数据的运算. 数据的逻辑结构 从具体问题中抽象出来的数学模型,反应了事物的组成结构和事物之间的逻辑关系. 逻辑结构可以用一个二元组B = (K,...
数组相关的问题
本章导读 笔试和面试中，除了字符串，另一类出现频率极高的问题便是与数组相关的问题。在阅读完第1章和本第二章后，读者会慢慢了解到解决面试编程题的有几种常用思路。首先一般考虑“万能的”暴力穷举（递归、回溯），如求n个数的全排列或八皇后（N皇后问题）。但因为穷举时间复杂度通常过高，所以需要考虑更好的方法，如分治法（通过分而治之，然后归并），以及空间换时间（如活用哈希表）。 此外，选择合适的数据结构可以显著提升效率，如寻找最小的k个数中，用堆代替数组。 再有，如果题目允许排序，则可以考虑排序。比如，寻找和为定值的两个数中，先排序，然后用前后两个指针往中间扫。而如果如果已经排好序了（如杨氏矩阵查找中），则想想有无必要二分。但是，如果题目不允许排序呢？这个时候，我们可以考虑不改变数列顺序的贪心算法（如最小生成树Prim、Kruskal及最短路dijkstra），或动态规划（如 01背包问题，每一步都在决策）。 最后，注意细节处理，不要忽略边界条件，如字符串转换成整数。
最大连续子数组和
题目描述 输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。 求所有子数组的和的最大值，要求时间复杂度为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,...
本章数组和队列的习题
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 <...