[整理III]微软等数据结构+算法经典面试100题[第61-80题]
[整理III]精选微软等数据结构+算法经典面试100题[第61-80题]
微软等公司数据结构+算法面试100题系列回顾：
--------------------------------
1.最初 发表于：2010-10-11 16:38:33
算法面试：精选微软经典的算法面试100题 [每周更新]
http://topic.csdn.net/u/20101011/16/2befbfd9-f3e4-41c5-bb31-814e9615832e.html
2.随后，整理了前40题，得到了推荐：
[整理]算法面试：精选微软经典的算法面试100题[前40题] [推荐]
http://topic.csdn.net/u/20101023/20/5652ccd7-d510-4c10-9671-307a56006e6d.html
现今，这俩帖子，都已结帖。
3.然后，写了一评论，思考了下，我发这些题的意义：
http://topic.csdn.net/u/20101117/17/b96478c3-32fc-47bc-981b-abf16d3f66da.html?16363#replyachor
分析：简单的回溯就可以实现了。当然排列的产生也有很多种算法，去看看组合数学，
还有逆序生成排列和一些不需要递归生成排列的方法。
印象中Knuth的<TAOCP>第一卷里面深入讲了排列的生成。
这些算法的理解需要一定的数学功底，
也需要一定的灵感，有兴趣最好看看。
71.数值的整数次方。
题目：实现函数double Power(double base, int exponent)，求base的exponent次方。
不需要考虑溢出。
分析：这是一道看起来很简单的问题。可能有不少的人在看到题目后30秒写出如下的代码：
double Power(double base, int exponent)
{
double result = 1.0;
for(int i = 1; i <= exponent; ++i)
result *= base;
return result;
}
72.
题目：设计一个类，我们只能生成该类的一个实例。
分析：只能生成一个实例的类是实现了Singleton模式的类型。
73.对策字符串的最大长度。
题目：输入一个字符串，输出该字符串中对称的子字符串的最大长度。
比如输入字符串“google”，由于该字符串里最长的对称子字符串是“goog”，因此输出4。
分析：可能很多人都写过判断一个字符串是不是对称的函数，这个题目可以看成是该函数的加强版。
74.数组中超过出现次数超过一半的数字
题目：数组中有一个数字出现的次数超过了数组长度的一半，找出这个数字。
分析：这是一道广为流传的面试题，包括百度、微软和Google在内的多家公司
都曾经采用过这个题目。要几十分钟的时间里很好地解答这道题，除了较好的编程能力之外，
还需要较快的反应和较强的逻辑思维能力。
75.二叉树两个结点的最低共同父结点
题目：二叉树的结点定义如下：
struct TreeNode
{
int m_nvalue;
TreeNode* m_pLeft;
TreeNode* m_pRight;
};
输入二叉树中的两个结点，输出这两个结点在数中最低的共同父结点。
分析：求数中两个结点的最低共同结点是面试中经常出现的一个问题。这个问题至少有两个变种。
76.复杂链表的复制
题目：有一个复杂链表，其结点除了有一个m_pNext指针指向下一个结点外，
还有一个m_pSibling指向链表中的任一结点或者NULL。其结点的C++定义如下：
struct ComplexNode
{
int m_nValue;
ComplexNode* m_pNext;
ComplexNode* m_pSibling;
};
下图是一个含有5个结点的该类型复杂链表。
图中实线箭头表示m_pNext指针，虚线箭头表示m_pSibling指针。
为简单起见，指向NULL的指针没有画出。
请完成函数ComplexNode* Clone(ComplexNode* pHead)，以复制一个复杂链表。
//图，接下来，自会补上。July、11.19.
分析：在常见的数据结构上稍加变化，这是一种很新颖的面试题。
要在不到一个小时的时间里解决这种类型的题目，
我们需要较快的反应能力，对数据结构透彻的理解以及扎实的编程功底。
77.关于链表问题的面试题目如下：
题一、 给定单链表，检测是否有环。
使用两个指针p1,p2从链表头开始遍历，p1每次前进一步，p2每次前进两步。
如果p2到达链表尾部，说明无环，否则p1、p2必然会在某个时刻相遇(p1==p2)，从而检测到链表中有环。
题二、 给定两个单链表(head1, head2)，检测两个链表是否有交点，如果有返回第一个交点。
如果head1==head2，那么显然相交，直接返回head1。
否则，分别从head1,head2开始遍历两个链表获得其长度len1与len2，假设len1>=len2，
那么指针p1由head1开始向后移动len1-len2步，指针p2=head2，
下面p1、p2每次向后前进一步并比较p1p2是否相等，如果相等即返回该结点，
否则说明两个链表没有交点。
题三、 给定单链表(head)，如果有环的话请返回从头结点进入环的第一个节点。
运用题一，我们可以检查链表中是否有环。
如果有环，那么p1p2重合点p必然在环中。从p点断开环，方法为：p1=p, p2=p->next,
p->next=NULL。此时，原单链表可以看作两条单链表，一条从head开始，另一条从p2开始，
于是运用题二的方法，我们找到它们的第一个交点即为所求。
题四、只给定单链表中某个结点p(并非最后一个结点，即p->next!=NULL)指针，删除该结点。
办法很简单，首先是放p中数据,然后将p->next的数据copy入p中，接下来删除p->next即可。
题五、只给定单链表中某个结点p(非空结点)，在p前面插入一个结点。
办法与前者类似，首先分配一个结点q，将q插入在p后，
接下来将p中的数据copy入q中，然后再将要插入的数据记录在p中。
78.链表和数组的区别在哪里？
分析：主要在基本概念上的理解。
但是最好能考虑的全面一点，现在公司招人的竞争可能就在细节上产生，
谁比较仔细，谁获胜的机会就大。
79.
1.编写实现链表排序的一种算法。说明为什么你会选择用这样的方法？
2.编写实现数组排序的一种算法。说明为什么你会选择用这样的方法？
3.请编写能直接实现strstr()函数功能的代码。
80.阿里巴巴一道笔试题
引自baihacker
问题描述:
12个高矮不同的人,排成两排,每排必须是从矮到高排列,而且第二排比对应的第一排的人高,问排列方式有多少种?
这个笔试题,很YD,因为把某个递归关系隐藏得很深.
//第81-100题正在整理中。
--------------------------------------
本人July对以上所有任何内容和资料享有版权，转载请注明出处。
向你的厚道致敬。谢谢。
欢迎，各位初学者，新手，好手，高手，行家，专家，一起交流，思考这些题目。
好好享受，祝旅途愉快。Good Trip。
致敬。谢谢。
2010年11月19日。
[解决办法]
很好很强大
[解决办法]
不顶下辈子还是中国人！
------解决方案--------------------
[解决办法]
