永久优化：微软技术面试100题第11-20题答案修正与优化

                永久优化：微软技术面试100题第11-20题答案修正与优化

作者：July、Sorehead、leeyunce、zhedahht等。
时间：二零一一年四月四日。
微博：http://weibo.com/julyweibo。
出处：http://blog.csdn.net/v_JULY_v。
--------------------------------------------

 

引言   
    可能最近才看到本人博客的朋友，不了解此微软100题的具体情况。一切的详情，请参见此文：横空出世，席卷CSDN [评微软等数据结构+算法面试100题]。在此，不再赘述。不过，正因为此文，曾在CSDN上刮起了一股长达4个月的微软面试题的风暴。

前言
    最初的第一版答案，请参考这：答案第一版[第1-20题答案]。而后对前10题第1-10题所做的勘误，见这：答案优化[第1-10题勘误]。本文则是针对之前上传资源的第一版答案第11-20题的答案，所做的勘误，点评，修正与优化。同样，还是非常感谢网友Sorehead所辅助校正的答案。非常感谢。

    当然，Sorehead所做的点评，或者他的答案肯定不是最好的，可能也有不少错误。之所以把其贴出来，是因为他发现了我之前上传答案中的很多问题与错误。相信，很多网友也发现了不少或同样的错误。为了给各位一个参考，同时也是为了相互交流，因此，成了本文。

    同时，由于本人之前最初整理此100题的答案十分仓促，加之水平有限，所以肯定还存在不少问题，任何人对我之前上传的答案，如：第1-20题答案，或者对前10题的勘误：第1-10题勘误，或者对以下任何一题的答案有任何问题，都欢迎批评指正。

    顺便透露下：经过一个多月的思量，本人已经决定：三年之内或之后，将出一本书。书名：不确定，内容：有关面试题还是有关算法，亦不确定。不过，本人奢望，拯救国内图书市场。

    ok，扯的太多了。回到咱们眼前的旅程，yeah，现在开始。

微软技术面试100题第11-20题答案修正与优化

    注意：以下内容有一部分是Sorehead在我帖子上微软100题，维护地址的回复内容（自行辨别），文中所说的楼主即指本人。且下文中所说的“楼主代码”，都是特指之前本人上传的答案第一版[第1-20题答案]，读者可相互对照着阅读。
第11题（树）
求二叉树中节点的最大距离...

如果我们把二叉树看成一个图，父子节点之间的连线看成是双向的，
我们姑且定义"距离"为两节点之间边的个数。
写一个程序，
求一棵二叉树中相距最远的两个节点之间的距离。

原先我给的答案，如下（个人感觉，还是本人写的代码更清晰）：

//定义一个结构体
struct NODE
{
    NODE* pLeft;
    NODE* pRight;
    int MaxLen;
    int MaxRgt;
}; 
NODE* pRoot;  //根节点
int MaxLength;

void traversal_MaxLen(NODE* pRoot)
{
    if(pRoot == NULL)
    {
        return 0;
    };
  
    if(pRoot->pLeft == NULL)  
    {
        pRoot->MaxLeft = 0;
    }
    else                                 //若左子树不为空
    {
        int TempLen = 0;
        if(pRoot->pLeft->MaxLeft > pRoot->pLeft->MaxRight)
          //左子树上的，某一节点，往左边大，还是往右边大
        {
            TempLen+=pRoot->pLeft->MaxLeft;
        }
        else
        {
            TempLen+=pRoot->pLeft->MaxRight;
        }
        pRoot->nMaxLeft = TempLen + 1;
        traversal_MaxLen(NODE* pRoot->pLeft);
        //此处，加上递归
    }  
    if(pRoot->pRigth == NULL)
    {
        pRoot->MaxRight = 0;
    }
    else                                //若右子树不为空
    {
        int TempLen = 0;
        if(pRoot->pRight->MaxLeft > pRoot->pRight->MaxRight)
        //右子树上的，某一节点，往左边大，还是往右边大
        {
            TempLen+=pRoot->pRight->MaxLeft;
        }
        else
        {
            TempLen+=pRoot->pRight->MaxRight;
        }
        pRoot->MaxRight = TempLen + 1;
        traversal_MaxLen(NODE* pRoot->pRight);
        //此处，加上递归
    }
  
   if(pRoot->MaxLeft + pRoot->MaxRight > 0)
    {
        MaxLength=pRoot->nMaxLeft + pRoot->MaxRight;
    }
}

    Sorehead：
     十一题我写了一个非递规的方法，一方面是非递规并不复杂，另外一方面我不大喜欢楼主答案中采用全局变量的方式，我一直认为全局变量能少就少，最好不用。写的代码，如下：
typedef struct _tree
{
        int             key;
        struct _tree    *left;
        struct _tree    *right;
        int             height_left;
        int             height_right;
} tree;

#define TREE_HEIGHT 32

int get_tree_max_distance(tree *head)
{
        tree *stack_node[TREE_HEIGHT];
        int stack_flag[TREE_HEIGHT];
        int top;
        tree *node;
        int max_len;

        if (head == NULL)
                return 0;

        max_len = 0;
        top = 0;
        stack_node[top] = head;
        stack_flag[top] = 0;
        while (top != -1)
        {
                node = stack_node[top];
                if (node == NULL)
                {
                        top--;
                        continue;
                }

                if (stack_flag[top] == 0)
                {
                        stack_flag[top]++;
                        stack_node[++top] = node->left;
                        stack_flag[top] = 0;
                }
                else if (stack_flag[top] == 1)
                {
                        stack_flag[top]++;
                        stack_node[++top] = node->right;
                        stack_flag[top] = 0;
                }
                else
                {
                        if (node->left != NULL)
                                node->height_left = node->left->height_left > node->left->height_right ? node->left->height_left + 1 : node->left->height_right + 1;
                        else
                                node->height_left = 0;
                        if (node->right != NULL)
                                node->height_right = node->right->height_left > node->right->height_right ? node->right->height_left + 1 : node->right->height_right + 1;
                        else
                                node->height_right = 0;

                        if (max_len height_left + node->height_right)
                                max_len = node->height_left + node->height_right;

                        top--;
                }
        }
        return max_len;
}

    一次遍历，由于必须是后序遍历，因此加了一个flag数组用于保存栈中节点的状态：0表示该节点刚开始处理；1表示其左子树遍历完毕；2表示右子树遍历完毕。当然可以创建一个结构把节点地址和这个标志放在一起。
    树的前序遍历和中序遍历并不需要这个标志，所以只需要一个栈保存节点地址即可。

非递归的方法，也可以如azuryy所示，这么写：
struct Node
{
    bool _visited;

    Node* left;
    Node* right;
    int maxLeft;
    int maxRight;

    Node()
    {
        _visited = false;
        maxLeft = 0;
        maxRight = 0;
        left = NULL;
        right = NULL;
    }
};

int maxLen   = 0;

stack nodeStack;

void findMaxLen( Node* root )
{
    Node* node;

    if ( root == NULL )
    {
        return ;
    }

    nodeStack.push( root );
    while( !nodeStack.empty())
    {
        node = nodeStack.top();

        if ( node->left == NULL && node->right == NULL )
        {
            nodeStack.pop();
            node->_visited = true;
            continue;
        }
        if ( node->left )
        {
            if ( !node->left->_visited )
            {
                nodeStack.push( node->left ) ;
            }           
            else
            {
                node->maxLeft = max( node->left->maxLeft,node->left->maxRight ) + 1;
            }
        }
        if ( ( !node->left || node->left->_visited ) && node->right )
        {
            if ( !node->right->_visited )
            {
                nodeStack.push( node->right ) ;
            }           
            else
            {
                node->maxRight = max( node->right->maxLeft,node->right->maxRight ) + 1;
            }
        }

        if (( !node->left || node->left->_visited ) && ( !node->right || node->right->_visited ))
        {
            maxLen = max( maxLen, node->maxLeft + node->maxRight );
            node->_visited = true;
            nodeStack.pop();           
        }
    }
}

 

第12题（语法）
题目：求1+2+…+n，
要求不能使用乘除法、for、while、if、else、switch、case等关键字以及条件判断语句（A?B:C）。

    Sorehead：说实话，我比较反感这种题目，这不是什么算法，就是一些纯技巧方面的东西，有点像我们很多考试的题目，根本就不能代表什么。
    刚看到这个题目，我的第一想法就是多半只能用递规解决，接下来难点就是递规如何结束。题目的要求是比较苛刻的，楼主答案里面用的两种方法确实挺巧妙的，但我不会C++，因此只能另外想办法。

下面是我写的代码：

int sum(int n)
{
        int val = 0;

        n > 0 && (val = n + sum(n - 1));

        return val;
}

虽然功能是实现了，但这个代码编译时是有警告的，当然这个警告不重要。但我总觉得有更加合适的方法。

或者如leeyunce所说：
思路：模板元编程，最快捷的计算方式，编译期完成计算

#include
using namespace std;

template
struct CalCls
{
    enum {sum = CalCls::sum + N};
};

template<>
struct CalCls<0>
{   
    enum {sum = 0};
};

int main()
{
    cout<<"1+2+3+...+100 = "<::sum<    return 0;
}

另，一位兄台，短短三行代码想解决第12题，是否正确列?：

int sum(int n)
{
    return ((n * (n+1))>>1);
} 

第13题（链表）：
题目：输入一个单向链表，输出该链表中倒数第k个结点。链表的倒数第0个结点为链表的尾指针。
链表结点定义如下： 
struct ListNode
{
  int m_nKey;
  ListNode* m_pNext;
};

思路和楼主一致，下面是我写的代码，只是判断上多一些。
       list *list_find_desc(list *head, int k)
      {
                list *p, *q;

        if (head == NULL || k <0)
                return NULL;

        p = head;
        while (p != NULL && k-- >= 0)
        {
                p = p->next;
        }
        if (p == NULL)
                return k <0 ? head : NULL;
       
        q = head;
        while (p != NULL)
        {
                p = p->next;
                q = q->next;
        }
       
        return q;
}

第14题（数组）：
题目：输入一个已经按升序排序过的数组和一个数字，
在数组中查找两个数，使得它们的和正好是输入的那个数字。
要求时间复杂度是O(n)。如果有多对数字的和等于输入的数字，输出任意一对即可。
例如输入数组1、2、4、7、11、15和数字15。由于4+11=15，因此输出4和11。

    思路和楼主一致，这个题目比较简单，尤其是还排好序。楼主提供的另外一个思路也挺好，我还真没想到。

他说的是指以下这个思路：
2.第14题，还有一种思路，如下俩个数组：
1、 2、  4、7、11、15     //用15减一下为
14、13、11、8、4、 0      //如果下面出现了和上面一样的数，稍加判断，就能找出这俩个数来了。

第一个数组向右扫描，第二个数组向左扫描。

第15题（树）：
题目：输入一颗二元查找树，将该树转换为它的镜像，
即在转换后的二元查找树中，左子树的结点都大于右子树的结点。
用递归和循环两种方法完成树的镜像转换。 
例如输入：
  8
  / \
  6 10
 /\ /\
5 7 9 11

输出：
   8
  / \
 10 6
 /\ /\
11 9 7 5

定义二元查找树的结点为：
struct BSTreeNode // a node in the binary search tree (BST)
{
  int m_nValue; // value of node
  BSTreeNode *m_pLeft; // left child of node
  BSTreeNode *m_pRight; // right child of node
};

这个题目也比较简单，对树的基本操作比较了解，很快就能写出这个代码。
但我不大推荐楼主非递规代码采用的方法，使用一个stack来实现，这种写法和递规看上去基本就是一回事，此外，这种方法是按照层次进行遍历，堆栈中要保存的数据相应也比较多，最大值是某一层最大的节点数量。

本人再多说点：

方案1，引用自网友zhedahht：
就是递归 翻转树，有子树则递归翻转子树。

//July、2010/10/19
void Revertsetree(list *root)
{
    if(!root)
       return;
    list *p;

    p=root->leftch;
    root->leftch=root->rightch;
    root->rightch=p;   //以上三行，就是简单的交换工作。

    if(root->leftch)
      Revertsetree(root->leftch);
    if(root->rightch)
      Revertsetree(root->rightch);
}

方案2：
由于递归的本质是编译器生成了一个函数调用的栈，
因此用循环来完成同样任务时最简单的办法就是用一个辅助栈来模拟递归。

首先我们把树的头结点放入栈中。
在循环中，只要栈不为空，弹出栈的栈顶结点，交换它的左右子树。

如果它有左子树，把它的左子树压入栈中；
如果它有右子树，把它的右子树压入栈中。
这样在下次循环中就能交换它儿子结点的左右子树了。

//再用辅助栈模拟递归，改成循环的（有误之处，望不吝指正）：

void Revertsetree(list *phead)
{
    if(!phead)
       return;

    stack stacklist;
    stacklist.push(phead);         //首先把树的头结点放入栈中。

    while(stacklist.size())
    //在循环中，只要栈不为空，弹出栈的栈顶结点，交换它的左右子树
    {
      list* pnode=stacklist.top();
      stacklist.pop();
  
      list *ptemp;
      ptemp=pnode->leftch;
      pnode->leftch=pnode->rightch;
      pnode->rightch=ptemp;

      if(pnode->leftch)
        stacklist.push(pnode->leftch);   //若有左子树，把它的左子树压入栈中
      if(pnode->rightch)
        stacklist.push(pnode->rightch);  //若有右子树，把它的右子树压入栈中
    }
}

第16题（树）：
题目（微软）：
输入一颗二元树，从上往下按层打印树的每个结点，同一层中按照从左往右的顺序打印。 
例如输入

   8
  / \
 6 10
/ \ / \
5 7 9 11

输出8 6 10 5 7 9 11。

一般遍历我们都是使用栈来实现，层次遍历显然不行，但队列先入先出正好可以用来实现这个。
下面是我写的代码：

#define QUEUE_LEN 128

typedef struct _tree
{
        int             key;
        struct _tree    *left;
        struct _tree    *right;
} tree;

void tree_level_traverse(tree *head)
{
        tree *queue[QUEUE_LEN];
        int front, rear;

        if (head == NULL)
                return;

        frOnt= 0;
        rear = 0;
        queue[rear++] = head;
        while (front != rear)
        {
                head = queue[front];
                frOnt= (front + 1) % QUEUE_LEN;
                printf("%d,", head->key);

                if (head->left != NULL)
                {
                        queue[rear] = head->left;
                        rear = (rear + 1) % QUEUE_LEN;
                }
                if (head->right != NULL)
                {
                        queue[rear] = head->right;
                        rear = (rear + 1) % QUEUE_LEN;
                }
        }
}

 

第17题（字符串）：
题目：在一个字符串中找到第一个只出现一次的字符。如输入abaccdeff，则输出b。 
分析：这道题是2006年google的一道笔试题。

    最快的方法就是采用Hash查找，基本就是采用楼主代码使用的方法。
    但是楼主代码中存在一个问题，使用pHashKey作为hashTable数组下标不是很好，应该进行一下unsigned char转换。不同的编译器对char处理不同，有些默认char为有符号，有些认为是无符号，标准好像没有说明这个。如果当作有符号处理，使用负数作为数组下标显然会出现问题的。

第18题（数组）：
题目：n个数字（0,1,…,n-1）形成一个圆圈，从数字0开始，
每次从这个圆圈中删除第m个数字（第一个为当前数字本身，第二个为当前数字的下一个数字）。
当一个数字删除后，从被删除数字的下一个继续删除第m个数字。
求出在这个圆圈中剩下的最后一个数字。

    说实话，这题我没想到什么好方法，只得采用笨办法来做，就和楼主答案一一样，只是我是用链表来做的。关于楼主答案二，我没想通原理是什么。

第19题（数组、递归）：
题目：定义Fibonacci数列如下： 
  / 0 n=0
f(n)= 1 n=1
  \ f(n-1)+f(n-2) n=2

输入n，用最快的方法求该数列的第n项。
分析：在很多C语言教科书中讲到递归函数的时候，都会用Fibonacci作为例子。
因此很多程序员对这道题的递归解法非常熟悉，但....。

我写的非递规方法和楼主的答案基本一致，下面是代码：

int fibonacci(int n)
{
        int a, b, i;

        if (n == 0)
                return 0;
        if (n == 1)
                return 1;

        a = 0;
        b = 1;
        for (i = 2; i <= n; i++)
        {
                b = a + b;
                a = b - a;
        }

        return b;
}

 简单的说，a、b就是用来保存f(n-1)、f(n-2)的值，a其实就是上次b的值，后来发现这个计算有点多余，每次循环其实是重复的，下面是优化后的代码，时间复杂度并没有变，但计算量减少不少：

int fibonacci2(int n)
{
        int m, a, b, i;
       
        if (n == 0)
                return 0;
        if (n == 1)
                return 1;
               
        m = n / 2;
        a = 0;
        b = 1;
        for (i = 0; i         {
                a = a + b;
                b = a + b;
        }

        return  (m * 2 == n) ? a : b;
}

我觉得肯定有比较简便的数学公式能够更加快速的计算出值来，期望楼主能说说时间复杂度为O(logn)的方法（公式比较繁琐，详情，请参见我的帖子：微软100题，维护地址第6页）。

 

第20题（字符串）：
题目：输入一个表示整数的字符串，把该字符串转换成整数并输出。
例如输入字符串"345"，则输出整数345。

这题目说简单也简单，不过要像楼主这样方方面面都考虑确实也不容易。
看了楼主的代码，有以下建议：
1、溢出的检查。和整型最大值做比较会永远返回假的，因为溢出后数据会自动取模。要想判断是否上溢，可以通过值是否变小了来进行判断。
2、错误处理，楼主使用g_nStatus全局变量，c语言里面用的是errno。但这种方式是存在一定问题的，个人觉得比较好的方式是函数增加一个输出参数，用来判断是否出错。
3、对于123abc这样的字符串，一般不认为是错误，而是输出123。

有任何问题，欢迎留言评论，不吝指正。也可以回复于此帖上：微软100题，维护地址。非常感谢。

---

版权声明：转载本BLOG内任何文章，请以超链接形式注明出处。