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

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

2.字符串
题目：在一个字符串中找到第一个只出现一次的字符。如输入abaccdeff，则输出b。

答案：

#include <iostream.h>
#include <string.h>

char FirstNotRepeatingChar(char* pString)
{
      if(!pString)
            return 0;

      const int tableSize = 256;
      unsigned int hashTable[tableSize];
      for(unsigned int i = 0; i < tableSize; ++ i)
            hashTable[i] = 0;

      char* pHashKey = pString;
      while(*(pHashKey) != '/0')
            hashTable[*(pHashKey++)] ++;

      pHashKey = pString;
      while(*pHashKey != '/0')
      {
            if(hashTable[*pHashKey] == 1)
                  return *pHashKey;

            pHashKey++;
      }
      return *pHashKey;
}

int main()
{
    cout<<"请输入一串字符："<<endl;
    char s[100];
    cin>>s;
    char* ps=s;
    cout<<FirstNotRepeatingChar(ps)<<endl;
    return 0;
}

3
写一个函数,它的原形是int continumax(char *outputstr,char *intputstr)
功能：
在字符串中找出连续最长的数字串，并把这个串的长度返回，
并把这个最长数字串付给其中一个函数参数outputstr所指内存。
例如："abcd12345ed125ss123456789"的首地址传给intputstr后，函数将返回9，
outputstr所指的值为123456789

答案：

int continumax(char *outputstr, char *intputstr)
{
    int i, maxlen = 0;
    char * maxstr = 0;

    while (true)
    {  
        while (intputstr && (*intputstr<'0' || *intputstr>'9')) //skip all non-digit

characters
        {  
            intputstr++;
        }

        if (!intputstr) break;

        int count = 0;
        char * tempstr = intputstr;
        while (intputstr && (*intputstr>='0' && *intputstr<='9')) //OK, these characters are

digits
        {  
            count++;
            intputstr++;
        }
        if (count > maxlen)
        {  
            maxlen = count;
            maxstr = tempstr;
        }
    }

    for (i=0; i<maxlen; i++)
    {  
        outputstr[i] = maxstr[i];
    }

    outputstr[i] = 0;

    return maxlen;
}

4.跳台阶问题
题目：一个台阶总共有n级，如果一次可以跳1级，也可以跳2级。
求总共有多少总跳法，并分析算法的时间复杂度。

答案：首先我们考虑最简单的情况。如果只有1级台阶，那显然只有一种跳法。
如果有2级台阶，那就有两种跳的方法了：一种是分两次跳，每次跳1级；另外一种就是一次跳2级。

现在我们再来讨论一般情况。我们把n级台阶时的跳法看成是n的函数，记为f(n)。
当n>2时，第一次跳的时候就有两种不同的选择：一是第一次只跳1级，
此时跳法数目等于后面剩下的n-1级台阶的跳法数目，即为f(n-1)；
另外一种选择是第一次跳2级，此时跳法数目等于后面剩下的n-2级台阶的跳法数目，即为f(n-2)。
因此n级台阶时的不同跳法的总数f(n)=f(n-1)+(f-2)。

我们把上面的分析用一个公式总结如下：

        /  1                          n=1
f(n)=      2                          n=2
        /  f(n-1)+(f-2)               n>2

分析到这里，相信很多人都能看出这就是我们熟悉的Fibonacci序列。

int jump_sum(int n)  //递归版本
{
    assert(n>0);
    if (n == 1 || n == 2) return n;
    return jump_sum(n-1)+jump_sum(n-2);
}

int jump_sum(int n) //迭代版本
{
    assert(n>0);
    if (n == 1 || n == 2) return n;

    int an, an_1=2, an_2=1;
    for (; n>=3; n--)
    {  
        an = an_2 + an_1;
        an_2 = an_1;
        an_1 = an;
    }
    return an;
}

5.在从1到n的正数中1出现的次数
题目：输入一个整数n，求从1到n这n个整数的十进制表示中1出现的次数。

例如输入12，从1到12这些整数中包含1 的数字有1，10，11和12，1一共出现了5次。
答案:

我们每次判断整数的个位数字是不是1。如果这个数字大于10，除以10之后再判断个位数字是不是1。
基于这个思路，不难写出如下的代码：*/

int NumberOf1(unsigned int n);

int NumberOf1BeforeBetween1AndN_Solution1(unsigned int n)
{
      int number = 0;

      // Find the number of 1 in each integer between 1 and n
      for(unsigned int i = 1; i <= n; ++ i)
            number += NumberOf1(i);

      return number;
}

int NumberOf1(unsigned int n)
{
      int number = 0;
      while(n)
      {
            if(n % 10 == 1)
                  number ++;

            n = n / 10;
      }

      return number;
}

6.和为n连续正数序列。
题目：输入一个正数n，输出所有和为n连续正数序列。
例如输入15，由于1+2+3+4+5=4+5+6=7+8=15，所以输出3个连续序列1-5、4-6和7-8。
答案：
这道题和本微软面试100题系列V0.1版的第14题有些类似。

我们可用两个数small和big分别表示序列的最小值和最大值。首先把small初始化为1，big初始化为2。
如果从small到big的序列的和大于n的话，我们向右移动small，相当于从序列中去掉较小的数字。
如果从small到big的序列的和小于n的话，我们向右移动big，相当于向序列中添加big的下一个数字。
一直到small等于(1+n)/2，因为序列至少要有两个数字。

基于这个思路，我们可以写出如下代码:
void PrintContinuousSequence(int small, int big);

// Find continuous sequence, whose sum is n
void FindContinuousSequence(int n)
{
      if(n < 3)
            return;

      int small = 1;
      int big = 2;
      int middle = (1 + n) / 2;
      int sum = small + big;

      while(small < middle)
      {
            // we are lucky and find the sequence
            if(sum == n)
                  PrintContinuousSequence(small, big);

            // if the current sum is greater than n,
            // move small forward
            while(sum > n)
            {
                  sum -= small;
                  small ++;

                  // we are lucky and find the sequence
                  if(sum == n)
                        PrintContinuousSequence(small, big);
            }

            // move big forward
            big ++;
            sum += big;
      }
}

// Print continuous sequence between small and big
void PrintContinuousSequence(int small, int big)
{
      for(int i = small; i <= big; ++ i)
            printf("%d ", i);

      printf("/n");
}