算法.docx
《算法.docx》由会员分享，可在线阅读，更多相关《算法.docx（81页珍藏版）》请在冰点文库上搜索。
算法
程序员面试题精选（01）－把二元查找树转变成排序的双向链表
题目：
输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。
要求不能创建任何新的结点，只调整指针的指向。
比如将二元查找树
10
/ \
6 14
/ \ / \
4 8 12 16
转换成双向链表
4=6=8=10=12=14=16。
分析：
本题是微软的面试题。
很多与树相关的题目都是用递归的思路来解决，本题也不例外。
下面我们用两种不同的递归思路来分析。
思路一：
当我们到达某一结点准备调整以该结点为根结点的子树时，先调整其左子树将左子树转换成一个排好序的左子链表，再调整其右子树转换右子链表。
最近链接左子链表的最右结点（左子树的最大结点）、当前结点和右子链表的最左结点（右子树的最小结点）。
从树的根结点开始递归调整所有结点。
思路二：
我们可以中序遍历整棵树。
按照这个方式遍历树，比较小的结点先访问。
如果我们每访问一个结点，假设之前访问过的结点已经调整成一个排序双向链表，我们再把调整当前结点的指针将其链接到链表的末尾。
当所有结点都访问过之后，整棵树也就转换成一个排序双向链表了。
参考代码：
首先我们定义二元查找树结点的数据结构如下：
structBSTreeNode//anodeinthebinarysearchtree
{
int m_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
if（pNode->m_pRight）
pRight=ConvertNode（pNode->m_pRight,true）;
//Connecttheleastnodeintherightsub-treetothecurrentnode
if（pRight）
{
pNode->m_pRight=pRight;
pRight->m_pLeft=pNode;
}
BSTreeNode*pTemp=pNode;
//Ifthecurrentnodeistherightchildofitsparent,
//returntheleastnodeinthetreewhoserootisthecurrentnode
if（asRight）
{
while（pTemp->m_pLeft）
pTemp=pTemp->m_pLeft;
}
//Ifthecurrentnodeistheleftchildofitsparent,
//returnthegreatestnodeinthetreewhoserootisthecurrentnode
else
{
while（pTemp->m_pRight）
pTemp=pTemp->m_pRight;
}
returnpTemp;
}
///////////////////////////////////////////////////////////////////////
//Covertabinarysearchtreeintoasorteddouble-linkedlist
//Input:
theheadoftree
//Output:
theheadofsorteddouble-linkedlist
///////////////////////////////////////////////////////////////////////
BSTreeNode*Convert（BSTreeNode*pHeadOfTree）
{
//Aswewanttoreturntheheadofthesorteddouble-linkedlist,
//wesetthesecondparametertobetrue
returnConvertNode（pHeadOfTree,true）;
}
思路二对应的代码：
///////////////////////////////////////////////////////////////////////
//Covertasubbinary-search-treeintoasorteddouble-linkedlist
//Input:
pNode- theheadofthesubtree
// pLastNodeInList-thetailofthedouble-linkedlist
///////////////////////////////////////////////////////////////////////
voidConvertNode（BSTreeNode*pNode,BSTreeNode*&pLastNodeInList）
{
if（pNode==NULL）
return;
BSTreeNode*pCurrent=pNode;
//Converttheleftsub-tree
if（pCurrent->m_pLeft!
=NULL）
ConvertNode（pCurrent->m_pLeft,pLastNodeInList）;
//Putthecurrentnodeintothedouble-linkedlist
pCurrent->m_pLeft=pLastNodeInList;
if（pLastNodeInList!
=NULL）
pLastNodeInList->m_pRight=pCurrent;
pLastNodeInList=pCurrent;
//Converttherightsub-tree
if（pCurrent->m_pRight!
=NULL）
ConvertNode（pCurrent->m_pRight,pLastNodeInList）;
}
///////////////////////////////////////////////////////////////////////
//Covertabinarysearchtreeintoasorteddouble-linkedlist
//Input:
pHeadOfTree-theheadoftree
//Output:
theheadofsorteddouble-linkedlist
///////////////////////////////////////////////////////////////////////
BSTreeNode*Convert_Solution1（BSTreeNode*pHeadOfTree）
{
BSTreeNode*pLastNodeInList=NULL;
ConvertNode（pHeadOfTree,pLastNodeInList）;
//Gettheheadofthedouble-linkedlist
BSTreeNode*pHeadOfList=pLastNodeInList;
while（pHeadOfList&&pHeadOfList->m_pLeft）
pHeadOfList=pHeadOfList->m_pLeft;
returnpHeadOfList;
}
程序员面试题精选（02）－设计包含min函数的栈
题目：
定义栈的数据结构，要求添加一个min函数，能够得到栈的最小元素。
要求函数min、push以及pop的时间复杂度都是O
（1）。
分析：
这是去年google的一道面试题。
我看到这道题目时，第一反应就是每次push一个新元素时，将栈里所有逆序元素排序。
这样栈顶元素将是最小元素。
但由于不能保证最后push进栈的元素最先出栈，这种思路设计的数据结构已经不是一个栈了。
在栈里添加一个成员变量存放最小元素（或最小元素的位置）。
每次push一个新元素进栈的时候，如果该元素比当前的最小元素还要小，则更新最小元素。
乍一看这样思路挺好的。
但仔细一想，该思路存在一个重要的问题：
如果当前最小元素被pop出去，如何才能得到下一个最小元素？
因此仅仅只添加一个成员变量存放最小元素（或最小元素的位置）是不够的。
我们需要一个辅助栈。
每次push一个新元素的时候，同时将最小元素（或最小元素的位置。
考虑到栈元素的类型可能是复杂的数据结构，用最小元素的位置将能减少空间消耗）push到辅助栈中；每次pop一个元素出栈的时候，同时pop辅助栈。
参考代码：
#include
#include
templateclassCStackWithMin
{
public:
CStackWithMin（void）{}
virtual~CStackWithMin（void）{}
T&top（void）;
constT&top（void）const;
voidpush（constT&value）;
voidpop（void）;
constT&min（void）const;
private:
T>m_data; //theelementsofstack
size_t>m_minIndex; //theindicesofminimumelements
};
//getthelastelementofmutablestack
templateT&CStackWithMin:
:
top（）
{
returnm_data.back（）;
}
//getthelastelementofnon-mutablestack
templateconstT&CStackWithMin:
:
top（）const
{
returnm_data.back（）;
}
//insertanelmentattheendofstack
templatevoidCStackWithMin:
:
push（constT&value）
{
//appendthedataintotheendofm_data
m_data.push_back（value）;
//settheindexofminimumelmentinm_dataattheendofm_minIndex
if（m_minIndex.size（）==0）
m_minIndex.push_back（0）;
else
{
if（value m_minIndex.push_back（m_data.size（）-1）;
else
m_minIndex.push_back（m_minIndex.back（））;
}
}
//ereasetheelementattheendofstack
templatevoidCStackWithMin:
:
pop（）
{
//popm_data
m_data.pop_back（）;
//popm_minIndex
m_minIndex.pop_back（）;
}
//gettheminimumelementofstack
templateconstT&CStackWithMin:
:
min（）const
{
assert（m_data.size（）>0）;
assert（m_minIndex.size（）>0）;
returnm_data[m_minIndex.back（）];
}
举个例子演示上述代码的运行过程：
步骤 数据栈 辅助栈 最小值
1.push3 3 0 3
2.push4 3,4 0,0 3
3.push2 3,4,2 0,0,2 2
4.push1 3,4,2,1 0,0,2,3 1
5.pop 3,4,2 0,0,2 2
6.pop 3,4 0,0 3
7.push0 3,4,0 0,0,2 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 {
nCurSum+=pData;
//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 {
if（pData>nGreatestSum）
nGreatestSum=pData;
}
}
returntrue;
}
讨论：
上述代码中有两点值得和大家讨论一下：
函数的返回值不是子数组和的最大值，而是一个判断输入是否有效的标志。
如果函数返回值的是子数组和的最大值，那么当输入一个空指针是应该返回什么呢？
返回0？
那这个函数的用户怎么区分输入无效和子数组和的最大值刚好是0这两中情况呢？
基于这个考虑，本人认为把子数组和的最大值以引用的方式放到参
升级会员 