編程面試的10大算法概念匯總

以下是在編程面試中排名前10的算法相關的概念，我會通過一些簡單的例子來闡述這些概念。由於完全掌握這些概念需要更多的努力，因此這份列表只是作為一個介紹。

本文將從Java的角度看問題，包含下面的這些概念：

1. 字符串
2. 鏈表
3. 樹
4. 圖
5. 排序
6. 遞歸 vs. 迭代
7. 動態規劃
8. 位操作
9. 概率問題
10. 排列組合

 

1. 字符串

如果IDE沒有代碼自動補全功能，所以你應該記住下面的這些方法。

toCharArray()// 獲得字符串對應的char數組
Arrays.sort() // 數組排序
Arrays.toString(char[] a)// 數組轉成字符串
charAt(intx)// 獲得某個索引處的字符
length()// 字符串長度
length// 數組大小

2. 鏈表

在Java中，鏈表的實現非常簡單，每個節點Node都有一個值val和指向下個節點的鏈接next。

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

鏈表兩個著名的應用是棧Stack和隊列Queue。

棧：

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;
  }
 }
}

隊列：

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;
  } 
 }
}

3. 樹

這裡的樹通常是指二叉樹，每個節點都包含一個左孩子節點和右孩子節點，像下面這樣：

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

下面是與樹相關的一些概念：

1. 平衡 vs. 非平衡：平衡二叉樹中，每個節點的左右子樹的深度相差至多為1（1或0）。
2. 滿二叉樹（Full Binary Tree）：除葉子節點以為的每個節點都有兩個孩子。
3. 完美二叉樹（Perfect Binary Tree）：是具有下列性質的滿二叉樹：所有的葉子節點都有相同的深度或處在同一層次，且每個父節點都必須有兩個孩子。
4. 完全二叉樹（Complete Binary Tree）：二叉樹中，可能除了最後一個，每一層都被完全填滿，且所有節點都必須盡可能想左靠。

譯者注：完美二叉樹也隱約稱為完全二叉樹。完美二叉樹的一個例子是一個人在給定深度的祖先圖，因為每個人都一定有兩個生父母。完全二叉樹可以看成是可以有若干額外向左靠的葉子節點的完美二叉樹。疑問：完美二叉樹和滿二叉樹的區別？（參考：http://xlinux.nist.gov/dads/HTML/perfectBinaryTree.html）

 

4. 圖

圖相關的問題主要集中在深度優先搜索（depth first search）和廣度優先搜索（breath first search）。

下面是一個簡單的圖廣度優先搜索的實現。

1) 定義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;
 }
}

2) 定義一個隊列Queue

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;
  } 
 }
}

3) 用隊列Queue實現廣度優先搜索

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);
    }
   }
  }
 }
}

輸出：

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

5. 排序

下面是不同排序算法的時間復雜度，你可以去wiki看一下這些算法的基本思想。

Algorithm Average Time Worst Time Space 冒泡排序 n^2 n^2 1 選擇排序 n^2 n^2 1 Counting Sort n+k n+k n+k Insertion sort n^2 n^2   Quick sort n log(n) n^2   Merge sort n log(n) n log(n) depends

另外，這裡有一些實現/演示：: Counting sort、Mergesort、 Quicksort、 InsertionSort。