在程序员的职业生涯中，算法亦算是一门基础课程，尤其是在面试的时候，很多公司都会让程序员编写一些算法实例，例如快速排序、二叉树查找等等。
本文总结了程序员在代码面试中最常遇到的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大算法"，旨在帮助求职者提升在面试中的表现。以下是这些算法的详细解析： 1. **排序算法**： - **快速排序**：通过分治策略实现，选择一个基准元素，将数组分为小于和大于基准...
摘要：面试也是一门学问，在面试之前做好充分的准备则是成功的必须条件，而程序员在代码面试时，常会...本文总结了程序员在代码面试中最常遇到的10大算法类型，想要真正了解这些算法的原理，还需程序员们花些功夫。
总之，《程序员代码面试指南》是一本全面且深入的资源，它不仅提供了大量的代码示例，还涵盖了理论知识和实践经验，对于希望提升自己算法能力、准备IT名企面试的程序员来说，是一本不可多得的宝典。
1. 1 - 100, 找出质数 2. 冒泡排序 3. 1~100共一百个自然数，放入一个只有99个元素的数组中，找出没有被放入数组的这个数； 4. 字符串的反转输出 5. 截取字符串, 如果该字符串是“abc我的”,当截取的字节数是3时候...
10. **堆**：最大堆和最小堆可用于优先队列，也可以用来求解Top-K问题。理解堆的性质和操作，如插入、删除和调整，是解决这些问题的关键。 面试中的算法题通常要求在有限的时间内编写出正确且高效的代码，因此熟练...
本资源"常见算法面试题目有代码详解"显然是一份针对算法面试的珍贵资料，涵盖了链表、图、树以及数据元素等核心概念。下面将详细阐述这些领域的关键知识点。 首先，链表是一种线性数据结构，它的元素（节点）不连续...
8. **常用算法**：除了上述数据结构，面试还会涉及排序、查找、图论、动态规划、贪心算法等经典算法。例如，快速排序、归并排序、二分查找、KMP字符串匹配、最小生成树（Prim或Kruskal）、最短路径（Dijkstra或...
常见算法介绍、算法刷题（含解析与代码）、笔试面试算法题
常见c#面试算法代码，保证正确无误，欢迎下载！！！！
本"Scala程序员面试算法宝典代码"集合了多种常见算法的实现，旨在帮助求职者提升面试成功率。 1. **基础数据结构** - 数组：数组是最基本的数据结构，用于存储固定大小的同类型元素集合。在Scala中，可以使用Array...
在面试过程中，面试官通过算法问题来评估求职者的逻辑思维、问题解决技巧和代码实现能力。因此，对于求职者来说，熟悉和掌握经典算法，不仅能提高面试通过率，也有助于在工作中解决复杂问题。在准备阶段，除了阅读...
10. **问题分析和解决方案**：面试不仅仅是测试你是否知道某种算法，更重要的是看你怎么分析问题，选择合适的算法，以及如何调试和优化代码。 掌握以上这些知识点，并通过实际练习和分析题目来提升自己的算法能力，...
这个名为"java常用算法大全源代码.zip"的压缩包文件显然包含了丰富的Java算法实现，对于学习和提高编程技能非常有帮助。随书光盘的形式表明这可能是某本关于Java算法书籍的配套资源，而“全套”和“注释详细”的描述...
4. **动态规划**：背包问题、最长公共子序列、矩阵链乘法等，动态规划是解决具有重叠子问题和最优子结构问题的有效方法，理解和编写动态规划代码是面试中的高分项。 5. **贪心算法**：贪心算法在解决部分最优问题上...
本资料包“算法数据结构常见面试题”是为准备面试的程序员精心准备的，涵盖了这一领域的核心知识点，旨在帮助你提升面试成功率。 数据结构是计算机科学中用于组织和存储数据的一种方式，它关系到数据的逻辑结构、...
根据给定的信息，本文将对Java面试中常见的算法题进行详细的解析与总结，特别是针对冒泡排序和选择排序这两种基础但重要的排序算法。 ### 冒泡排序 #### 算法原理 冒泡排序是一种简单的排序算法。它重复地遍历要...
为了帮助求职者们更有效地准备面试中的算法部分，《2024年互联网面试算法常见100题精析.pdf》这本图解笔记应运而生。它汇集了105道高频面试题，并以图解的方式进行解析，使之更加生动和易于理解，尤其适合算法初学者...
这里我们将深入探讨几种常见的排序算法，如冒泡排序、选择排序和插入排序，并分析一个递归求斐波那契数列的问题，以及模拟事件处理的简单设计模式。 首先，让我们来看冒泡排序。冒泡排序是一种简单的排序算法，它...
《程序员面试算法大全》这份资料集是专门为准备面试的程序员们精心整理的资源，涵盖了大量常见面试题目的实例和解析，旨在帮助求职者提升在面试中的表现。由于标签为"test"，我们可以推断这份资料主要关注的是测试...