代碼面試最常用的10大算法

來(lái)源：網(wǎng)絡(luò)    更新時(shí)間：2014-4-19

摘要：面試也是一門(mén)學(xué)問(wèn)，在面試之前做好充分的準(zhǔn)備則是成功的必須條件，而程序員在代碼面試時(shí)，常會(huì)遇到編寫(xiě)算法的相關(guān)問(wèn)題，比如排序、二叉樹(shù)遍歷等等。
在程序員的職業(yè)生涯中，算法亦算是一門(mén)基礎(chǔ)課程，尤其是在面試的時(shí)候，很多公司都會(huì)讓程序員編寫(xiě)一些算法實(shí)例，例如快速排序、二叉樹(shù)查找等等。

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

1.String/Array/Matrix

在Java中，String是一個(gè)包含char數(shù)組和其它字段、方法的類(lèi)。如果沒(méi)有IDE自動(dòng)完成代碼，下面這個(gè)方法大家應(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 stringString/arrays很容易理解，但與它們有關(guān)的問(wèn)題常常需要高級(jí)的算法去解決，例如動(dòng)態(tài)編程、遞歸等。
下面列出一些需要高級(jí)算法才能解決的經(jīng)典問(wèn)題：

•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
•實(shí)現(xiàn)strStr()
•Set Matrix Zeroes
•搜索插入位置
•Longest Consecutive Sequence
•Valid Palindrome
•螺旋矩陣
•搜索一個(gè)二維矩陣
•旋轉(zhuǎn)圖像
•三角形
•Distinct Subsequences Total
•Maximum Subarray
•刪除重復(fù)的排序數(shù)組
•刪除重復(fù)的排序數(shù)組2
•查找沒(méi)有重復(fù)的最長(zhǎng)子串
•包含兩個(gè)獨(dú)特字符的最長(zhǎng)子串
•Palindrome Partitioning

2.鏈表

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

 

class Node {
 int val;
 Node next;
 
 Node(int x) {
  val = x;
  next = null;
 }
}比較流行的兩個(gè)鏈表例子就是棧和隊(duì)列。

棧（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;
  }
 }
}隊(duì)列（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)庫(kù)中已經(jīng)包含一個(gè)叫做Stack的類(lèi)，鏈表也可以作為一個(gè)隊(duì)列使用（add()和remove()）。（鏈表實(shí)現(xiàn)隊(duì)列接口）如果你在面試過(guò)程中，需要用到�；蜿�(duì)列解決問(wèn)題時(shí)，你可以直接使用它們。

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

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

3.樹(shù)&堆

這里的樹(shù)通常是指二叉樹(shù)。

class TreeNode{
 int value;
 TreeNode left;
 TreeNode right;
}
下面是一些與二叉樹(shù)有關(guān)的概念：

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

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

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

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

4.Graph

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

 第一步，定義一個(gè)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;
 }
}

第二步，定義一個(gè)隊(duì)列

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;
  } 
 }
}第三步，使用隊(duì)列進(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
實(shí)際中，基于Graph需要經(jīng)常用到的算法：

•克隆Graph

5.排序

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

 

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

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

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

6.遞歸和迭代

下面通過(guò)一個(gè)例子來(lái)說(shuō)明什么是遞歸。

問(wèn)題：

這里有n個(gè)臺(tái)階，每次能爬1或2節(jié)，請(qǐng)問(wèn)有多少種爬法？
步驟1：查找n和n-1之間的關(guān)系

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

步驟2：確保開(kāi)始條件是正確的

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;
}遞歸方法的時(shí)間復(fù)雜度指數(shù)為n，這里會(huì)有很多冗余計(jì)算。

 

f(5)
f(4) + f(3)
f(3) + f(2) + f(2) + f(1)
f(2) + f(1) + f(2) + f(2) + f(1)該遞歸可以很簡(jiǎn)單地轉(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;
}
在這個(gè)例子中，迭代花費(fèi)的時(shí)間要少些。關(guān)于迭代和遞歸，你可以去 這里看看。

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

動(dòng)態(tài)規(guī)劃主要用來(lái)解決如下技術(shù)問(wèn)題：

•通過(guò)較小的子例來(lái)解決一個(gè)實(shí)例；
•對(duì)于一個(gè)較小的實(shí)例，可能需要許多個(gè)解決方案；
•把較小實(shí)例的解決方案存儲(chǔ)在一個(gè)表中，一旦遇上，就很容易解決；
•附加空間用來(lái)節(jié)省時(shí)間。

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

 

public static int[] A = new int[100];
 
public static int f3(int n) {
 if (n <= 2)
  A[n]= n;
 
 if(A[n] > 0)
  return A[n];
 else
  A[n] = f3(n-1) + f3(n-2);//store results so only calculate once!
 return A[n];
}
一些基于動(dòng)態(tài)規(guī)劃的算法：

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

8.位操作

位操作符：

 

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

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 Number
•Maximum Binary Gap

9.概率

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

有50個(gè)人在一個(gè)房間，那么有兩個(gè)人是同一天生日的可能性有多大？（忽略閏年，即一年有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個(gè)數(shù)字，輸出不同的順序，其中4不可以排在第三位，3和5不能相鄰，請(qǐng)問(wèn)有多少種組合？
例2：

有5個(gè)香蕉、4個(gè)梨、3個(gè)蘋(píng)果，假設(shè)每種水果都是一樣的，請(qǐng)問(wèn)有多少種不同的組合？
基于它們的一些常見(jiàn)算法

•排列
•排列2
•排列順序

來(lái)自：ProgramCreek

 

上一篇文章： 閱讀優(yōu)秀代碼是提高開(kāi)發(fā)人員修為的一種捷徑

下一篇文章： java常見(jiàn)面試知識(shí)點(diǎn)匯總1