面试10大算法汇总＋常见题目解答(转)
以下用Java角度解释面试常见的算法和数据结构：字符串，链表，树，图，排序，递归 vs. 迭代，动态规划，位操作，概率问题，排列组合，以及一些需要寻找规律的题目。
1. 字符串和数组
首先需要注意的是和C++不同，Java字符串不是char数组。没有IDE代码自动补全功能，应该记住下面的这些常用的方法。
经典题目：复制图(Clone Graph)
5. 排序
下面是不同排序算法的时间复杂度，你可以去wiki看一下这些算法的基本思想。
AlgorithmAverage TimeWorst TimeSpace冒泡排序(Bubble sort)n^2n^21选择排序(Selection sort)n^2n^21插入排序(Insertion sort)n^2n^2?快速排序(Quick sort)n log(n)n^2?归并排序(Merge sort)n log(n)n log(n)depends* 另外还有BinSort, RadixSort和CountSort 三种比较特殊的排序。
经典题目：?Mergesort,?Quicksort,?InsertionSort.
6. 递归 vs. 迭代
对程序员来说，递归应该是一个与生俱来的思想（a built-in thought），可以通过一个简单的例子来说明。
问题：
有n步台阶，一次只能上1步或2步，共有多少种走法。
步骤1:找到走完前n步台阶和前n-1步台阶之间的关系。
为了走完n步台阶，只有两种方法：从n-1步台阶爬1步走到或从n-2步台阶处爬2步走到。如果f(n)是爬到第n步台阶的方法数，那么f(n) = f(n-1) + f(n-2)。
步骤2: 确保开始条件是正确的。
f(0) = 0;
f(1) = 1;f(5)
f(4) + f(3)
f(3) + f(2) + f(2) + f(1)
f(2) + f(1) + f(1) + f(0) + f(1) + f(0) + f(1)
f(1) + f(0) + f(1) + f(1) + f(0) + f(1) + f(0) + f(1)直接的想法是将递归转换为迭代：
OR (|)AND (&)XOR (^)Left Shift (<<)Right Shift (>>)Not (~)1|0=11&0=01^0=10010<<2=10001100>>2=0011~1=0用一个题目来理解这些操作 －
获得给定数字n的第i位：(i从0计数并从右边开始)
i=1, n=10
1<<1= 10
1010&10=10
10 is not 0, so return true;9. 概率问题
解决概率相关的问题通常需要先分析问题，下面是一个这类问题的简单例子：
一个房间里有50个人，那么至少有两个人生日相同的概率是多少？（忽略闰年的事实，也就是一年365天）
计算某些事情的概率很多时候都可以转换成先计算其相对面。在这个例子里，我们可以计算所有人生日都互不相同的概率，也就是：365/365 * 364/365 * 363/365 * … * (365-49)/365，这样至少两个人生日相同的概率就是1 – 这个值。
calculateProbability(50) = 0.9710. 排列组合
组合和排列的区别在于次序是否关键。
11. 其他类型的题目
主要是不能归到上面10大类的。需要寻找规律，然后解决问题的。
经典题目:?Reverse Integer
