这个项目里面的代码都是对一些IT公司经典面试笔试的解答
-------------------------------------------------------------------------------
部分题目来源是：v_july_v
http://blog.csdn.net/v_july_v/article/details/6870251
http://topic.csdn.net/u/20101126/10/b4f12a00-6280-492f-b785-cb6835a63dc9.html
-------------------------------------------------------------------------------
第1-5题：
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
};


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


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

例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2，
因此输出为该子数组的和18。



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

二元树节点的数据结构定义为：

struct BinaryTreeNode // a node in the binary tree
{
int m_nValue; // value of node
BinaryTreeNode *m_pLeft; // left child of node
BinaryTreeNode *m_pRight; // right child of node
};


5.查找最小的k个元素
题目：输入n个整数，输出其中最小的k个。
例如输入1，2，3，4，5，6，7和8这8个数字，则最小的4个数字为1，2，3和4。

第6-10题
------------------------------------
第6题，腾讯面试题：   
给你10分钟时间，根据上排给出十个数，在其下排填出对应的十个数   
要求下排每个数都是先前上排那十个数在下排出现的次数。   
上排的十个数如下：   
【0，1，2，3，4，5，6，7，8，9】

初看此题，貌似很难，10分钟过去了，可能有的人，题目都还没看懂。   
举一个例子，   
数值: 0,1,2,3,4,5,6,7,8,9   
分配: 6,2,1,0,0,0,1,0,0,0   
0在下排出现了6次，1在下排出现了2次，   
2在下排出现了1次，3在下排出现了0次....   
以此类推..   
    

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


第8题
微软面试题，此题篇幅较为庞大。为了尽量让整个版面看起来，简介，略。
可参考我博客，或者资源下载。

第9题
判断整数序列是不是二元查找树的后序遍历结果
题目：输入一个整数数组，判断该数组是不是某二元查找树的后序遍历的结果。
如果是返回true，否则返回false。
例如输入5、7、6、9、11、10、8，由于这一整数序列是如下树的后序遍历结果：
  8
  / \
  6 10
  / \ / \
  5 7 9 11
因此返回true。
如果输入7、4、6、5，没有哪棵树的后序遍历的结果是这个序列，因此返回false。


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

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


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


第13题：
题目：输入一个单向链表，输出该链表中倒数第k个结点。链表的倒数第0个结点为链表的尾指针。
链表结点定义如下：   
struct ListNode
{
  int m_nKey;
  ListNode* m_pNext;
};
思路：利用两个指针 p1,p2;
p1=p2=head
for(int i=0;i<=k-1;++i)
   p1=p1->m_pNext;
while(p1)
{
	p1 = p1->m_pNext;
	p2 = p2->m_pNext;
}



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

思路见代码：sum_eq.h
扩展：如果数据是没有排序的，依然要求在O(n)的时间找出两个数，如何解？
思路：还没有想到- -

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

第16题：
题目（微软）：
输入一颗二元树，从上往下按层打印树的每个结点，同一层中按照从左往右的顺序打印。   
例如输入
  8
  / \
 6 10
/ \ / \
5 7 9 11
输出8 6 10 5 7 9 11。
思路：也就是常说的层序遍历


第17题：
题目：在一个字符串中找到第一个只出现一次的字符。如输入abaccdeff，则输出b。   
分析：这道题是2006年google的一道笔试题。
思路：
1、最笨的方法：O(n^2)，略（当然空间是最省的）
2、统计每个字符的次数，用一个map即可，但是这里只有字符，ASCII值在0——255，因此只用一个普通的数组
  就可以搞定。用字符的ascii值做下标
伪代码：
  input:str
  int c2i[256]={0};
  for c in str:
      c2i[c]++;
  for c in str:
      if(c2i[c] ==1) return c;


第18题：
题目：n个数字（0,1,…,n-1）形成一个圆圈，从数字0开始，
每次从这个圆圈中删除第m个数字（第一个为当前数字本身，第二个为当前数字的下一个数字）。
当一个数字删除后，从被删除数字的下一个继续删除第m个数字。
求出在这个圆圈中剩下的最后一个数字。
July：我想，这个题目，不少人已经 见识过了。

 

第19题：
题目：定义Fibonacci数列如下：   
  / 0 n=0
f(n)= 1 n=1
  \ f(n-1)+f(n-2) n=2
输入n，用最快的方法求该数列的第n项。
分析：在很多C语言教科书中讲到递归函数的时候，都会用Fibonacci作为例子。
因此很多程序员对这道题的递归解法非常熟悉，但....呵呵，你知道的。。
思路：
为了避免无畏的重复计算，采用迭代的计算更好
如果这个方法需要在一段代码内频繁使用，可以考虑如下方式，用数组保存已经计算的结果：
vector<int> fab(10);
static max_calculated = 1;
fab[0] = 0;
fab[1] = 1;
int f(int n)
{
	if(n<=max_calculated)
		return fab[n];
	else
	{
		for(int i=max_calculated+1;i<=n;++i)
			fab.push_back(fab[n-2]+fab[n-1]);
		max_calculated = n;
		return fab[n];
	}
}
据说这个有log(n)的解法，暂时我还没想出来
谁想出来了告知我一声呗邮箱：[email protected]

第20题：
题目：输入一个表示整数的字符串，把该字符串转换成整数并输出。
例如输入字符串"345"，则输出整数345
很常规的，但是很实用的一个功能。当然库函数都有实现。自己模拟实现库函数吧
注意几点：
1、输入的合法性判断
2、正负号的判断 “-1234”
3、溢出判断 if result > numeric_limits<int>::max() then overflow

第21-25题：
------------------
第21题
2010年中兴面试题
编程求解：
输入两个整数 n 和 m，从数列1，2，3.......n 中 随意取几个数,
使其和等于 m ,要求将其中所有的可能组合列出来.


第22题：
有4张红色的牌和4张蓝色的牌，主持人先拿任意两张，再分别在A、B、C三人额头上贴任意两张牌，
A、B、C三人都可以看见其余两人额头上的牌，看完后让他们猜自己额头上是什么颜色的牌，
A说不知道，B说不知道，C说不知道，然后A说知道了。
请教如何推理，A是怎么知道的。
如果用程序，又怎么实现呢？


第23题：
用最简单， 最快速的方法计算出下面这个圆形是否和正方形相交。"   
3D坐标系 原点(0.0,0.0,0.0)
圆形:
半径r = 3.0
圆心o = (*.*, 0.0, *.*)
正方形:
4个角坐标;   
1:(*.*, 0.0, *.*)
2:(*.*, 0.0, *.*)
3:(*.*, 0.0, *.*)
4:(*.*, 0.0, *.*)


第24题：
链表操作，
（1）.单链表就地逆置，
（2）合并链表


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

26.左旋转字符串
题目:
定义字符串的左旋转操作:把字符串前面的若干个字符移动到字符串的尾部。
如把字符串 abcdef 左旋转 2 位得到字符串 cdefab。请实现字符串左旋转的函数。
要求时间对长度为 n 的字符串操作的复杂度为 O(n),辅助内存为 O(1)。
27.跳台阶问题
题目:一个台阶总共有 n 级,如果一次可以跳 1 级,也可以跳 2 级。
求总共有多少总跳法,并分析算法的时间复杂度。
这道题最近经常出现,包括 MicroStrategy 等比较重视算法的公司
都曾先后选用过个这道题作为面试题或者笔试题。

28.整数的二进制表示中 1 的个数
题目:输入一个整数,求该整数的二进制表达中有多少个 1。
例如输入 10,由于其二进制表示为 1010,有两个 1,因此输出 2。
分析:
这是一道很基本的考查位运算的面试题。
包括微软在内的很多公司都曾采用过这道题。
29.栈的 push、pop 序列
题目:输入两个整数序列。其中一个序列表示栈的 push 顺序,
判断另一个序列有没有可能是对应的 pop 顺序。
为了简单起见,我们假设 push 序列的任意两个整数都是不相等的。
比如输入的 push 序列是 1、2、3、4、5,那么 4、5、3、2、1 就有可能是一个 pop 系列。
因为可以有如下的 push 和 pop 序列:
push 1,push 2,push 3,push 4,pop,push 5,pop,pop,pop,pop,
这样得到的 pop 序列就是 4、5、3、2、1。
但序列 4、3、5、1、2 就不可能是 push 序列 1、2、3、4、5 的 pop 序列。


30.在从 1 到 n 的正数中 1 出现的次数
题目:输入一个整数 n,求从 1 到 n 这 n 个整数的十进制表示中 1 出现的次数。
例如输入 12,从 1 到 12 这些整数中包含 1 的数字有 1,10,11 和 12,1 一共出现了 5 次。
分析:这是一道广为流传的 google 面试题。
31.华为面试题:
一类似于蜂窝的结构的图,进行搜索最短路径(要求 5 分钟)
32.
有两个序列 a,b,大小都为 n,序列元素的值任意整数,无序;
要求:通过交换 a,b 中的元素,使[序列 a 元素的和]与[序列 b 元素的和]之间的差最小。
例如:
var a=[100,99,98,1,2, 3];
var b=[1, 2, 3, 4,5,40];

33.
实现一个挺高级的字符匹配算法:
给一串很长字符串,要求找到符合要求的字符串,例如目的串:123
1******3***2 ,12*****3 这些都要找出来
其实就是类似一些和谐系统。。。

34.
实现一个队列。
队列的应用场景为:
一个生产者线程将 int 类型的数入列,一个消费者线程将 int 类型的数出列
35.
求一个矩阵中最大的二维矩阵(元素和最大).如:
1 2 0 3 4
2 3 4 5 1
1 1 5 3 0
中最大的是:
4 5
5 3
要求:(1)写出算法;(2)分析时间复杂度;(3)用 C 写出关键代码
第 36 题-40 题(有些题目搜集于 CSDN 上的网友,已标明)
:
36.引用自网友:longzuo
谷歌笔试:
n 支队伍比赛,分别编号为 0,1,2。。
。。n-1,已知它们之间的实力对比关系,
存储在一个二维数组 w[n][n]中,w[i][j] 的值代表编号为 i,j 的队伍中更强的一支。
所以 w[i][j]=i 或者 j,现在给出它们的出场顺序,并存储在数组 order[n]中,
比如 order[n] = {4,3,5,8,1......},那么第一轮比赛就是 4 对 3, 5 对 8。.......
胜者晋级,败者淘汰,同一轮淘汰的所有队伍排名不再细分,即可以随便排,
下一轮由上一轮的胜者按照顺序,再依次两两比,比如可能是 4 对 5,直至出现第一名
编程实现,给出二维数组 w,一维数组 order 和 用于输出比赛名次的数组 result[n],
求出 result。

37.
有 n 个长为 m+1 的字符串,
如果某个字符串的最后 m 个字符与某个字符串的前 m 个字符匹配,则两个字符串可以联接,
问这 n 个字符串最多可以连成一个多长的字符串,如果出现循环,则返回错误。


38.
百度面试:
1.用天平(只能比较,不能称重)从一堆小球中找出其中唯一一个较轻的,使用 x 次天平,
最多可以从 y 个小球中找出较轻的那个,求 y 与 x 的关系式。
2.有一个很大很大的输入流,大到没有存储器可以将其存储下来,
而且只输入一次,如何从这个输入流中随机取得 m 个记录。
3.大量的 URL 字符串,如何从中去除重复的,优化时间空间复杂度

39.
网易有道笔试:
(1).
求一个二叉树中任意两个节点间的最大距离,
两个节点的距离的定义是 这两个节点间边的个数,
比如某个孩子节点和父节点间的距离是 1,和相邻兄弟节点间的距离是 2,优化时间空间复
杂度。
(2).
求一个有向连通图的割点,割点的定义是,如果除去此节点和与其相关的边,
有向图不再连通,描述算法。

40.百度研发笔试题
引用自:zp155334877
1)设计一个栈结构,满足一下条件:min,push,pop 操作的时间复杂度为 O(1)。
2)一串首尾相连的珠子(m 个),有 N 种颜色(N<=10),
设计一个算法,取出其中一段,要求包含所有 N 中颜色,并使长度最短。
并分析时间复杂度与空间复杂度。
3)设计一个系统处理词语搭配问题,比如说 中国 和人民可以搭配,
则中国人民 人民中国都有效。要求:
*系统每秒的查询数量可能上千次;
*词语的数量级为 10W;
*每个词至多可以与 1W 个词搭配
当用户输入中国人民的时候,要求返回与这个搭配词组相关的信息。

41.求固晶机的晶元查找程序
晶元盘由数目不详的大小一样的晶元组成,晶元并不一定全布满晶元盘,
照相机每次这能匹配一个晶元,如匹配过,则拾取该晶元,
若匹配不过,照相机则按测好的晶元间距移到下一个位置。
求遍历晶元盘的算法 求思路。
42.请修改 append 函数,利用这个函数实现:
两个非降序链表的并集,1->2->3 和 2->3->5 并为 1->2->3->5
另外只能输出结果,不能修改两个链表的数据。
43.递归和非递归俩种方法实现二叉树的前序遍历。
44.腾讯面试题:
1.设计一个魔方(六面)的程序。
2.有一千万条短信,有重复,以文本文件的形式保存,一行一条,有重复。
请用 5 分钟时间,找出重复出现最多的前 10 条。
3.收藏了 1 万条 url,现在给你一条 url,如何找出相似的 url。
(面试官不解释何为相似)


45.雅虎:
1.对于一个整数矩阵,存在一种运算,对矩阵中任意元素加一时,需要其相邻(上下左右)
某一个元素也加一,
现给出一正数矩阵,
判断其是否能够由一个全零矩阵经过上述运算得到。
2.一个整数数组,长度为 n,将其分为 m 份,使各份的和相等,求 m 的最大值
比如{3,2,4,3,6} 可以分成{3,2,4,3,6} m=1;
{3,6}{2,4,3} m=2
{3,3}{2,4}{6} m=3 所以 m 的最大值为 3

46.搜狐:
四对括号可以有多少种匹配排列方式?比如两对括号可以有两种: ()和( )

47.创新工场:
求一个数组的最长递减子序列 比如{9,4,3,2,5,4,3,2}的最长递减子序列为{9,5,
4,3,2}

48.微软:
一个数组是由一个递减数列左移若干位形成的,比如{4,3,2,1,6,5}
是由{6,5,4,3,2,1}左移两位形成的,在这种数组中查找某一个数。
49.一道看上去很吓人的算法面试题:
如何对 n 个数进行排序,要求时间复杂度 O(n),空间复杂度 O(1)
50.网易有道笔试:
1.求一个二叉树中任意两个节点间的最大距离,两个节点的距离的定义是 这两个节点间边
的个数,
比如某个孩子节点和父节点间的距离是 1,和相邻兄弟节点间的距离是 2,优化时间空间复
杂度。
2.求一个有向连通图的割点,割点的定义是,
如果除去此节点和与其相关的边,有向图不再连通,描述算法。
-------------------------------------------------------------------