微软等面试100题系列--（61-80）

61.找出数组中两个只出现一次的数字（数组）
题目：一个整型数组里除了两个数字之外，其他的数字都出现了两次。
请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

分析：这是一道很新颖的关于位运算的面试题。

使用异或运算，参考http://blog.csdn.net/stormbjm/article/details/8925749

62.找出链表的第一个公共结点（链表）。
题目：两个单向链表，找出它们的第一个公共结点。

链表的结点定义为：
struct ListNode

{

      int         m_nKey;

      ListNode*   m_pNext;

};

分析：这是一道微软的面试题。微软非常喜欢与链表相关的题目，
因此在微软的面试题中，链表出现的概率相当高。

参考：http://blog.csdn.net/stormbjm/article/details/8847501

63.在字符串中删除特定的字符（字符串）。
题目：输入两个字符串，从第一字符串中删除第二个字符串中所有的字符。

例如，输入”They are students.”和”aeiou”，

则删除之后的第一个字符串变成”Thy r stdnts.”。

分析：这是一道微软面试题。在微软的常见面试题中，与字符串相关的题目占了很大的一部分，
因为写程序操作字符串能很好的反映我们的编程基本功。

  思路：通过两个指针避免每次删除字符时都要以后后面的所有字符，再加上哈希。

  参考：http://blog.csdn.net/stormbjm/article/details/8926020

64. 寻找丑数（运算）。
题目：我们把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，
但14不是，因为它包含因子7。习惯上我们把1当做是第一个丑数。
求按从小到大的顺序的第1500个丑数。

分析：这是一道在网络上广为流传的面试题，据说google曾经采用过这道题。

   参考：http://www.cnblogs.com/mingzi/archive/2009/08/04/1538491.html

     http://www.cppblog.com/zenliang/articles/131094.html

65.输出1到最大的N位数（运算）
题目：输入数字n，按顺序输出从1最大的n位10进制数。比如输入3，

则输出1、2、3一直到最大的3位数即999。
分析：这是一道很有意思的题目。看起来很简单，其实里面却有不少的玄机。

66.颠倒栈（栈）。
题目：用递归颠倒一个栈。例如输入栈{1, 2, 3, 4, 5}，1在栈顶。
颠倒之后的栈为{5, 4, 3, 2, 1}，5处在栈顶。

参考：http://blog.csdn.net/cxllyg/article/details/7655935

67.俩个闲玩娱乐（运算）。

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

参考：http://blog.csdn.net/tianshuai11/article/details/7908102

2.n个骰子的点数。
把n个骰子扔在地上，所有骰子朝上一面的点数之和为S。输入n，
打印出S的所有可能的值出现的概率。

参考：http://blog.csdn.net/tianshuai11/article/details/7908102

68.把数组排成最小的数（数组、算法）。
题目：输入一个正整数数组，将它们连接起来排成一个数，输出能排出的所有数字中最小的一个。
例如输入数组{32,  321}，则输出这两个能排成的最小数字32132。
请给出解决问题的算法，并证明该算法。

分析：这是09年6月份百度的一道面试题，
从这道题我们可以看出百度对应聘者在算法方面有很高的要求。

参考http://blog.csdn.net/tianshuai11/article/details/7908102

69.旋转数组中的最小元素（数组、算法）。
题目：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个排好序的数组的一个旋转，

输出旋转数组的最小元素。例如数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转，该数组的最小值为1。

    分析：这道题最直观的解法并不难。从头到尾遍历数组一次，就能找出最小的元素，
时间复杂度显然是O(N)。但这个思路没有利用输入数组的特性，我们应该能找到更好的解法。

http://blog.csdn.net/tianshuai11/article/details/7908102

70.给出一个函数来输出一个字符串的所有排列（经典字符串问题）。
ANSWER 简单的回溯就可以实现了。当然排列的产生也有很多种算法，去看看组合数学，

还有逆序生成排列和一些不需要递归生成排列的方法。
印象中Knuth的第一卷里面深入讲了排列的生成。这些算法的理解需要一定的数学功底，
也需要一定的灵感，有兴趣最好看看。

http://blog.csdn.net/stormbjm/article/details/8853381

http://blog.csdn.net/stormbjm/article/details/8855366

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;
}
ANSWER

…

double power(double base, int exp) {
  if (exp == 1) return base;
  double half = power(base, exp >> 1);
  return (((exp & 1) == 1) ? base : 1.0) * half * half;
}

72. 题目：设计一个类，我们只能生成该类的一个实例。
分析：只能生成一个实例的类是实现了Singleton 模式的类型。
ANSWER
I’m not good at multithread programming... But if we set a lazy initialization, the “if” condition could be interrupted thus multiple constructor could be called, so we must add synchronized to the if judgements, which is a loss of efficiency. Putting it to the static initialization will guarantee that the constructor only be executed once by the java class loader.
public class Singleton {
  private static Singleton instance = new Singleton();
  private synchronized Singleton() {
  }
  public Singleton getInstance() {
    return instance();
  }
}
This may not be correct. I’m quite bad at this...

73.对称字符串的最大长度（字符串）。

题目：输入一个字符串，输出该字符串中对称的子字符串的最大长度。
比如输入字符串“google”，由于该字符串里最长的对称子字符串是“goog”，因此输出4。

分析：可能很多人都写过判断一个字符串是不是对称的函数，这个题目可以看成是该函数的加强版。

思路：最长回文数http://blog.csdn.net/stormbjm/article/details/8737446

74.数组中超过出现次数超过一半的数字（数组）

题目：数组中有一个数字出现的次数超过了数组长度的一半，找出这个数字。

分析：这是一道广为流传的面试题，包括百度、微软和Google在内的多家公司都
曾经采用过这个题目。要几十分钟的时间里很好地解答这道题，
除了较好的编程能力之外，还需要较快的反应和较强的逻辑思维能力。

思路：两数字不相同就相消

Delete every two different digits. The last one that left is the one.
int getMajor(int a[], int n) {
  int x, cnt=0;
  for (int i=0; i       x = a[i]; cnt++;
    } else if (a[i]==x) {
      cnt ++;
    } else {
      cnt --;
    }     
  }
  return x;
}

75.二叉树两个结点的最低共同父结点
题目：二叉树的结点定义如下：
struct TreeNode
{
int m_nvalue;
TreeNode* m_pLeft;
TreeNode* m_pRight;
};
输入二叉树中的两个结点，输出这两个结点在数中最低的共同父结点。
分析：求数中两个结点的最低共同结点是面试中经常出现的一个问题。这个问题至少有两个
变种。

TreeNode* getLCA(TreeNode* root, TreeNode* X, TreeNode *Y) {
  if (root == NULL) return NULL;
  if (X == root || Y == root) return root;
  TreeNode * left = getLCA(root->m_pLeft, X, Y);
  TreeNode * right = getLCA(root->m_pRight, X, Y);
  if (left == NULL) return right;
  else if (right == NULL) return left;
  else return root;
}

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)，以复制一个复杂链表。 
分析：在常见的数据结构上稍加变化，这是一种很新颖的面试题。
要在不到一个小时的时间里解决这种类型的题目，我们需要较快的反应能力，
对数据结构透彻的理解以及扎实的编程功底。

参考：http://blog.csdn.net/stormbjm/article/details/8931007

77.关于链表问题的面试题目如下（链表）：

1.给定单链表，检测是否有环。
 使用两个指针p1,p2从链表头开始遍历，p1每次前进一步，p2每次前进两步。如果p2到达链表尾部，
说明无环，否则p1、p2必然会在某个时刻相遇(p1==p2)，从而检测到链表中有环。

2.给定两个单链表(head1, head2)，检测两个链表是否有交点，如果有返回第一个交点。

        如果head1==head2，那么显然相交，直接返回head1。
否则，分别从head1,head2开始遍历两个链表获得其长度len1与len2，假设len1>=len2，
那么指针p1由head1开始向后移动len1-len2步，指针p2=head2，
下面p1、p2每次向后前进一步并比较p1p2是否相等，如果相等即返回该结点，
否则说明两个链表没有交点。

3.给定单链表(head)，如果有环的话请返回从头结点进入环的第一个节点。
        运用题一，我们可以检查链表中是否有环。
        如果有环，那么p1p2重合点p必然在环中。从p点断开环，
方法为：p1=p, p2=p->next, p->next=NULL。此时，原单链表可以看作两条单链表，
一条从head开始，另一条从p2开始，于是运用题二的方法，我们找到它们的第一个交点即为所求。

4.只给定单链表中某个结点p(并非最后一个结点，即p->next!=NULL)指针，删除该结点。
 办法很简单，首先是放p中数据,然后将p->next的数据copy入p中，接下来删除p->next即可。

5.只给定单链表中某个结点p(非空结点)，在p前面插入一个结点。
  办法与前者类似，首先分配一个结点q，将q插入在p后，接下来将p中的数据copy入q中，
然后再将要插入的数据记录在p中。

78.链表和数组的区别在哪里（链表、数组）？

分析：主要在基本概念上的理解。
但是最好能考虑的全面一点，现在公司招人的竞争可能就在细节上产生，
谁比较仔细，谁获胜的机会就大。

79.
1.编写实现链表排序的一种算法。说明为什么你会选择用这样的方法？
ANSWER
For linked list sorting, usually mergesort is the best choice. Pros: O(1) auxilary space, compared to array merge sort. No node creation, just pointer operations. 
Node * linkedListMergeSort(Node * pHead) {
  int len = getLen(pHead);
  return mergeSort(pHead, len);
}

Node * mergeSort(Node * p, int len) {
  if (len == 1) { p->next = NULL; return p; }
  Node * pmid = p;
  for (int i=0; inext;
  }
  Node * p1 = mergeSort(p, len/2);
  Node * p2 = mergeSort(pmid, len - len/2);
  return merge(p1, p2);
}
Node * merge(Node * p1, Node * p2) {
  Node * p = NULL, * ph = NULL;
  while (p1!=NULL && p2!=NULL) {
    if (p1->datadata) {
      if (ph == NULL) {ph = p = p1;}
      else { p->next = p1; p1 = p1->next; p = p->next;}
    } else {
      if (ph == NULL) {ph = p = p2;}
      else { p->next = p2; p2 = p2->next; p = p->next;}
    }
  }
  p->next = (p1==NULL) ? p2 : p1;
  return ph;
} 

2.编写实现数组排序的一种算法。说明为什么你会选择用这样的方法？

3.请编写能直接实现strstr()函数功能的代码。

80.阿里巴巴一道笔试题（运算、算法）

问题描述:
12个高矮不同的人,排成两排,每排必须是从矮到高排列,而且第二排比对应的第一排的人高,问排列方式有多少种?
这个笔试题,很YD,因为把某个递归关系隐藏得很深。