在程序員的職業(yè)生涯中，算法亦算是一門基礎(chǔ)課程，尤其是在面試的時候，很多公司都會讓程序員編寫一些算法實例，例如快速排序、二叉樹查找等等。

本文總結(jié)了程序員在代碼面試中最常遇到的10大算法類型，想要真正了解這些算法的原理，還需程序員們花些功夫。

1.String/Array/Matrix

在Java中，String是一個包含char數(shù)組和其它字段、方法的類。如果沒有IDE自動完成代碼，下面這個方法大家應(yīng)該記?。?

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很容易理解，但與它們有關(guān)的問題常常需要高級的算法去解決，例如動態(tài)編程、遞歸等。

下面列出一些需要高級算法才能解決的經(jīng)典問題：

Evaluate Reverse Polish Notation Longest Palindromic Substring 單詞分割 字梯 Median of Two Sorted Arrays 正則表達(dá)式匹配 合并間隔 插入間隔 Two Sum 3Sum 4Sum 3Sum Closest String to Integer 合并排序數(shù)組Valid Parentheses實現(xiàn)strStr() Set Matrix Zeroes 搜索插入位置 Longest Consecutive Sequence Valid Palindrome 螺旋矩陣 搜索一個二維矩陣 旋轉(zhuǎn)圖像 三角形 Distinct Subsequences Total Maximum Subarray 刪除重復(fù)的排序數(shù)組 刪除重復(fù)的排序數(shù)組2 查找沒有重復(fù)的最長子串 包含兩個獨特字符的最長子串 Palindrome Partitioning

2.鏈表

在Java中實現(xiàn)鏈表是非常簡單的，每個節(jié)點都有一個值，然后把它鏈接到下一個節(jié)點。

class?Node?{
	int?val;
	Node?next;
?
	Node(int?x)?{
		val?=?x;
		next?=?null;
	}
}

比較流行的兩個鏈表例子就是棧和隊列。

棧（Stack）

class?Stack{
	Node?top;?
?
	public?Node?peek(){
		if(top?!=?null){
			return?top;
		}
?
		return?null;
	}
?
	public?Node?pop(){
		if(top?==?null){
			return?null;
		}else{
			Node?temp?=?new?Node(top.val);
			top?=?top.next;
			return?temp;	
		}
	}
?
	public?void?push(Node?n){
		if(n?!=?null){
			n.next?=?top;
			top?=?n;
		}
	}
}

隊列（Queue）

class?Queue{
	Node?first,?last;
?
	public?void?enqueue(Node?n){
		if(first?==?null){
			first?=?n;
			last?=?first;
		}else{
			last.next?=?n;
			last?=?n;
		}
	}
?
	public?Node?dequeue(){
		if(first?==?null){
			return?null;
		}else{
			Node?temp?=?new?Node(first.val);
			first?=?first.next;
			return?temp;
		}	
	}
}

值得一提的是，Java標(biāo)準(zhǔn)庫中已經(jīng)包含一個叫做Stack的類，鏈表也可以作為一個隊列使用（add()和remove()）。（鏈表實現(xiàn)隊列接口）如果你在面試過程中，需要用到?；蜿犃薪鉀Q問題時，你可以直接使用它們。

在實際中，需要用到鏈表的算法有：

插入兩個數(shù)字 重新排序列表 鏈表周期 Copy List with Random Pointer 合并兩個有序列表 合并多個排序列表 從排序列表中刪除重復(fù)的 分區(qū)列表 LRU緩存

3.樹&堆

這里的樹通常是指二叉樹。

class?TreeNode{
	int?value;
	TreeNode?left;
	TreeNode?right;
}

下面是一些與二叉樹有關(guān)的概念： 二叉樹搜索：對于所有節(jié)點，順序是：left children <= current node <= right children；平衡vs.非平衡：它是一 棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹；滿二叉樹：除最后一層無任何子節(jié)點外，每一層上的所有結(jié)點都有兩個子結(jié)點；完美二叉樹（Perfect Binary Tree）：一個滿二叉樹，所有葉子都在同一個深度或同一級，并且每個父節(jié)點都有兩個子節(jié)點；完全二叉樹：若設(shè)二叉樹的深度為h，除第 h 層外，其它各層 (1～h-1) 的結(jié)點數(shù)都達(dá)到最大個數(shù)，第 h 層所有的結(jié)點都連續(xù)集中在最左邊，這就是完全二叉樹。

堆（Heap）是一個基于樹的數(shù)據(jù)結(jié)構(gòu)，也可以稱為優(yōu)先隊列（ PriorityQueue），在隊列中，調(diào)度程序反復(fù)提取隊列中第一個作業(yè)并運行，因而實際情況中某些時間較短的任務(wù)將等待很長時間才能結(jié)束，或者某些不短小，但具有重要性的作業(yè)，同樣應(yīng)當(dāng)具有優(yōu)先權(quán)。堆即為解決此類問題設(shè)計的一種數(shù)據(jù)結(jié)構(gòu)。

下面列出一些基于二叉樹和堆的算法：

二叉樹前序遍歷二叉樹中序遍歷二叉樹后序遍歷字梯驗證二叉查找樹把二叉樹變平放到鏈表里二叉樹路徑和從前序和后序構(gòu)建二叉樹把有序數(shù)組轉(zhuǎn)換為二叉查找樹把有序列表轉(zhuǎn)為二叉查找樹最小深度二叉樹二叉樹最大路徑和平衡二叉樹

4.Graph

與Graph相關(guān)的問題主要集中在深度優(yōu)先搜索和寬度優(yōu)先搜索。深度優(yōu)先搜索非常簡單，你可以從根節(jié)點開始循環(huán)整個鄰居節(jié)點。下面是一個非常簡單的寬度優(yōu)先搜索例子，核心是用隊列去存儲節(jié)點。

第一步，定義一個GraphNode

class?GraphNode{?
	int?val;
	GraphNode?next;
	GraphNode[]?neighbors;
	boolean?visited;
?
	GraphNode(int?x)?{
		val?=?x;
	}
?
	GraphNode(int?x,?GraphNode[]?n){
		val?=?x;
		neighbors?=?n;
	}
?
	public?String?toString(){
		return?"value:?"+?this.val;?
	}
}

第二步，定義一個隊列

class?Queue{
	GraphNode?first,?last;
?
	public?void?enqueue(GraphNode?n){
		if(first?==?null){
			first?=?n;
			last?=?first;
		}else{
			last.next?=?n;
			last?=?n;
		}
	}
?
	public?GraphNode?dequeue(){
		if(first?==?null){
			return?null;
		}else{
			GraphNode?temp?=?new?GraphNode(first.val,?first.neighbors);
			first?=?first.next;
			return?temp;
		}	
	}
}

第三步，使用隊列進(jìn)行寬度優(yōu)先搜索

public?class?GraphTest?{
?
	public?static?void?main(String[]?args)?{
		GraphNode?n1?=?new?GraphNode(1);?
		GraphNode?n2?=?new?GraphNode(2);?
		GraphNode?n3?=?new?GraphNode(3);?
		GraphNode?n4?=?new?GraphNode(4);?
		GraphNode?n5?=?new?GraphNode(5);?
?
		n1.neighbors?=?new?GraphNode[]{n2,n3,n5};
		n2.neighbors?=?new?GraphNode[]{n1,n4};
		n3.neighbors?=?new?GraphNode[]{n1,n4,n5};
		n4.neighbors?=?new?GraphNode[]{n2,n3,n5};
		n5.neighbors?=?new?GraphNode[]{n1,n3,n4};
?
		breathFirstSearch(n1,?5);
	}
?
	public?static?void?breathFirstSearch(GraphNode?root,?int?x){
		if(root.val?==?x)
			System.out.println("find?in?root");
?
		Queue?queue?=?new?Queue();
		root.visited?=?true;
		queue.enqueue(root);
?
		while(queue.first?!=?null){
			GraphNode?c?=?(GraphNode)?queue.dequeue();
			for(GraphNode?n:?c.neighbors){
?
				if(!n.visited){
					System.out.print(n?+?"?");
					n.visited?=?true;
					if(n.val?==?x)
						System.out.println("Find?"+n);
					queue.enqueue(n);
				}
			}
		}
	}
}

輸出結(jié)果：

value: 2 value: 3 value: 5 Find value: 5
value: 4

實際中，基于Graph需要經(jīng)常用到的算法：

克隆Graph

5.排序

不同排序算法的時間復(fù)雜度，大家可以到wiki上查看它們的基本思想。

BinSort、Radix Sort和CountSort使用了不同的假設(shè)，所有，它們不是一般的排序方法。

下面是這些算法的具體實例，另外，你還可以閱讀： Java開發(fā)者在實際操作中是如何排序的。

歸并排序快速排序插入排序

6.遞歸和迭代

下面通過一個例子來說明什么是遞歸。

問題：

這里有n個臺階，每次能爬1或2節(jié)，請問有多少種爬法？

步驟1：查找n和n-1之間的關(guān)系

為了獲得n，這里有兩種方法：一個是從第一節(jié)臺階到n-1或者從2到n-2。如果f(n)種爬法剛好是爬到n節(jié)，那么f(n)=f(n-1)+f(n-2)。

步驟2：確保開始條件是正確的

f(0) = 0;
f(1) = 1;

public?static?int?f(int?n){
	if(n?<=?2)?return?n;
	int?x?=?f(n-1)?+?f(n-2);
	return?x;
}

遞歸方法的時間復(fù)雜度指數(shù)為n，這里會有很多冗余計算。

f(5)
f(4)?+?f(3)
f(3)?+?f(2)?+?f(2)?+?f(1)
f(2)?+?f(1)?+?f(2)?+?f(2)?+?f(1)

該遞歸可以很簡單地轉(zhuǎn)換為迭代。

public?static?int?f(int?n)?{
?
	if?(n?<=?2){
		return?n;
	}
?
	int?first?=?1,?second?=?2;
	int?third?=?0;
?
	for?(int?i?=?3;?i?<=?n;?i++)?{
		third?=?first?+?second;
		first?=?second;
		second?=?third;
	}
?
	return?third;
}

在這個例子中，迭代花費的時間要少些。關(guān)于迭代和遞歸，你可以去 這里看看。

7.動態(tài)規(guī)劃

動態(tài)規(guī)劃主要用來解決如下技術(shù)問題：

通過較小的子例來解決一個實例；對于一個較小的實例，可能需要許多個解決方案；把較小實例的解決方案存儲在一個表中，一旦遇上，就很容易解決；附加空間用來節(jié)省時間。

上面所列的爬臺階問題完全符合這四個屬性，因此，可以使用動態(tài)規(guī)劃來解決：

public?static?int[]?A?=?new?int[100];
?
public?static?int?f3(int?n)?{
	if?(n??0)
		return?A[n];
	else
		A[n]?=?f3(n-1)?+?f3(n-2);//store?results?so?only?calculate?once!
	return?A[n];
}

一些基于動態(tài)規(guī)劃的算法：

編輯距離最長回文子串單詞分割最大的子數(shù)組

8.位操作

位操作符：

從一個給定的數(shù)n中找位i（i從0開始，然后向右開始）

public?static?boolean?getBit(int?num,?int?i){
	int?result?=?num?&?(1<<i);
?
	if(result?==?0){
		return?false;
	}else{
		return?true;
	}
}

例如，獲取10的第二位：

i=1,?n=10
1<<1=?10
1010&10=10
10?is?not?0,?so?return?true;

典型的位算法： Find Single NumberMaximum Binary Gap

9.概率

通常要解決概率相關(guān)問題，都需要很好地格式化問題，下面提供一個簡單的例子：

有50個人在一個房間，那么有兩個人是同一天生日的可能性有多大？（忽略閏年，即一年有365天）

算法：

public?static?double?caculateProbability(int?n){
	double?x?=?1;?
?
	for(int?i=0;?i<n;?i++){
		x?*=??(365.0-i)/365.0;
	}
?
	double?pro?=?Math.round((1-x)?*?100);
	return?pro/100;
}

結(jié)果：

calculateProbability(50) = 0.97

10.組合和排列

組合和排列的主要差別在于順序是否重要。

例1：

1、2、3、4、5這5個數(shù)字，輸出不同的順序，其中4不可以排在第三位，3和5不能相鄰，請問有多少種組合？

例2：

有5個香蕉、4個梨、3個蘋果，假設(shè)每種水果都是一樣的，請問有多少種不同的組合？

基于它們的一些常見算法

排列排列2排列順序