[答案V0.1版]精选微软等数据结构+算法面试100题 [前20题]

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

--答案公布

-------

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

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

现在，我要，好好整理下，这篇帖子我已做出来的题目答案 了。

展示自己的思考结果，我觉得很骄傲。:)。

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

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();
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);
}
}

// 二叉树转换成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
//

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 1 //push 5,min=p->[3]=1 ^
3: 1 1 //push 1,min=p->[3]=1 | //此刻push进A的元素1小于B中栈顶元素2
2: 4 2 //push 4,min=p->[0]=2 |
1: 6 2 //push 6,min=p->[0]=2 |
0: 2 2 //push 2,min=p->[0]=2 |

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

然后，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.求子数组的最大和
题目：
输入一个整形数组，数组里有正数也有负数。
数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。
求所有子数组的和的最大值。要求时间复杂度为O(n)。

例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2，
因此输出为该子数组的和18。

//July 2010/10/18

#include <iostream.h>

int maxSum(int* a, int n)
{
int sum=0;
int b=0;

for(int i=0; i<n; i++)
{
if(b<0)
b=a[i];
else
b+=a[i];
if(sum<b)
sum=b;
}
return sum;
}

int main()
{
int a[10]={1,-8,6,3,-1,5,7,-2,0,1};
cout<<maxSum(a,10)<<endl;
return 0;
}

运行结果，如下：
20
Press any key to continue

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

int maxSum(int* a, int n)
{
int sum=0;
int b=0;

for(int i=0; i<n; i++)
{
if(b<=0) //此处修正下，把b<0改为 b<=0
b=a[i];
else
b+=a[i];
if(sum<b)
sum=b;
}
return sum;
}

//
解释下：
例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，
那么最大的子数组为3, 10, -4, 7, 2，
因此输出为该子数组的和18

所有的东西都在以下俩行，
即：
b：0 1 -1 3 13 9 16 18 7
sum：0 1 1 3 13 13 16 18 18

其实算法很简单，当前面的几个数，加起来后，b<0后，
把b重新赋值，置为下一个元素，b=a[i]。
当b>sum，则更新sum=b;
若b<sum，则sum保持原值，不更新。:)。July、10/31。
///

//关于第4题，
当访问到某一结点时，把该结点添加到路径上，并累加当前结点的值。
如果当前结点为叶结点并且当前路径的和刚好等于输入的整数，则当前的路径符合要求，我们把它打印出来。

如果当前结点不是叶结点，则继续访问它的子结点。当前结点访问结束后，递归函数将自动回到父结点。
因此我们在函数退出之前要在路径上删除当前结点并减去当前结点的值，
以确保返回父结点时路径刚好是根结点到父结点的路径。

我们不难看出保存路径的数据结构实际上是一个栈结构，因为路径要与递归调用状态一致，
而递归调用本质就是一个压栈和出栈的过程。

其中，部分题目源码及思路，参考自：

http://zhedahht.blog.163.com/blog/#m=0

void FindPath
(
BinaryTreeNode * pTreeNode, // a node of binary tree
int expectedSum, // the expected sum
std::vector < int >& path, // a path from root to current node
int & currentSum // the sum of path
)
{
if ( ! pTreeNode)
return ;

currentSum += pTreeNode -> m_nValue;
path.push_back(pTreeNode -> m_nValue);

// if the node is a leaf, and the sum is same as pre-defined,
// the path is what we want. print the path
bool isLeaf = ( ! pTreeNode -> m_pLeft && ! pTreeNode -> m_pRight);
if (currentSum == expectedSum && isLeaf)
{
std::vector < int > ::iterator iter = path.begin();
for (; iter != path.end(); ++ iter)
std::cout << * iter << ' \t ' ;
std::cout << std::endl;
}

// if the node is not a leaf, goto its children
if (pTreeNode -> m_pLeft)
FindPath(pTreeNode -> m_pLeft, expectedSum, path, currentSum);
if (pTreeNode -> m_pRight)
FindPath(pTreeNode -> m_pRight, expectedSum, path, currentSum);

// when we finish visiting a node and return to its parent node,
// we should delete this node from the path and
// minus the node's value from the current sum
currentSum -= pTreeNode -> m_nValue;
path.pop_back();
}

5.查找最小的k个元素
题目：输入n个整数，输出其中最小的k个。
例如输入1，2，3，4，5，6，7和8这8个数字，
则最小的4个数字为1，2，3和4。
//July 2010/10/18
//引用自116 楼 wocaoqwer 的回复。

#include<iostream>
using namespace std;

class MinK{
public:
MinK(int *arr,int si):array(arr),size(si){}

bool kmin(int k,int*& ret){
if(k>size)
{
ret=NULL;
return false;
}
else
{
ret=new int[k--];
int i;
for(i=0;i<=k;++i)
ret[i]=array[i];
for(int j=(k-1)/2;j>=0;--j)
shiftDown(ret,j,k);
for(;i<size;++i)
if(array[i]<ret[0])
{
ret[0]=array[i];
shiftDown(ret,0,k);
}
return true;
}
}

void remove(int*& ret){
delete[] ret;
ret=NULL;
}


private:
void shiftDown(int *ret,int pos,int length){
int t=ret[pos];
for(int s=2*pos+1;s<=length;s=2*s+1){
if(s<length&&ret[s]<ret[s+1])
++s;
if(t<ret[s])
{
ret[pos]=ret[s];
pos=s;
}
else break;
}
ret[pos]=t;
}

int *array;
int size;
};


int main()
{
int array[]={1,2,3,4,5,6,7,8};
MinK mink(array,sizeof(array)/sizeof(array[0]));
int *ret;
int k=4;
if(mink.kmin(k,ret))
{
for(int i=0;i<k;++i)
cout<<ret[i]<<endl;
mink.remove(ret);
}
return 0;
}


/////
运行结果：
4
2
3
1
Press any key to continue
/////

第6题
------------------------------------
腾讯面试题：
给你10分钟时间，根据上排给出十个数，在其下排填出对应的十个数
要求下排每个数都是先前上排那十个数在下排出现的次数。
上排的十个数如下：
【0，1，2，3，4，5，6，7，8，9】

初看此题，貌似很难，10分钟过去了，可能有的人，题目都还没看懂。

举一个例子，
数值: 0,1,2,3,4,5,6,7,8,9
分配: 6,2,1,0,0,0,1,0,0,0
0在下排出现了6次，1在下排出现了2次，
2在下排出现了1次，3在下排出现了0次....
以此类推..
// 引用自July 2010年10月18日。

//数值: 0,1,2,3,4,5,6,7,8,9
//分配: 6,2,1,0,0,0,1,0,0,0

#include <iostream.h>
#define len 10


class NumberTB
{
private:
int top[len];
int bottom[len];
bool success;
public:
NumberTB();
int* getBottom();
void setNextBottom();
int getFrequecy(int num);
};

NumberTB::NumberTB()
{
success = false;
//format top
for(int i=0;i<len;i++)
{
top[i] = i;
}
}

int* NumberTB::getBottom()
{
int i = 0;
while(!success)
{
i++;
setNextBottom();
}
return bottom;
}

//set next bottom
void NumberTB::setNextBottom()
{
bool reB = true;

for(int i=0;i<len;i++)
{
int frequecy = getFrequecy(i);

if(bottom[i] != frequecy)
{
bottom[i] = frequecy;
reB = false;
}
}
success = reB;
}

//get frequency in bottom
int NumberTB::getFrequecy(int num) //此处的num即指上排的数 i
{
int count = 0;

for(int i=0;i<len;i++)
{
if(bottom[i] == num)
count++;
}
return count; //cout即对应 frequecy
}

int main()
{
NumberTB nTB;
int* result= nTB.getBottom();

for(int i=0;i<len;i++)
{
cout<<*result++<<endl;
}
return 0;
}
///
运行结果：
6
2
1
0
0
0
1
0
0
0
Press any key to continue
/////

第7题
------------------------------------
微软亚院之编程判断俩个链表是否相交
给出俩个单向链表的头指针，比如h1，h2，判断这俩个链表是否相交。
为了简化问题，我们假设俩个链表均不带环。

问题扩展：
1.如果链表可能有环列?
2.如果需要求出俩个链表相交的第一个节点列?

//这一题，自己也和不少人讨论过了，
//更详细的，请看这里：
//My sina Blog：
//http://blog.sina.com.cn/s/blog_5e3ab00c0100le4s.html

1.首先假定链表不带环
那么，我们只要判断俩个链表的尾指针是否相等。
相等，则链表相交；否则，链表不相交。
2.如果链表带环，
那判断一链表上俩指针相遇的那个节点，在不在另一条链表上。
如果在，则相交，如果不在，则不相交。

所以，事实上，这个问题就转化成了：
1.先判断带不带环
2.如果都不带环，就判断尾节点是否相等
3.如果都带环，判断一链表上俩指针相遇的那个节点，在不在另一条链表上。
如果在，则相交，如果不在，则不相交。

//用两个指针，一个指针步长为1，一个指针步长为2，判断链表是否有环
bool check(const node* head)
{
if(head==NULL)
return false;
node *low=head, *fast=head->next;
while(fast!=NULL && fast->next