閱讀132 返回首頁    go 小米淨水器

編程麵試的10大算法概念匯總(http://blog.jobbole.com/52144/)

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

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

1. 字符串

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

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

2. 鏈表

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

1
2
3
4
5
6
7
8
9
classNode {
    intval;
    Node next;
  
    Node(intx) {
        val = x;
        next =null;
    }
}

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

棧：

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{
    Node top; 
  
    publicNode peek(){
        if(top !=null){
            returntop;
        }
  
        returnnull;
    }
  
    publicNode pop(){
        if(top ==null){
            returnnull;
        }else{
            Node temp =newNode(top.val);
            top = top.next;
            returntemp;    
        }
    }
  
    publicvoidpush(Node n){
        if(n !=null){
            n.next = top;
            top = n;
        }
    }
}

隊列：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
classQueue{
    Node first, last;
  
    publicvoidenqueue(Node n){
        if(first ==null){
            first = n;
            last = first;
        }else{
            last.next = n;
            last = n;
        }
    }
  
    publicNode dequeue(){
        if(first ==null){
            returnnull;
        }else{
            Node temp =newNode(first.val);
            first = first.next;
            returntemp;
        }   
    }
}

3. 樹

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

1
2
3
4
5
classTreeNode{
    intvalue;
    TreeNode left;
    TreeNode right;
}

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

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

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

4. 圖

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

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

1) 定義GraphNode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
classGraphNode{ 
    intval;
    GraphNode next;
    GraphNode[] neighbors;
    boolean visited;
  
    GraphNode(intx) {
        val = x;
    }
  
    GraphNode(intx, GraphNode[] n){
        val = x;
        neighbors = n;
    }
  
    publicStringtoString(){
        return"value: "+this.val; 
    }
}

2) 定義一個隊列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{
    GraphNode first, last;
  
    publicvoidenqueue(GraphNode n){
        if(first ==null){
            first = n;
            last = first;
        }else{
            last.next = n;
            last = n;
        }
    }
  
    publicGraphNode dequeue(){
        if(first ==null){
            returnnull;
        }else{
            GraphNode temp =newGraphNode(first.val, first.neighbors);
            first = first.next;
            returntemp;
        }   
    }
}

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

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) {
        GraphNode n1 =newGraphNode(1); 
        GraphNode n2 =newGraphNode(2); 
        GraphNode n3 =newGraphNode(3); 
        GraphNode n4 =newGraphNode(4); 
        GraphNode n5 =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(GraphNode root, intx){
        if(root.val == x)
            System.out.println("find in root");
  
        Queue queue =newQueue();
        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:
1
2
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。

6. 遞歸 vs. 迭代

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

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

步驟1:找到走完前n步台階和前n-1步台階之間的關係。

為了走完n步台階，隻有兩種方法：從n-1步台階爬1步走到或從n-2步台階處爬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的指數級，因為有很多冗餘的計算，如下：

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)

直接的想法是將遞歸轉換為迭代：

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

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

 

7. 動態規劃

動態規劃是解決下麵這些性質類問題的技術：

  1. 一個問題可以通過更小子問題的解決方法來解決（譯者注：即問題的最優解包含了其子問題的最優解，也就是最優子結構性質）。
  2. 有些子問題的解可能需要計算多次（譯者注：也就是子問題重疊性質）。
  3. 子問題的解存儲在一張表格裏，這樣每個子問題隻用計算一次。
  4. 需要額外的空間以節省時間。

爬台階問題完全符合上麵的四條性質，因此可以用動態規劃法來解決。

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);//store results so only calculate once!
    returnA[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

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

1
2
3
4
5
6
7
8
publicstaticboolean getBit(intnum, inti){
    intresult = num & (1<<i);
  
    if(result ==0){
        returnfalse;
    }else{
        returntrue;
    }

例如，獲得數字10的第2位：

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

9. 概率問題

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

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

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

1
2
3
4
5
6
7
8
9
publicstaticdouble caculateProbability(intn){
    double x =1; 
  
    for(inti=0; i<n; i++){
        x *=  (365.0-i)/365.0;
    }
  
    double pro = Math.round((1-x) * 100);
    returnpro/100;

calculateProbability(50) = 0.97

10. 排列組合

組合和排列的區別在於次序是否關鍵。

如果你有任何問題請在下麵評論。

參考/推薦資料：
1. Binary tree
2. Introduction to Dynamic Programming
3. UTSA Dynamic Programming slides
4. Birthday paradox
5. Cracking the Coding Interview: 150 Programming Interview Questions and Solutions, Gayle Laakmann McDowell

 

最後更新：2017-04-03 14:54:35

  上一篇：go 基於smtp協議的郵件係統（自己寫的）
  下一篇：go Apache支持.htaccess