精选微软等数据结构+算法面试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</
分享到:
相关推荐
[答案V0.2版]精选微软数据结构+算法面试100题[前20题]--修正 http://download.csdn.net/source/2813890 //第61-100题答案、思路,正在整理中。 更多资源,下载地址: http://v_july_v.download.csdn.net/谢谢。 ...
[最新答案V0.3版]微软等数据结构+算法面试100题[第21-40题答案.rar[最新答案V0.3版]微软等数据结构+算法面试100题[第21-40题答案.rar[最新答案V0.3版]微软等数据结构+算法面试100题[第21-40题答案.rar
### 数据结构与算法面试题目解析——二叉查找树转排序双向链表 #### 题目背景 在IT行业,特别是软件开发领域,数据结构与算法是衡量一个程序员技术水平的重要标准之一。很多知名科技公司在招聘过程中会设置专门的...
火爆出炉:微软等数据结构+算法面试100题首次完整亮相[100题V0.1最终完美珍藏版.rar火爆出炉:微软等数据结构+算法面试100题首次完整亮相[100题V0.1最终完美珍藏版.rar火爆出炉:微软等数据结构+算法面试100题首次...
根据给定的信息,本文将详细解析“[珍藏版]微软等数据结构+算法面试100题全部出炉[100题V0.1最终完美版]”中提到的几个核心知识点,包括数据结构与算法的基础概念及其应用场景。 ### 1. 数据结构基础 #### 1.1 ...
2.[答案V0.2版]精选微软数据结构+算法面试100题[前20题]--修正 http://download.csdn.net/source/2813890 //此份答案是针对最初的V0.1版本,进行的校正与修正。 3.[答案V0.1版]精选微软数据结构+算法面试100题[前25...
微软等公司数据结构与算法面试题的背景 - **作者**: July,一位热衷于分享数据结构和算法知识的博主。 - **发布时间**: 2010年12月5日。 - **目的**: 分享微软及其他知名IT公司面试中常见的数据结构与算法题目,...
这份“微软等数据结构+算法面试100题全部答案集锦”文档显然是一个宝贵的资源,它提供了深入理解这些关键概念的机会。 首先,我们要明确数据结构是什么。数据结构是指在计算机中组织和存储数据的方式,包括数组、...
### 数据结构与算法面试知识点详解 ...以上知识点涵盖了常见的数据结构与算法面试题目,包括二叉树、栈、数组和链表等相关问题。这些问题旨在测试求职者对于这些基础知识的掌握程度以及解决问题的能力。
标题与描述指出了一份珍贵的学习资源——“微软等数据结构+算法面试100题”。这份资源由作者July于2010年12月6日完成并发布,共收录了100道与数据结构和算法相关的面试题。这些题目不仅覆盖了微软公司的面试内容,还...