1.把二元查找树转变成排序的双向链表
题目：
输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。
要求不能创建任何新的结点，只调整指针的指向。
10
/ \
6 14
/ \ / \
4 8 12 16
转换成双向链表
4=6=8=10=12=14=16。
首先我们定义的二元查找树节点的数据结构如下：
struct BSTreeNode
{
int m_nValue; // value of node
BSTreeNode *m_pLeft; // left child of node
BSTreeNode *m_pRight; // right child of node
};

解答：
我们可以中序遍历整棵树。按照这个方式遍历树，比较小的结点先访问。如果我们每访问一个结点，假设之前访问过的结点已经调整成一个排序双向链表，我们再把调整当前结点的指针将其链接到链表的末尾。当所有结点都访问过之后，整棵树也就转换成一个排序双向链表了。
void ConvertNode(BSTreeNode* pNode, BSTreeNode*& pLastNodeInList)
{
      if(pNode == NULL)
            return;
      BSTreeNode *pCurrent = pNode;
      // Convert the left sub-tree
      if (pCurrent->m_pLeft != NULL)
            ConvertNode(pCurrent->m_pLeft, pLastNodeInList);
      // Put the current node into the double-linked list
      pCurrent->m_pLeft = pLastNodeInList;
      if(pLastNodeInList != NULL)
            pLastNodeInList->m_pRight = pCurrent;
      pLastNodeInList = pCurrent;
      // Convert the right sub-tree
      if (pCurrent->m_pRight != NULL)
            ConvertNode(pCurrent->m_pRight, pLastNodeInList);
}
//把二叉树转化为双向链表
BSTreeNode* ConvertToDoubleList(BSTreeNode* pHeadOfTree)
{
      BSTreeNode *pLastNodeInList = NULL;
      ConvertNode(pHeadOfTree, pLastNodeInList);
      // Get the head of the double-linked list
      BSTreeNode *pHeadOfList = pLastNodeInList;
      while(pHeadOfList && pHeadOfList->m_pLeft)
            pHeadOfList = pHeadOfList->m_pLeft;
      return pHeadOfList;
}

2、计包含min 函数的栈。

定义栈的数据结构，要求添加一个min 函数，能够得到栈的最小元素。
要求函数min、push 以及pop 的时间复杂度都是O(1)。

解答：

struct MinStackElement {

  int data;
  int min;
};

struct MinStack {
  MinStackElement * data;
  int size;
  int top;
}

MinStack MinStackInit(int maxSize) {
  MinStack stack;
  stack.size = maxSize;
  stack.data = (MinStackElement*) malloc(sizeof(MinStackElement)*maxSize);
  stack.top = 0;
  return stack;
}
void MinStackFree(MinStack stack) {
  free(stack.data);
}
void MinStackPush(MinStack stack, int d) {
  if (stack.top == stack.size) error(“out of stack space.”);
  MinStackElement* p = stack.data[stack.top];
  p->data = d;
  p->min = (stack.top==0?d : stack.data[top-1]);
  if (p->min > d) p->min = d;
  top ++;
}
int MinStackPop(MinStack stack) {
  if (stack.top == 0) error(“stack is empty!”);
  return stack.data[--stack.top].data;
}
int MinStackMin(MinStack stack) {
  if (stack.top == 0) error(“stack is empty!”);
  return stack.data[stack.top-1].min;
}

3、求子数组的最大和

题目：
输入一个整形数组，数组里有正数也有负数。
数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。
求所有子数组的和的最大值。要求时间复杂度为O(n)。
参考编程之美

4.在二元树中找出和为某一值的所有路径
题目：输入一个整数和一棵二元树。
从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。
打印出和与输入整数相等的所有路径。

简答递归，遍历树即可。

5.查找最小的k 个元素

堆排序

我们首先取前k个元素调整成最大堆，如果发现，然后扫描后面的数据，并与堆顶元素比较，如果比堆顶元素小，那么用该元素替换堆顶，然后再调整为最小堆。

6、给你10 分钟时间，根据上排给出十个数，在其下排填出对应的十个数
要求下排每个数都是先前上排那十个数在下排出现的次数。
上排的十个数如下：
【0，1，2，3，4，5，6，7，8，9】
举一个例子，
数值: 0,1,2,3,4,5,6,7,8,9
分配: 6,2,1,0,0,0,1,0,0,0

设0的个数为k，则下排有k个0，下排数据和为10，除了0下面的k外，还有9-k个非0数据，其和为10-k，故这些数据是个2,8-k个1，

0     1     2     3     .....9

k     8-k   1

k+8-k+1=9,故还有一个1，所以总共有2个1，8-k=2,

k=6.

7、微软亚院之编程判断俩个链表是否相交
给出俩个单向链表的头指针，比如h1，h2，判断这俩个链表是否相交。
为了简化问题，我们假设俩个链表均不带环。
问题扩展：
1.如果链表可能有环列?
2.如果需要求出俩个链表相交的第一个节点列?

判断相交，只需判断两个链表尾节点是否相同，

1、快慢指针，判断链表是否相遇

2、长链表指针先走k个节点

第8 题
此贴选一些比较怪的题，，由于其中题目本身与算法关系不大，仅考考思维。特此并作一题。

1.有两个房间，一间房里有三盏灯，另一间房有控制着三盏灯的三个开关，
这两个房间是分割开的，从一间里不能看到另一间的情况。
现在要求受训者分别进这两房间一次，然后判断出这三盏灯分别是由哪个开关控制的。
有什么办法呢？

2.你让一些人为你工作了七天，你要用一根金条作为报酬。金条被分成七小块，每天给出一
块。
如果你只能将金条切割两次，你怎样分给这些工人?
ANSWER:
1+2+4;

3. 用一种算法来颠倒一个链接表的顺序。现在在不用递归式的情况下做一遍。
ANSWER:
Node * reverse(Node * head) {
  if (head == NULL) return head;
  if (head->next == NULL) return head;
  Node * ph = reverse(head->next);
  head->next->next = head;
  head->next = NULL;
  return ph;
}
Node * reverseNonrecurisve(Node * head) {
  if (head == NULL) return head;
  Node * p = head;
  Node * previous = NULL;
  while (p->next != NULL) {
    p->next = previous;
    previous = p;
    p = p->next;
  }
  p->next = previous;
  return p;
}

4、颠倒一个字符串。优化速度。优化空间。
void reverse(char *str) {
  reverseFixlen(str, strlen(str));
}
void reverseFixlen(char *str, int n) {
  char* p = str+n-1;
  while (str < p) {
    char c = *str;
    *str = *p; *p=c;
  }   
}

5、颠倒一个句子中的词的顺序，比如将“我叫克丽丝”转换为“克丽丝叫我”，
实现速度最快，移动最少。

6、假设你有一个用1001 个整数组成的数组，这些整数是任意排列的，但是你知道所有的整数都在1 到1000(包括1000)之间。此外，除一个数字出现两次外，其他所有数字只出现一次。假设你只能对这个数组做一次处理，用一种算法找出重复的那个数字。如果你在运算中使用了辅助的存储方式，那么你能找到不用这种方式的算法吗?

相加再减去sum（1,1000）。

第9 题
判断整数序列是不是二元查找树的后序遍历结果
题目：输入一个整数数组，判断该数组是不是某二元查找树的后序遍历的结果。
如果是返回true，否则返回false。

10、翻转句子中单词的顺序。
题目：输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。
句子中单词以空格符隔开。为简单起见，标点符号和普通字母一样处理。
例如输入“I am a student.”，则输出“student. a am I”。

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

     

struct NODE {     NODE *pLeft;     NODE *pRight; };    struct RESULT {     int nMaxDistance;     int nMaxDepth; };    RESULT GetMaximumDistance(NODE* root) {     if (!root)     {         RESULT empty = { 0, -1 };   // trick: nMaxDepth is -1 and then caller will plus 1 to balance it as zero.         return empty;     }        RESULT lhs = GetMaximumDistance(root->pLeft);     RESULT rhs = GetMaximumDistance(root->pRight);        RESULT result;     result.nMaxDepth = max(lhs.nMaxDepth + 1, rhs.nMaxDepth + 1);     result.nMaxDistance = max(max(lhs.nMaxDistance, rhs.nMaxDistance), lhs.nMaxDepth + rhs.nMaxDepth + 2);     return result; } 第12 题 题目：求1+2+…+n， 要求不能使用乘除法、for、while、if、else、switch、case 等关键字以及条件判断语句 （A?B:C）。 采用static成员变量。 第13 题： 题目：输入一个单向链表，输出该链表中倒数第k 个结点。链表的倒数第0 个结点为链表的尾指针。 两个指针。 第14 题： 题目：输入一个已经按升序排序过的数组和一个数字， 在数组中查找两个数，使得它们的和正好是输入的那个数字。 要求时间复杂度是O(n)。如果有多对数字的和等于输入的数字，输出任意一对即可。 void find2Number(int a[], int n, int dest) {   int *f = a, *e=a+n-1;   int sum = *f + *e;   while (sum != dest && f < e) {     if (sum < dest) ++f;     else --e;     sum = *f + *e;   }   if (sum == dest) printf(“%d, %d\n”, *f, *e); } 第15 题： 题目：输入一颗二元查找树，将该树转换为它的镜像， 即在转换后的二元查找树中，左子树的结点都大于右子树的结点。 用递归和循环两种方法完成树的镜像转换。 void swap(Node ** l, Node ** r) {   Node * p = *l;   *l = *r;   *r = p; } void mirror(Node * root) {   if (root == NULL) return;   swap(&(root->left), &(root->right));   mirror(root->left);   mirror(root->right); } void mirrorIteratively(Node * root) {   if (root == NULL) return;   stack<Node*> buf;   buf.push(root);   while (!stack.empty()) {     Node * n = stack.pop();     swap(&(root->left), &(root->right));     if (root->left != NULL) buf.push(root->left);     if (root->right != NULL) buf.push(root->right);   } } 第16 题： 题目（微软）： 输入一颗二元树，从上往下按层打印树的每个结点，同一层中按照从左往右的顺序打印。 例如输入 8 / \ 6 10 / \ / \ 5 7 9 11 输出8 6 10 5 7 9 11。 void printByLevel(Node root) {   Node sentinel = new Node();   LinkedList<Node> q=new LinkedList<Node>();   q.addFirst(root); q.addFirst(sentinel);   while (!q.isEmpty()) {     Node n = q.removeLast();     if (n==sentinel) {       System.out.println(“\n”);       q.addFirst(sentinel);     } else {       System.out.println(n);       if (n.left() != null) q.addFirst(n.left());       if (n.right()!=null) q.addFirst(n.right());      }      } } 第17 题： 题目：在一个字符串中找到第一个只出现一次的字符。如输入abaccdeff，则输出b。 char firstSingle(char * str) {   int a[255];   memset(a, 0, 255*sizeof(int));   char *p=str;   while (*p!=’\0’) {     a[*p] ++;     p++;   }   p = str;   while (*p!=’\0’) {     if (a[*p] == 1) return *p;   }   return ‘\0’; // this must the one that occurs exact 1 time. }

第18 题： 题目：n 个数字（0,1,…,n-1）形成一个圆圈，从数字0 开始， 每次从这个圆圈中删除第m 个数字（第一个为当前数字本身，第二个为当前数字的下一个数 字）。 当一个数字删除后，从被删除数字的下一个继续删除第m 个数字。 求出在这个圆圈中剩下的最后一个数字。 int LastNumber(unsigned int n, unsigned int m)   {     if (n<=0||m<=0||n<m)     {         return -1;     }     int lastinteger=m-1;     for (int i=m+1;i<=n;i++)     {         lastinteger=(lastinteger+m)%i;     }     return lastinteger; } int _tmain(int argc, _TCHAR* argv[]) {     unsigned int n,m;     scanf("%d",&n);     scanf("%d",&m);     int k =LastNumber(n,m);     printf("%d",k);     getchar();     getchar();     return 0; } 19、题目：定义Fibonacci 数列如下： / 0 n=0 f(n)= 1 n=1 \ f(n-1)+f(n-2) n=2 输入n，用最快的方法求该数列的第n 项。 第20 题： 题目：输入一个表示整数的字符串，把该字符串转换成整数并输出。 例如输入字符串"345"，则输出整数345。 第21 题 2010 年中兴面试题 编程求解： 输入两个整数n 和m，从数列1，2，3.......n 中随意取几个数, 使其和等于m ,要求将其中所有的可能组合列出来. void findCombination(int n, int m) {   if (n>m) findCombination(m, m);   int aux[n];   memset(aux, 0, n*sizeof(int));   helper(m, 0, aux); } void helper(int dest, int idx, int aux[], int n) {   if (dest == 0)     dump(aux, n);   if (dest <= 0 || idx==n) return;   helper(dest, idx+1, aux, n);   aux[idx] = 1;   helper(dest-idx-1, idx+1, aux, n);   aux[idx] = 0; } void dump(int aux[], int n) {   for (int i=0; i<n; i++)     if (aux) printf(“%3d”, i+1);   printf(“\n”); } 第22 题： 有4 张红色的牌和4 张蓝色的牌，主持人先拿任意两张，再分别在A、B、C 三人额头上贴任意两张牌，A、B、C 三人都可以看见其余两人额头上的牌，看完后让他们猜自己额头上是什么颜色的牌，A 说不知道，B 说不知道，C 说不知道，然后A 说知道了。 思路：目的是推导出A的颜色，由于A先看B、C,则应先假定B、C的颜色然后推导A 分析：头上可能出现的牌为 bb、rr、rb（blue 、red）             A：不知道 说明  B 、C中颜色相加没有等于4的牌             B：不知道 说明  A、C中颜色相加没有等于4的牌             C：不知道 说明  A、B中颜色相加没有等于4的牌       过程：1>  B:rr(bb)   C:rr(bb)    A肯定知道，所以不符合要求            2>         B:rr(bb)   C:bb(rr)    A不知道，由于B不知道，C不知道 所以A只能取  rb            3>  B:rr     C：rb    C不知道->A不是rr  A若是bb ->C根据A、B判断可以知道自己为rb，但C不知道，所以排除bb   A=rb                  B:bb   C：rb    同理可证A=rb                  B:rb    C：rr     同理可证A=rb                  B:rb    C：bb    同理可证A=rb            4>  B:rb    C：rb     如果A=rr       B=rb     C猜如果自己=bb  则B不可能不知道自己为rb  所以C可以猜到C=rb                                             如果A=bb     B=rb      同理C可以猜到自己=rb                                             由于A排除了rr   bb 所以只能取  A=rb 结论：不能同时存在rr和bb，A不能是rr和bb 第23 题： 用最简单，最快速的方法计算出下面这个圆形是否和正方形相交。 第24 题： 链表操作， （1）.单链表就地逆置， （2）合并链表 第25 题： 写一个函数,它的原形是int continumax(char *outputstr,char *intputstr) 功能： 在字符串中找出连续最长的数字串，并把这个串的长度返回， 并把这个最长数字串付给其中一个函数参数outputstr 所指内存。 例如："abcd12345ed125ss123456789"的首地址传给intputstr 后，函数将返回9， outputstr 所指的值为123456789

沙发。。楼主辛苦了

这我看过，题题精品

就是帖子太长了 排版不太好弄 不过sissi辛苦啦~

帖子不错，怒马一记