精选微软数据结构+算法面试100题前20题

精选微软等数据结构+算法面试100题

--答案修正 V0.2版本

此份答案是针对，前期已公布的最初的那份答案的，初步校正与修正。

http://www.77cn.com.cn/source/2796735 （V 0.1版）

相比第一份 V0.1版答案，此份答案 V0.2版更加准确，亦修正了不少题目的答案。此份20题的答案，思路更加清晰易懂，简介明了。

帖子更新地址：

http://www.77cn.com.cn/u/20101023/20/5652ccd7-d510-4c10-9671-307a56006e6d.html 若对已公布的面试题有任何问题，请把意见发表在上述帖子上，探讨交流。 所有源码及答案，只做了初步校正，欢迎批评指正。

My Blog：

http://www.77cn.com.cn/v_JULY_v

My Sina Blog：

http://www.77cn.com.cn/shitou009

My E-mail：

z houlei0907@http://www.77cn.com.cn

//东华理工、July 整理编辑。2010/11/06。 谢谢。

------- 我很享受思考的过程，个人思考的全部结果，都放在了这篇帖子上，

http://www.77cn.com.cn/u/20101023/20/5652ccd7-d510-4c10-9671-307a56006e6d.html

现在，我要，好好整理下，上篇帖子上，已公布出来的题目答案 了。 展示自己的思考结果，我觉得很骄傲。:)。

----------------------------------------------------------

1

2010年 10月18日下午 July -------------------------------- 1.把二元查找树转变成排序的双向链表 题目：

输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。 要求不能创建任何新的结点，只调整指针的指向。

10 / \ 6 14 / \ / \ 4 8 12 16 转换成双向链表 4=6=8=10=12=14=16。

首先我们定义的二元查找树 节点的数据结构如下： struct BSTreeNode {

int m_nValue; // value of node

BSTreeNode *m_pLeft; // left child of node BSTreeNode *m_pRight; // right child of node };

//引用 245 楼 tree_star 的回复 #include <stdio.h> #include <iostream.h>

struct BSTreeNode {

int m_nValue; // value of node

BSTreeNode *m_pLeft; // left child of node BSTreeNode *m_pRight; // right child of node };

typedef BSTreeNode DoubleList; DoubleList * pHead; DoubleList * pListIndex;

void convertToDoubleList(BSTreeNode * pCurrent);

// 创建二元查找树

void addBSTreeNode(BSTreeNode * & pCurrent, int value) {

if (NULL == pCurrent) {

BSTreeNode * pBSTree = new BSTreeNode();

2

pBSTree->m_pLeft = NULL; pBSTree->m_pRight = NULL; pBSTree->m_nValue

=

value; pCurrent = pBSTree;

}

else

{

if ((pCurrent->m_nValue) > value)

{

addBSTreeNode(pCurrent->m_pLeft, value); }

else if ((pCurrent->m_nValue) < value) {

addBSTreeNode(pCurrent->m_pRight, value);}

else

{

//cout<<"重复加入节点"<<endl; }

} }

// 遍历二元查找树 中序

void ergodicBSTree(BSTreeNode * pCurrent) {

if (NULL == pCurrent) {

return;

}

if (NULL != pCurrent->m_pLeft) {

ergodicBSTree(pCurrent->m_pLeft); }

// 节点接到链表尾部

convertToDoubleList(pCurrent); // 右子树为空

if (NULL != pCurrent->m_pRight) {

ergodicBSTree(pCurrent->m_pRight); } }

3

// 二叉树转换成 list

void convertToDoubleList(BSTreeNode * pCurrent) {

pCurrent->m_pLeft = pListIndex; if (NULL != pListIndex) {

pListIndex->m_pRight = pCurrent; }

else

{

pHead = pCurrent; }

pListIndex = pCurrent;

cout<<pCurrent->m_nValue<<endl; }

int main() {

BSTreeNode * pRoot = NULL; pListIndex = NULL; pHead = NULL;

addBSTreeNode(pRoot, 10); addBSTreeNode(pRoot, 4); addBSTreeNode(pRoot, 6); addBSTreeNode(pRoot, 8); addBSTreeNode(pRoot, 12); addBSTreeNode(pRoot, 14); addBSTreeNode(pRoot, 15); addBSTreeNode(pRoot, 16); ergodicBSTree(pRoot); return 0; }

/////////////////////////////////////////////// 4 6 8 10 12 14 15 16

Press any key to continue

//////////////////////////////////////////////

4

2.设计包含 min 函数的栈。

定义栈的数据结构，要求添加一个 min 函数，能够得到栈的最小元素。 要求函数 min、push 以及 pop 的时间复杂度都是 O(1)。

结合链表一起做。 首先我做插入以下数字：10，7，3，3，8，5，2， 6

0: 10 -> NULL (MIN=10, POS=0)

1: 7 -> [0] (MIN=7, POS=1) 用数组表示堆栈，第0个元素表示栈底 2: 3 -> [1] (MIN=3, POS=2) 3: 3 -> [2] (MIN=3, POS=3)

4: 8 -> NULL (MIN=3, POS=3) 技巧在这里，因为8比当前的 MIN 大，所以弹出8不会对当前 的 MIN 产生影响

5：5 -> NULL (MIN=3, POS=3)

6: 2 -> [2] (MIN=2, POS=6) 如果2出栈了，那么3就是 MIN 7: 6 -> [6]

出栈的话采用类似方法修正。 所以，此题的第1小题，即是借助辅助栈，保存最小值， 且随时更新辅助栈中的元素。 如先后，push 2 6 4 1 5 stack A stack B（辅助栈）

4: 5

3: 1 栈顶元素2 2: 4 1: 6 0: 2

1 1

//push 5,min=p->[3]=1 //push 1,min=p->[3]=1

^ |

//此刻 push 进 A 的元素1小于 B

2 2 2

//push 4,min=p->[0]=2 //push 6,min=p->[0]=2 //push 2,min=p->[0]=2

| | |

push 第一个元素进 A，也把它 push 进 B，

当向 Apush 的元素比 B 中的元素小， 则也 push 进 B，即更新 B。否则，不动 B，保存原值。 向栈 A push 元素时，顺序由下至上。 辅助栈 B 中，始终保存着最小的元素。

5

然后，pop 栈 A 中元素，5 1 4 6 2 A B ->更新 4: 5 1 1 //pop 5,min=p->[3]=1 | 3: 1 1 2 //pop 1,min=p->[0]=2 | 2: 4 2 2 //pop 4,min=p->[0]=2 | 1: 6 2 2

//pop 6,min=p->[0]=2

|

0:

2

2

NULL //pop 2,min=NULL

v

当 pop A 中的元素小于 B 中栈顶元素时，则也要 pop B 中栈顶元素。

3.求子数组的最大和 题目：

输入一个整形数组，数组里有正数也有负数。 数组中连续的一个或多个整数组 …… 此处隐藏：8691字，全部文档内容请下载后查看。喜欢就下载吧 ……