程序员面试题精选100题Word文档下载推荐.docx
《程序员面试题精选100题Word文档下载推荐.docx》由会员分享，可在线阅读，更多相关《程序员面试题精选100题Word文档下载推荐.docx（154页珍藏版）》请在冰点文库上搜索。
4=6=8=10=12=14=16。
分析：
本题是微软的面试题。
很多与树相关的题目都是用递归的思路来解决，本题也不例外。
下面我们用两种不同的递归思路来分析。
思路一：
当我们到达某一结点准备调整以该结点为根结点的子树时，先调整其左子树将左子树转换成一个排好序的左子链表，再调整其右子树转换右子链表。
最近链接左子链表的最右结点（左子树的最大结点）、当前结点和右子链表的最左结点（右子树的最小结点）。
从树的根结点开始递归调整所有结点。
思路二：
我们可以中序遍历整棵树。
按照这个方式遍历树，比较小的结点先访问。
如果我们每访问一个结点，假设之前访问过的结点已经调整成一个排序双向链表，我们再把调整当前结点的指针将其链接到链表的末尾。
当所有结点都访问过之后，整棵树也就转换成一个排序双向链表了。
参考代码：
首先我们定义二元查找树结点的数据结构如下：
structBSTreeNode//anodeinthebinarysearchtree
{
intm_nValue;
//valueofnode
BSTreeNode*m_pLeft;
//leftchildofnode
BSTreeNode*m_pRight;
//rightchildofnode
};
思路一对应的代码：
///////////////////////////////////////////////////////////////////////
//Covertasubbinary-search-treeintoasorteddouble-linkedlist
//Input:
pNode-theheadofthesubtree
//asRight-whetherpNodeistherightchildofitsparent
//Output:
ifasRightistrue,returntheleastnodeinthesub-tree
//elsereturnthegreatestnodeinthesub-tree
BSTreeNode*ConvertNode（BSTreeNode*pNode,boolasRight）
{
if（!
pNode）
returnNULL;
BSTreeNode*pLeft=NULL;
BSTreeNode*pRight=NULL;
//Converttheleftsub-tree
if（pNode->
m_pLeft）
pLeft=ConvertNode（pNode->
m_pLeft,false）;
//Connectthegreatestnodeintheleftsub-treetothecurrentnode
if（pLeft）
pLeft->
m_pRight=pNode;
pNode->
m_pLeft=pLeft;
}
//Converttherightsub-tree
m_pRight）
pRight=ConvertNode（pNode->
m_pRight,true）;
//Connecttheleastnodeintherightsub-treetothecurrentnode
if（pRight）
m_pRight=pRight;
pRight->
m_pLeft=pNode;
BSTreeNode*pTemp=pNode;
//Ifthecurrentnodeistherightchildofitsparent,
//returntheleastnodeinthetreewhoserootisthecurrentnode
if（asRight）
while（pTemp->
pTemp=pTemp->
m_pLeft;
//Ifthecurrentnodeistheleftchildofitsparent,
//returnthegreatestnodeinthetreewhoserootisthecurrentnode
else
m_pRight;
returnpTemp;
}
//Covertabinarysearchtreeintoasorteddouble-linkedlist
theheadoftree
theheadofsorteddouble-linkedlist
BSTreeNode*Convert（BSTreeNode*pHeadOfTree）
//Aswewanttoreturntheheadofthesorteddouble-linkedlist,
//wesetthesecondparametertobetrue
returnConvertNode（pHeadOfTree,true）;
思路二对应的代码：
//pLastNodeInList-thetailofthedouble-linkedlist
voidConvertNode（BSTreeNode*pNode,BSTreeNode*&
pLastNodeInList）
if（pNode==NULL）
return;
BSTreeNode*pCurrent=pNode;
if（pCurrent->
m_pLeft!
=NULL）
ConvertNode（pCurrent->
m_pLeft,pLastNodeInList）;
//Putthecurrentnodeintothedouble-linkedlist
pCurrent->
m_pLeft=pLastNodeInList;
if（pLastNodeInList!
pLastNodeInList->
m_pRight=pCurrent;
pLastNodeInList=pCurrent;
m_pRight!
m_pRight,pLastNodeInList）;
pHeadOfTree-theheadoftree
BSTreeNode*Convert_Solution1（BSTreeNode*pHeadOfTree）
BSTreeNode*pLastNodeInList=NULL;
ConvertNode（pHeadOfTree,pLastNodeInList）;
//Gettheheadofthedouble-linkedlist
BSTreeNode*pHeadOfList=pLastNodeInList;
while（pHeadOfList&
&
pHeadOfList->
pHeadOfList=pHeadOfList->
returnpHeadOfList;
（02）设计包含min函数的栈
题目：
定义栈的数据结构，要求添加一个min函数，能够得到栈的最小元素。
要求函数min、push以及pop的时间复杂度都是O
（1）。
分析：
这是去年google的一道面试题。
我看到这道题目时，第一反应就是每次push一个新元素时，将栈里所有逆序元素排序。
这样栈顶元素将是最小元素。
但由于不能保证最后push进栈的元素最先出栈，这种思路设计的数据结构已经不是一个栈了。
在栈里添加一个成员变量存放最小元素（或最小元素的位置）。
每次push一个新元素进栈的时候，如果该元素比当前的最小元素还要小，则更新最小元素。
乍一看这样思路挺好的。
但仔细一想，该思路存在一个重要的问题：
如果当前最小元素被pop出去，如何才能得到下一个最小元素？
因此仅仅只添加一个成员变量存放最小元素（或最小元素的位置）是不够的。
我们需要一个辅助栈。
每次push一个新元素的时候，同时将最小元素（或最小元素的位置。
考虑到栈元素的类型可能是复杂的数据结构，用最小元素的位置将能减少空间消耗）push到辅助栈中；
每次pop一个元素出栈的时候，同时pop辅助栈。
#include<
deque>
assert.h>
template<
typenameT>
classCStackWithMin
public:
CStackWithMin（void）{}
virtual~CStackWithMin（void）{}
T&
top（void）;
constT&
top（void）const;
voidpush（constT&
value）;
voidpop（void）;
min（void）const;
private:
T>
m_data;
//theelementsofstack
size_t>
m_minIndex;
//theindicesofminimumelements
};
//getthelastelementofmutablestack
CStackWithMin<
T>
:
top（）
returnm_data.back（）;
//getthelastelementofnon-mutablestack
top（）const
//insertanelmentattheendofstack
voidCStackWithMin<
push（constT&
value）
//appendthedataintotheendofm_data
m_data.push_back（value）;
//settheindexofminimumelmentinm_dataattheendofm_minIndex
if（m_minIndex.size（）==0）
m_minIndex.push_back（0）;
if（value<
m_data[m_minIndex.back（）]）
m_minIndex.push_back（m_data.size（）-1）;
else
m_minIndex.push_back（m_minIndex.back（））;
//ereasetheelementattheendofstack
pop（）
//popm_data
m_data.pop_back（）;
//popm_minIndex
m_minIndex.pop_back（）;
//gettheminimumelementofstack
min（）const
assert（m_data.size（）>
0）;
assert（m_minIndex.size（）>
returnm_data[m_minIndex.back（）];
举个例子演示上述代码的运行过程：
步骤
数据栈
辅助栈
最小值
1.push3
3
0
3
2.push4
3,4
0,0
3.push2
3,4,2
0,0,2
2
4.push1
3,4,2,1
0,0,2,3
1
5.pop
6.pop
7.push0
3,4,0
0
讨论：
如果思路正确，编写上述代码不是一件很难的事情。
但如果能注意一些细节无疑能在面试中加分。
比如我在上面的代码中做了如下的工作：
∙
用模板类实现。
如果别人的元素类型只是int类型，模板将能给面试官带来好印象；
两个版本的top函数。
在很多类中，都需要提供const和非const版本的成员访问函数；
min函数中assert。
把代码写的尽量安全是每个软件公司对程序员的要求；
添加一些注释。
注释既能提高代码的可读性，又能增加代码量，何乐而不为？
总之，在面试时如果时间允许，尽量把代码写的漂亮一些。
说不定代码中的几个小亮点就能让自己轻松拿到心仪的Offer。
（03）－求子数组的最大和
输入一个整形数组，数组里有正数也有负数。
数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。
求所有子数组的和的最大值。
要求时间复杂度为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）。
很容易理解，当我们加上一个正数时，和会增加；
当我们加上一个负数时，和会减少。
如果当前得到的和是个负数，那么这个和在接下来的累加中应该抛弃并重新清零，不然的话这个负数将会减少接下来的和。
基于这样的思路，我们可以写出如下代码。
/////////////////////////////////////////////////////////////////////////////
//Findthegreatestsumofallsub-arrays
//Returnvalue:
iftheinputisvalid,returntrue,otherwisereturnfalse
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;
{
if（pData[i]>
nGreatestSum=pData[i];
}
returntrue;
}
上述代码中有两点值得和大家讨论一下：
函数的返回值不是子数组和的最大值，而是一个判断输入是否有效的标志。
如果函数返回值的是子数组和的最大值，那么当输入一个空指针是应该返回什么呢？
返回0？
那这个函数的用户怎么区分输入无效和子数组和的最大值刚好是0这两中情况呢？
基于这个考虑，本人认为把子数组和的最大值以引用的方式放到参数列表中，同时让函数返回一个函数是否正常执行的标志。
输入有一类特殊情况需要特殊处理。
当输入数组中所有整数都是负数时，子数组和的最大值就是数组中的最大元素。
（04）－在二元树中找出和为某一值的所有路径
输入一个整数和一棵二元树。
从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。
打印出和与输入整数相等的所有路径。
例如输入整数22和如下二元树
5
12
/
7
则打印出两条路径：
10,12和10,5,7。
二元树结点的数据结构定义为：
structBinaryTreeNode//anodeintheb
升级会员 