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

作者：敏敏譯 2013-11-28 09:55:22

開發(fā) 項目管理算法

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

以下是在編程面試中排名前10的算法相關(guān)的概念，我會通過一些簡單的例子來闡述這些概念。由于完全掌握這些概念需要更多的努力，因此這份列表只是作為一個介紹。本文將從Java的角度看問題，包含下面的這些概念：

1. 字符串

2. 鏈表

3. 樹

4. 圖

5. 排序

6. 遞歸 vs. 迭代

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

8. 位操作

9. 概率問題

10. 排列組合

1. 字符串

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

toCharyArray() // 獲得字符串對應(yīng)的char數(shù)組 
Arrays.sort()  // 數(shù)組排序 
Arrays.toString(char[] a) // 數(shù)組轉(zhuǎn)成字符串 
charAt(int x) // 獲得某個索引處的字符 
length() // 字符串長度 
length // 數(shù)組大小

2. 鏈表

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

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

鏈表兩個著名的應(yīng)用是棧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. 樹

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

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

下面是與樹相關(guān)的一些概念：

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

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

#p#

4. 圖

圖相關(guān)的問題主要集中在深度優(yōu)先搜索（depth first search）和廣度優(yōu)先搜索（breath first search）。

下面是一個簡單的圖廣度優(yōu)先搜索的實現(xiàn)。

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實現(xià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); 
                } 
            } 
        } 
    } 
}

Output:

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

5. 排序

下面是不同排序算法的時間復(fù)雜度，你可以去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

另外，這里有一些實現(xiàn)/演示：: Counting sort、Mergesort、 Quicksort、 InsertionSort。

《視覺直觀感受 7 種常用的排序算法》
《視頻: 6分鐘演示15種排序算法》

#p#

6. 遞歸 vs. 迭代

對程序員來說，遞歸應(yīng)該是一個與生俱來的思想（a built-in thought），可以通過一個簡單的例子來說明。

問題：有n步臺階，一次只能上1步或2步，共有多少種走法。

步驟1:找到走完前n步臺階和前n-1步臺階之間的關(guān)系。

為了走完n步臺階，只有兩種方法：從n-1步臺階爬1步走到或從n-2步臺階處爬2步走到。如果f(n)是爬到第n步臺階的方法數(shù)，那么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ù)雜度是n的指數(shù)級，因為有很多冗余的計算，如下：

f(5)
f(4) + f(3)
f(3) + f(2) + f(2) + f(1)
f(2) + f(1) + f(1) + f(0) + f(1) + f(0) + f(1)
f(1) + f(0) + f(1) + f(1) + f(0) + f(1) + f(0) + 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; 
}

對這個例子而言，迭代花費的時間更少，你可能也想看看Recursion vs Iteration。

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

動態(tài)規(guī)劃是解決下面這些性質(zhì)類問題的技術(shù)：

一個問題可以通過更小子問題的解決方法來解決（譯者注：即問題的最優(yōu)解包含了其子問題的最優(yōu)解，也就是最優(yōu)子結(jié)構(gòu)性質(zhì)）。

有些子問題的解可能需要計算多次（譯者注：也就是子問題重疊性質(zhì)）。

子問題的解存儲在一張表格里，這樣每個子問題只用計算一次。

需要額外的空間以節(jié)省時間。

爬臺階問題完全符合上面的四條性質(zhì)，因此可以用動態(tài)規(guī)劃法來解決。

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

8. 位操作

位操作符：

OR (\|)	AND (&)	XOR (^)	Left Shift (<<)	Right Shift (>>)	Not (~)
1\|0=1	1&0=0	1^0=1	0010<<2=1000	1100>>2=0011	~1=0

獲得給定數(shù)字n的第i位：(i從0計數(shù)并從右邊開始)

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

例如，獲得數(shù)字10的第2位：

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

9. 概率問題

解決概率相關(guān)的問題通常需要很好的規(guī)劃了解問題（formatting the problem），這里剛好有一個這類問題的簡單例子：

一個房間里有50個人，那么至少有兩個人生日相同的概率是多少？（忽略閏年的事實，也就是一年365天）

計算某些事情的概率很多時候都可以轉(zhuǎn)換成先計算其相對面。在這個例子里，我們可以計算所有人生日都互不相同的概率，也就是：365/365 + 364/365 + 363/365 + 365-n/365 + 365-49/365，這樣至少兩個人生日相同的概率就是1 – 這個值。

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;

calculateProbability(50) = 0.97

10. 排列組合

組合和排列的區(qū)別在于次序是否關(guān)鍵。

原文鏈接：http://www.programcreek.com/2012/11/top-10-algorithms-for-coding-interview/

譯文鏈接：http://blog.jobbole.com/52144/

責(zé)任編輯：陳四芳來源：伯樂在線

算法面試