在程序员的职业生涯中，算法亦算是一门基础课程，尤其是在面试的时候，很多公司都会让程序员编写一些算法实例，例如快速排序、二叉树查找等等。
本文总结了程序员在代码面试中最常遇到的10大算法类型，想要真正了解这些算法的原理，还需程序员们花些功夫。
1.String/Array/Matrix
在Java中，String是一个包含char数组和其它字段、方法的类。如果没有IDE自动完成代码，下面这个方法大家应该记住：
toCharArray() //get char array of a String
Arrays.sort() //sort an array
Arrays.toString(char[] a) //convert to string
charAt(int x) //get a char at the specific index
length() //string length
length //array size
substring(int beginIndex)
substring(int beginIndex, int endIndex)
Integer.valueOf()//string to integer
String.valueOf()/integer to string
String/arrays很容易理解，但与它们有关的问题常常需要高级的算法去解决，例如动态编程、递归等。
下面列出一些需要高级算法才能解决的经典问题：
EvaluateReversePolishNotationLongestPalindromicSubstring单词分割字梯MedianofTwoSortedArrays正则表达式匹配合并间隔插入间隔TwoSum3Sum4Sum3SumClosestStringtoInteger合并排序数组ValidParentheses实现strStr()SetMatrixZeroes搜索插入位置LongestConsecutiveSequenceValidPalindrome螺旋矩阵搜索一个二维矩阵旋转图像三角形DistinctSubsequencesTotalMaximumSubarray删除重复的排序数组删除重复的排序数组2查找没有重复的最长子串包含两个独特字符的最长子串PalindromePartitioning2.链表
在Java中实现链表是非常简单的，每个节点都有一个值，然后把它链接到下一个节点。
|
1
2
3
4
5
6
7
8
9
|
classNode{
intval;
Nodenext;
Node(intx){
val=x;
next=null;
}
}
|
比较流行的两个链表例子就是栈和队列。
栈（Stack）
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
classStack{
Nodetop;
publicNodepeek(){
if(top!=null){
returntop;
}
returnnull;
}
publicNodepop(){
if(top==null){
returnnull;
}else{
Nodetemp=newNode(top.val);
top=top.next;
returntemp;
}
}
publicvoidpush(Noden){
if(n!=null){
n.next=top;
top=n;
}
}
}
|
队列（Queue）
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
classQueue{
Nodefirst,last;
publicvoidenqueue(Noden){
if(first==null){
first=n;
last=first;
}else{
last.next=n;
last=n;
}
}
publicNodedequeue(){
if(first==null){
returnnull;
}else{
Nodetemp=newNode(first.val);
first=first.next;
returntemp;
}
}
}
|
值得一提的是，Java标准库中已经包含一个叫做Stack的类，链表也可以作为一个队列使用（add()和remove()）。（链表实现队列接口）如果你在面试过程中，需要用到栈或队列解决问题时，你可以直接使用它们。
在实际中，需要用到链表的算法有：
插入两个数字重新排序列表链表周期CopyListwithRandomPointer合并两个有序列表合并多个排序列表从排序列表中删除重复的分区列表LRU缓存3.树&堆
这里的树通常是指二叉树。
|
1
2
3
4
5
|
classTreeNode{
intvalue;
TreeNodeleft;
TreeNoderight;
}
|
下面是一些与二叉树有关的概念：
二叉树搜索：对于所有节点，顺序是：leftchildren<=currentnode<=rightchildren；
平衡vs.非平衡：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树；
满二叉树：除最后一层无任何子节点外，每一层上的所有结点都有两个子结点；
完美二叉树（PerfectBinaryTree）：一个满二叉树，所有叶子都在同一个深度或同一级，并且每个父节点都有两个子节点；
完全二叉树：若设二叉树的深度为h，除第h层外，其它各层(1～h-1)的结点数都达到最大个数，第h层所有的结点都连续集中在最左边，这就是完全二叉树。
堆（Heap）是一个基于树的数据结构，也可以称为优先队列（PriorityQueue），在队列中，调度程序反复提取队列中第一个作业并运行，因而实际情况中某些时间较短的任务将等待很长时间才能结束，或者某些不短小，但具有重要性的作业，同样应当具有优先权。堆即为解决此类问题设计的一种数据结构。
下面列出一些基于二叉树和堆的算法：
二叉树前序遍历二叉树中序遍历二叉树后序遍历字梯验证二叉查找树把二叉树变平放到链表里二叉树路径和从前序和后序构建二叉树把有序数组转换为二叉查找树把有序列表转为二叉查找树最小深度二叉树二叉树最大路径和平衡二叉树4.Graph
与Graph相关的问题主要集中在深度优先搜索和宽度优先搜索。深度优先搜索非常简单，你可以从根节点开始循环整个邻居节点。下面是一个非常简单的宽度优先搜索例子，核心是用队列去存储节点。
第一步，定义一个GraphNode
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
classGraphNode{
intval;
GraphNodenext;
GraphNode[]neighbors;
booleanvisited;
GraphNode(intx){
val=x;
}
GraphNode(intx,GraphNode[]n){
val=x;
neighbors=n;
}
publicStringtoString(){
return"value:"+this.val;
}
}
|
第二步，定义一个队列
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
classQueue{
GraphNodefirst,last;
publicvoidenqueue(GraphNoden){
if(first==null){
first=n;
last=first;
}else{
last.next=n;
last=n;
}
}
publicGraphNodedequeue(){
if(first==null){
returnnull;
}else{
GraphNodetemp=newGraphNode(first.val,first.neighbors);
first=first.next;
returntemp;
}
}
}
|
第三步，使用队列进行宽度优先搜索
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
publicclassGraphTest{
publicstaticvoidmain(String[]args){
GraphNoden1=newGraphNode(1);
GraphNoden2=newGraphNode(2);
GraphNoden3=newGraphNode(3);
GraphNoden4=newGraphNode(4);
GraphNoden5=newGraphNode(5);
n1.neighbors=newGraphNode[]{n2,n3,n5};
n2.neighbors=newGraphNode[]{n1,n4};
n3.neighbors=newGraphNode[]{n1,n4,n5};
n4.neighbors=newGraphNode[]{n2,n3,n5};
n5.neighbors=newGraphNode[]{n1,n3,n4};
breathFirstSearch(n1,5);
}
publicstaticvoidbreathFirstSearch(GraphNoderoot,intx){
if(root.val==x)
System.out.println("findinroot");
Queuequeue=newQueue();
root.visited=true;
queue.enqueue(root);
while(queue.first!=null){
GraphNodec=(GraphNode)queue.dequeue();
for(GraphNoden:c.neighbors){
if(!n.visited){
System.out.print(n+"");
n.visited=true;
if(n.val==x)
System.out.println("Find"+n);
queue.enqueue(n);
}
}
}
}
}
|
输出结果：
value:2value:3value:5Findvalue:5
value:4
实际中，基于Graph需要经常用到的算法：
克隆Graph
5.排序
不同排序算法的时间复杂度，大家可以到wiki上查看它们的基本思想。
BinSort、RadixSort和CountSort使用了不同的假设，所有，它们不是一般的排序方法。
下面是这些算法的具体实例，另外，你还可以阅读：Java开发者在实际操作中是如何排序的。
归并排序
快速排序
插入排序
6.递归和迭代
下面通过一个例子来说明什么是递归。
问题：
这里有n个台阶，每次能爬1或2节，请问有多少种爬法？
步骤1：查找n和n-1之间的关系
为了获得n，这里有两种方法：一个是从第一节台阶到n-1或者从2到n-2。如果f(n)种爬法刚好是爬到n节，那么f(n)=f(n-1)+f(n-2)。
步骤2：确保开始条件是正确的
f(0)=0;
f(1)=1;
|
1
2
3
4
5
|
publicstaticintf(intn){
if(n<=2)returnn;
intx=f(n-1)+f(n-2);
returnx;
}
|
递归方法的时间复杂度指数为n，这里会有很多冗余计算。
|
1
2
3
4
|
f(5)
f(4)+f(3)
f(3)+f(2)+f(2)+f(1)
f(2)+f(1)+f(2)+f(2)+f(1)
|
该递归可以很简单地转换为迭代。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
publicstaticintf(intn){
if(n<=2){
returnn;
}
intfirst=1,second=2;
intthird=0;
for(inti=3;i<=n;i++){
third=first+second;
first=second;
second=third;
}
returnthird;
}
|
在这个例子中，迭代花费的时间要少些。关于迭代和递归，你可以去这里看看。
7.动态规划
动态规划主要用来解决如下技术问题：
通过较小的子例来解决一个实例；
对于一个较小的实例，可能需要许多个解决方案；
把较小实例的解决方案存储在一个表中，一旦遇上，就很容易解决；
附加空间用来节省时间。
上面所列的爬台阶问题完全符合这四个属性，因此，可以使用动态规划来解决：
|
1
2
3
4
5
6
7
8
9
10
11
12
|
publicstaticint[]A=newint[100];
publicstaticintf3(intn){
if(n<=2)
A[n]=n;
if(A[n]>0)
returnA[n];
else
A[n]=f3(n-1)+f3(n-2);
returnA[n];
}
|
一些基于动态规划的算法：
编辑距离
最长回文子串
单词分割
最大的子数组
8.位操作
位操作符：
从一个给定的数n中找位i（i从0开始，然后向右开始）
|
1
2
3
4
5
6
7
8
9
|
publicstaticbooleangetBit(intnum,inti){
intresult=num&(1<<i);
if(result==0){
returnfalse;
}else{
returntrue;
}
}
|
例如，获取10的第二位：
|
1
2
3
4
|
i=1,n=10
1<<1=10
1010&10=10
10isnot0,soreturntrue;
|
典型的位算法：
FindSingleNumber
MaximumBinaryGap
9.概率
通常要解决概率相关问题，都需要很好地格式化问题，下面提供一个简单的例子：
有50个人在一个房间，那么有两个人是同一天生日的可能性有多大？（忽略闰年，即一年有365天）
算法：
|
1
2
3
4
5
6
7
8
9
10
|
publicstaticdoublecaculateProbability(intn){
doublex=1;
for(inti=0;i<n;i++){
x*=(365.0-i)/365.0;
}
doublepro=Math.round((1-x)*100);
returnpro/100;
}
|
结果：calculateProbability(50)=0.97
10.组合和排列
组合和排列的主要差别在于顺序是否重要。
例1：
1、2、3、4、5这5个数字，输出不同的顺序，其中4不可以排在第三位，3和5不能相邻，请问有多少种组合？
例2：
有5个香蕉、4个梨、3个苹果，假设每种水果都是一样的，请问有多少种不同的组合？
基于它们的一些常见算法
排列
排列2
排列顺序
来自：ProgramCreek
转自：http://bbs.csdn.net/topics/390768965
分享到：
相关推荐
代码面试最常用的10大算法的中文完整版（部分中文，部分英文）及英文原版。
摘要：面试也是一门学问，在面试之前做好充分的准备则是成功的必须条件，而程序员在代码面试时，常会...本文总结了程序员在代码面试中最常遇到的10大算法类型，想要真正了解这些算法的原理，还需程序员们花些功夫。
1. 1 - 100, 找出质数 2. 冒泡排序 3. 1~100共一百个自然数，放入一个只有99个元素的数组中，找出没有被放入数组的这个数； 4. 字符串的反转输出 5. 截取字符串, 如果该字符串是“abc我的”,当截取的字节数是3时候...
常见c#面试算法代码，保证正确无误，欢迎下载！！！！
常见算法面试题目有代码详解 链表，图，树，数据元素
常见算法面试宝典，原理+代码示例！
基础数据结构，算法，大公司笔试真题，牛客算法题，lintcode，九章算法，《剑指Offer》，左程云《程序员代码面试指南》
算法基础篇 **章 算法和实现算法的Java语法 1.1 建立算法初步概念 1.1.1 什么是算法 1.1.2 算法的发展历史 1.1.3 算法的分类 1.2 算法相关概念的区别 1.2.1 算法与公式的关系 1.2.2 算法与程序的...**4章 算法面试题
程序员名企面试的必备算法书籍，设计数据结构、排序、动态规划、大数据等常见算法。书籍是PDF版本，易于阅读~
《Java常用算法手册》分三篇，共13章，分别介绍了算法基础、算法应用和算法面试题。首先介绍了算法概述，然后重点分析了数据结构和基本算法思想；接着，详细讲解了算法在排序、查找、数学计算、数论、历史趣题、游戏...
IT常见的面试题目，各种排序算法的Java代码实现，内部有代码和详细的注释信息。
常见面试算法题的Scala语言实现，其中包括 链表，字符串，数组，已经面试建议和大数据的算法问题，希望可以帮助读者提高编写scala代码的能力，增加解决常见算法题的能力。
C++算法大全及面试题详解...这两份资料整理了C++的常见算法、常见考点和重要知识技巧，内容齐全，涵盖各类应试考点，满满干货（代码里程多）。这份精细资料旨在为大家面试面试C++程序员或算法工程师提供一些有用参考。
2_互联网面试常见100题精析
《剑指Offer》，《程序员代码面试指南》，Leetcode等算法题目集合。基于.net core的控制台程序，C#实现，包含每道题目的完整描述，多种解法AC代码，以及解题思路，所有题目均可直接运行以查看输出结果。常用算法汇总...
.NETY面试常见算法题，100%凭借亲身经历亲自编写，绝对可正确运行，更适合初级岗位面试者，有任何问题可留言讨论！
常见的数据结构有数组、链表、栈、队列、树、图等。 算法则是解决特定问题的步骤，是对数据运算和操作的详细描述。算法的设计和选择会直接影响到程序的效率，因此，在设计和选择算法时，需要考虑到时间复杂度、空间...
而数组是我们最常用的一种数据结构，支持根据下标快速访问。很多算法需要特定的数据结构来实现，所以经常把它们放到一块讲。 实际上，在真正的项目开发中，大部分时间都是 从数据库取数据 -> 数据操作和结构化 -> ...