微软面试100 题题解

/*
    Name: 在二元树中找出和为某一值的所有路径（树）
    Copyright: 
    Author: yifi
    Date: 27/11/16 17:10
    Description: 
*/

#include <bits/stdc++.h>

using namespace std;


struct BinaryTreeNode
{
    int m_nValue;
    BinaryTreeNode * m_pLeft;
    BinaryTreeNode * m_pRight;
};

int count = 0;


void FindPath(BinaryTreeNode* pTreeNode,
int expectedSum,vector<int>& path,int& currentSum)
{
    if (!pTreeNode)
    {
        return ;
    }
    currentSum += pTreeNode->m_nValue;
    path.push_back(pTreeNode->m_nValue);
    bool isLeaf = !(pTreeNode->m_pLeft) && !(pTreeNode->m_pRight);
    
    
    if (currentSum == expectedSum && isLeaf)
    {
        vector<int>::iterator iter;
        for (iter = path.begin();iter != path.end(); iter++)
        {
            cout << *iter << "	"; 
        }
        cout << endl;
    }
    
    if (pTreeNode->m_pLeft)
    {
        FindPath(pTreeNode->m_pLeft,expectedSum,path,currentSum);
    }
    if (pTreeNode->m_pRight)
    {
        FindPath(pTreeNode->m_pRight,expectedSum,path,currentSum);
    }
    currentSum -= pTreeNode->m_nValue;
    path.pop_back();
}

void addTree(BinaryTreeNode **T, int num)
{
    if(*T == NULL)
    {   
        *T = (BinaryTreeNode *)malloc(sizeof(BinaryTreeNode));
        (*T)->m_nValue = num;
        (*T)->m_pLeft = NULL;
        (*T)->m_pRight = NULL;
    }   
    else if((*T)->m_nValue > num)
         addTree(&((*T)->m_pLeft), num);
    else if((*T)->m_nValue < num)
        addTree(&((*T)->m_pRight), num);
    else
        cout << "重复加入同一结点" << endl;
}

 int main()
{
    BinaryTreeNode * T = NULL;
    addTree(&T, 10);
    addTree(&T, 12);
    addTree(&T, 5);
    addTree(&T, 7);
    addTree(&T, 4);

    vector<int> path;
    int sum = 0;
    FindPath(T, 22, path, sum);

    return 0;
}
             

/*
    Name: 子数组的最大和（数组）
    Copyright: 
    Author: yifi
    Date: 23/11/16 22:51
    Description: 
*/


#include <bits/stdc++.h>

using namespace std;

int main()
{
    int sum = 0;
    int MaxSum = -10000000;
    int a[] = {1,-2,3,10,-4,7,2,-5};
    int i = 0;
    for (i = 0;i<8;i++)
    {
        if (sum < 0)
        {
            sum = a[i];
        }
        else 
        {
            sum += a[i];
        }
        if (sum > MaxSum)
        {
            MaxSum = sum;
        }
    }
    cout << MaxSum << endl;
}

/*
    Name: 包含 min 函数的栈（栈）
    Copyright: 
    Author: yifi 
    Date: 23/11/16 22:16
    Description: 
*/

#include <stdio.h>

#include <iostream>
using namespace std;

#define STACK_SIZE 20

typedef struct _STACK{
    int data[STACK_SIZE];
    int top;
    int min;
}Stack;

void Init(Stack* s);
void Push(Stack* s,int val);
int Pop(Stack* s);
bool Full(Stack* s);
bool Empty(Stack* s);
int Min(Stack* s);


Stack haha;
int main()
{
    Stack s;
   Init( &s );
   Push( &s, 3);
   std::cout << Min( &s ) << std::endl;
   Push( &s, 4);
   std::cout << Min( &s ) << std::endl;
   Push( &s, 2);
   std::cout << Min( &s ) << std::endl;
   Push( &s, 1);
   std::cout << Min( &s ) << std::endl;
   Pop( &s );
   std::cout << Min( &s ) << std::endl;
   Pop( &s );
   std::cout << Min( &s ) << std::endl;
   Push( &s, 0);
   std::cout << Min( &s ) << std::endl;
   return 0;
}

void Init(Stack* s)
{
    s->top = -1;
    s->min = -1;
    haha.top = -1;
}


void Push(Stack* s,int val)
{
    if (Full(s))
    {
        printf("Satck is Full
");
        return ;
    }
    if (s->min == -1 || val < s->min)
    {
        s->min = val;
        haha.data[++haha.top] = val;
    }
    s->data[++s->top] = val;
}



int Pop( Stack *s )
{
   int data;
   if( Empty(s) )
   {
      printf( "stack is empty
" );
      return -1;
   }
   data = s->data[s->top--];
   if( data == haha.data[haha.top] )
   {
      s->min = haha.data[--haha.top];
   }
   return data;
}
int Min( Stack *s )
{
   return s->min;
}
bool Empty( Stack *s )
{
   if( s->top == -1 )
   {
      return true;
   }
   return false;
}

bool Full( Stack *s )
{
   if( s->top == STACK_SIZE-1 )
   {
      return true;
   }
   return false;
}

/*
    Name: 二元查找树转变成排序的双向链表（树）
    Copyright: 
    Author: yifi
    Date: 23/11/16 17:06
    Description: 
*/


#include <iostream>
using namespace std;

typedef struct _BSTreeNode{
    int m_Value;
    _BSTreeNode* pLeft;
    _BSTreeNode* pRight;
}BSTreeNode,*pBSTreeNode; 

void addBSTreeNode(BSTreeNode *&pCurrent,int value);
void inOrderBSTree(BSTreeNode* pBSTree);
void convertToDoubleList(BSTreeNode* pCurrent);

BSTreeNode *pHead=NULL;//指向循环队列头结点
BSTreeNode *pIndex=NULL;//指向前一个结点
int main()
{
    BSTreeNode *pRoot=NULL;
    addBSTreeNode(pRoot,10);
    addBSTreeNode(pRoot,6);
    addBSTreeNode(pRoot,14);
    addBSTreeNode(pRoot,4);
    addBSTreeNode(pRoot,8);
    addBSTreeNode(pRoot,12);
    addBSTreeNode(pRoot,16);
    inOrderBSTree(pRoot);
    return 0;
}


void addBSTreeNode(BSTreeNode *&pCurrent,int value)
{
    if (pCurrent == NULL)     
    {
        BSTreeNode* pTemp = new BSTreeNode();
        pTemp->m_Value = value;
        pTemp->pLeft = NULL;
        pTemp->pRight = NULL;
        pCurrent = pTemp;
    }
    else if (pCurrent->m_Value < value)
    {
        addBSTreeNode(pCurrent->pRight,value);
    }
    else if (pCurrent->m_Value > value)
    {
        addBSTreeNode(pCurrent->pLeft,value);
    }
    else 
    {
        cout << "Node Repeated" << endl;
    }
}

void inOrderBSTree(BSTreeNode* pBSTree)
{
    if (pBSTree == NULL)
    {
        return ;
    }
    if (pBSTree->pLeft != NULL)
    {
        inOrderBSTree(pBSTree->pLeft);
    }
     convertToDoubleList(pBSTree);
    if (pBSTree->pRight != NULL)
    {
        inOrderBSTree(pBSTree->pRight);
    }
     
}
void convertToDoubleList(BSTreeNode* pCurrent)
{
    pCurrent->pLeft = pIndex;
    if (pIndex == NULL)
    {
        pHead = pCurrent;
    }
    else 
    {
        pIndex->pRight = pCurrent;
    }
    pIndex = pCurrent;
    
    cout << pCurrent->m_Value << " "; 
}