微软十五道面试题 答案

long strToInt(char *str,int length)//从最左边开始 
{
	if(length>1) 
		return str[0]=='-'? strToInt(str,length-1)*10-(str[length-1]-'0') : strToInt(str,length-1)*10+str[length-1]-'0';
	else 
		return str[0]=='-'? 0:str[0]-'0';
}

#include
#include
using namespace std;


void swap(char *a,char *b)
{
	char t;  
    t=*a;  
    *a=*b;  
    *b=t; 
}


void printAllArray(char a[],int n,int index)
{
	int i,j;
	if(index==n)
	{
		for(i=0;i

#include
#include
#include
using namespace std;
#define N 101


void myStrcpy(char a[],char b[])
{
	char c[N];
	int len,len2,i,j,k,f;
	len=strlen(a);
	
	f=0;
	for(i=0;i

#include
#include
#include
#include
using namespace std;
#define N 101
struct  Node{
	int data;
	struct Node *left,*right;
}; 




Node* bulidTree(int array[], int start, int end) 
{
	if (start>end) 
		return NULL;
	int m=(start+end)/2;
	Node *root=(Node*)malloc(sizeof(Node));
	root->data=array[m];
	root->left=bulidTree(array,start,m-1);
	root->right=bulidTree(array,m+1,end);
	return root;
} 


// 中序遍历 左根右 
void displayTreeMid(Node *head) 
{
	if(head->left)
		displayTreeMid(head->left);
	printf("%d ",head->data);
	if(head->right)
		displayTreeMid(head->right);
}
// 前序遍历 根左右 
void displayTreeFore(Node *head) 
{
	printf("%d ",head->data);
	if(head->left)
		displayTreeFore(head->left);
	if(head->right)
		displayTreeFore(head->right);
}


// 后序遍历 左右根 
void displayTreeBack(Node *head) 
{
	if(head->left)
		displayTreeBack(head->left);
	if(head->right)
		displayTreeBack(head->right);
	printf("%d ",head->data);
}


int main()
{
	/*
			  5
		  2	     7
		1  3   6  8
		    4      9
	中序遍历：1 2 3 4 5 6 7 8 9
	前序遍历：5 2 1 3 4 7 6 8 9
	后序遍历：1 4 3 2 6 9 8 7 5
	*//* 
	int array[]={1,2,3,4,5,6,7,8,9};
	Node *root;
	root=bulidTree(array,0,sizeof(array)/sizeof(int)-1);
	printf("中序遍历：");
	displayTreeMid(root);
	printf("n");
	 
	printf("前序遍历：");
	displayTreeFore(root);
	printf("n");
	
	printf("后序遍历：");
	displayTreeBack(root);
	printf("n");
	return 0;
}

/*
第 16  题：
题目（微软）： 
输入一颗二元树，从上往下按层打印树的每个结点，同一层中按照从左往右的顺序打印。
		8
      /  
	 6   10
	/   / 
   5  7 9  11
打印出来：8 6 10 5 7 9 11


BFS广度优先搜索 




#include
#include
#include
#include 
using namespace std;
#define MAX 20


struct BTreeNode{
	int data;
	BTreeNode *left,*right;
}; 


//建立二叉树 
BTreeNode * CreateTree(int data[],int pos,int len)
{
	BTreeNode *tree;
	if(pos>=len) 
	{
		return NULL;
	}
	else
	{
		tree=(BTreeNode *)malloc(sizeof(BTreeNode));
		tree->data=data[pos];
		tree->left=CreateTree(data,2*pos+1,len);//数组坐标 
		tree->right=CreateTree(data,2*pos+2,len);
		return tree;
	}
	
}


void InOrder(BTreeNode *tree)
{
	if(tree!=NULL)
	{
		InOrder(tree->left);
		printf("%d ",tree->data);
		InOrder(tree->right);
	}
}


void BFS(BTreeNode *root)
{
	BTreeNode *temp,*start;
	queue q;
	
	q.push(root);
	while(!q.empty())
	{
		start=q.front();
		q.pop();
		
		if(start->left!=NULL)
			q.push(start->left);
		
		if(start->right!=NULL)
			q.push(start->right);
		printf("%d ",start->data);	
	}
}


int main(){
	
	int data[]={8,6,10,5,7,9,11};
	int len=sizeof(data)/sizeof(int);
	
	BTreeNode *tree=CreateTree(data,0,len);


	printf("中序遍历：n");//左根右 
	InOrder(tree);printf("n");
	printf("打印结果：n");
	BFS(tree);printf("n");
	
	return 0;
}

node * reverseNonrecurse(node *head)
{
	if(head==NULL) return head;
	
	node *p=head,*previous=NULL,*next=NULL;
	
	while(p->next!=NULL)
	{
		next=p->next;//保存下一个 
		p->next=previous;//p下一个为他前面的
		previous=p;
		p=next; 
	}
	p->next=previous;
	return p;
}

#include
#include
#include
using namespace std;


int atoi(char* a) 
{
	if (*a=='+')
		return atoi(a+1);
	else if(*a=='-') 
		return -atoi(a+1);
		
	char *p=a;
	int ans=0;
	while(*p>='0'&&*p

void devide(int val1, int val2, int& res, int &rev) //两个值val1 val2 商res 余数rev 
{  
    int maxv = max(val1, val2);  
    int minv = min(val1, val2);  
    res=0;  rev = 0;  
    if(maxv == minv){  
        res = 1;  
        rev = 0;  
        return;  
    }
	else
	{  
        while(maxv>minv)
		{  
            maxv=maxv-minv;  
            res+=1;  
        }  
        rev=maxv;  
        return;  
    }  
}

void countNum(int a[],int start,int finish，int num)
{
 
    int middle=(start+finish)/2;
    if(start>finish)
      return ;


    if(a[middle]==num)
    {
        count++;
        countNum(a,start,middle-1,num);
        countNum(a,middle+1,finish,num);
    }
	else if(a[middle]>num)
        countNum(a,start,middle-1);
	else
       countNum(a,middle+1,finish);
}

/*
67.俩个闲玩娱乐。
1.扑克牌的顺子
从扑克牌中随机抽 5  张牌，判断是不是一个顺子，即这 5  张牌是不是连续的。2-10  为数
字本身，A为1，J 11，Q为12，K为13，而大小王可以看成任意数字。


5张牌看成由5个数字组成的数组。大小王当成0.我们把数组排序。由于0可以当成任意数字，
我们可以用0去补满数组中的空缺。也就是排序之后的数组不是连续的，
即相邻的两个数字相隔若干个数字，但如果我们有足够的0可以补满这两个数字的空缺，
这个数组实际上还是连续的。
{0，1，3，4，5}。0可以当成2去填补这个空缺,所以是顺子 
*/
#include
#include
#include
using namespace std;


bool checkGaps(int a[],int s,int e,int allowGaps)
{
	int i=s;
	while(i0)
		return checkGaps(a,0,4,0);
	else if(a[0]==0&&a[1]!=0)
		return checkGaps(a,1,4,1);
	return checkGaps(a,2,4,2);
}


int main()
{
	int i;
	int a[]={1,0,3,4,5};
	int b[]={0,0,9,5,6};
	int c[]={1,0,2,3,6};
	
	for(i=0;i

/*
75.二叉树两个结点的最低共同父结点
题目：二叉树的结点定义如下：
struct TreeNode
{
int  m_nvalue;
TreeNode*  m_pLeft;
TreeNode*  m_pRight;
}; 
输入二叉树中的两个结点，输出这两个结点在数中最低的共同父结点。


对于一个子树的根结点来说，如果那两个结点分别位于该子树的左右子树，则最低共同父结点为该子树的根结点，
如果那两个结点都位于该子树的左子树，则最低共同父结点位于该子树根结点的左子树，
否则来自右子树。递归
*/


//寻找二叉树两个结点的最低共同父节点
TreeNode *FindFirstCommonParentNode(TreeNode *pRoot, TreeNode *pNodeOne, TreeNode *pNodeTwo)
{
    if (NULL==pRoot)
    {
        return NULL;
    }
    if (pRoot==pNodeOne || pRoot==pNodeTwo)
    {
        return pRoot;
    }
    TreeNode *pLeft = FindFirstCommonParentNode(pRoot->m_pLeft, pNodeOne, pNodeTwo);
    TreeNode *pRight = FindFirstCommonParentNode(pRoot->m_pRight, pNodeOne, pNodeTwo);


    if (NULL==pLeft) //1、左子树没有找到任何一个结点，则第一个公共父节点必定在右子树，而且找到第一个结点就是最低共同父节点
    {
        return pRight;
    }
    else if (NULL==pRight) //2、右子树没有找到任何一个结点，则第一个公共父节点必定在左子树，而且找到第一个结点就是最低共同父节点
    {
        return pLeft;
    }
    else          //3、分别在结点的左右子树找到，则此节点必为第一个公共父节点
    {
        return pRoot;
    }
}

static BinNode Find(BinNode root)
{
    BinNode min = FindMinNode(root);
    BinNode max = FindMaxNode(root);
    double find = (double)(min.Element+max.Element) / 2;
    return FindNode(root, find);
}
 
static BinNode FindMinNode(BinNode root)
{
    BinNode min = root;
    while (min.Left != null)
    {
        min = min.Left;
    }
    return min;
}


static BinNode FindMaxNode(BinNode root)
{
    BinNode max = root;
    while (max.Right != null)
    {
        max = max.Right;
    }
    return max;
}


递归寻找BST的节点，O(logN)。
static BinNode FindNode(BinNode root, double mid)
{           
    //如果小于相等，则从右边找一个最小值
    if (root.Element find
    {
        if (root.Left == null)
            return root;
        BinNode find = FindNode(root.Left, mid);
        //不一定找得到
        return find.Element 

void find2Number(int a[],int n,int dest)
{
	int *f=a,*e=a+n-1;
	int sum=*f+*e;
	while(sum!=dest&&f

int main()  
{  
    int a[] = {1,3,4,7,8,9,10};  
    int sum = 11;  
    int len = sizeof(a)/sizeof(int);  
    int *b = (int *)malloc(sizeof(len));  
    
    for(int i=0;i b[high])  
        {  
            high--;  
        }else{  
            low++;  
        }  
    }  
    getchar();  
    return 0;  
}