C#面试题汇总(.net SQL几百道).docx

一、二叉树遍历算法设计，涉及指针问题，暂不看
二、设计包含min函数的栈：
题目：定义栈的数据结构，要求添加一个min函数，能够得到栈的最小元素。要求函数min、push以及pop的时间复杂度都是O(1)。
分析：这是去年google的一道面试题。
我看到这道题目时，第一反应就是每次push一个新元素时，将栈里所有逆序元素排序。这样栈顶元素将是最小元素。但由于不能保证最后push进栈的元素最先出栈，这种思路设计的数据结构已经不是一个栈了。（排序不行）
在栈里添加一个成员变量存放最小元素（或最小元素的位置）。每次push一个新元素进栈的时候，如果该元素比当前的最小元素还要小，则更新最小元素。乍一看这样思路挺好的。但仔细一想，该思路存在一个重要的问题：如果当前最小元素被pop出去，如何才能得到下一个最小元素？（添加变量来记录也不行）
因此仅仅只添加一个成员变量存放最小元素（或最小元素的位置）是不够的。我们需要一个辅助栈。每次push一个新元素的时候，同时将最小元素（或最小元素的位置。考虑到栈元素的类型可能是复杂的数据结构，用最小元素的位置将能减少空间消耗）push到辅助栈中；每次pop一个元素出栈的时候，同时pop辅助栈。（辅助栈，记录最小元素的存储位置）

三、求子数组的最大和
题目：输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。
例如输入的数组为1,-2,3,10,-4,7,2,-5，和最大的子数组为3,10,-4,7,2，因此输出为该子数组的和18。
分析：本题最初为2005年浙江大学计算机系的考研题的最后一道程序设计题，在2006年里包括google在内的很多知名公司都把本题当作面试题。由于本题在网络中广为流传，本题也顺利成为2006年程序员面试题中经典中的经典。
如果不考虑时间复杂度，我们可以枚举出所有子数组并求出他们的和。不过非常遗憾的是，由于长度为n的数组有O(n2)个子数组；而且求一个长度为n的数组的和的时间复杂度为O(n)。因此这种思路的时间是O(n3)。
很容易理解，当我们加上一个正数时，和会增加；当我们加上一个负数时，和会减少。如果当前得到的和是个负数，那么这个和在接下来的累加中应该抛弃并重新清零，不然的话这个负数将会减少接下来的和。基于这样的思路，我们可以写出如下代码。
boolFindGreatestSumOfSubArray( int*pData,//anarray unsignedintnLength,//thelengthofarray int&nGreatestSum//thegreatestsumofallsub-arrays){ //iftheinputisinvalid,returnfalse if((pData==NULL)||(nLength==0)) returnfalse; intnCurSum=nGreatestSum=0;
/*逐个向后面加，如果出现了负数的和值，就抛弃，重新开始加
这样也有个问题，如果后面的是负数，加上了，但和依然是正数，则不能说就是最大值，建议再定义一个数组，用来存放每次加后如果是正数的和值，用来最后判断一下取出最大值。然后再和数组中的每一个元素进行对比，如果的确是最大则取之*/ for(unsignedinti=0;i<nLength;++i) { nCurSum+=pData[i]; //ifthecurrentsumisnegative,discardit if(nCurSum<0) nCurSum=0; //ifagreatersumisfound,updatethegreatestsum if(nCurSum>nGreatestSum) nGreatestSum=nCurSum;
}
//ifalldataarenegative,findthegreatestelementinthearray
//输入有一类特殊情况需要特殊处理。当输入数组中所有整数都是负数时，子数组和的最大值就是数组中的最大元素。
if(nGreatestSum==0) { nGreatestSum=pData[0]; for(unsignedinti=1;i<nLength;++i) { if(pData[i]>nGreatestSum) nGreatestSum=pData[i]; } } returntrue;}
四、查找最小的k个元素
分析：这道题最简单的思路莫过于把输入的n个整数排序，这样排在最前面的k个数就是最小的k个数。只是这种思路的时间复杂度为O(nlogn)。我们试着寻找更快的解决思路。
另一种方法：定义一个长度