面試常見十大類算法匯總

jopen 8年前發布 | 14K 次閱讀算法二叉樹

出處：http://www.iteye.com

1.String/Array/Matrix

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

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

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

2.鏈表

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

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標準庫中已經包含一個叫做Stack的類，鏈表也可以作為一個隊列使用（add()和remove()）。（鏈表實現隊列接口）如果你在面試過程中，需要用到棧或隊列解決問題時，你可以直接使用它們。

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

3.樹&堆

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

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

下面是一些與二叉樹有關的概念：

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

堆（Heap）是一個基于樹的數據結構，也可以稱為優先隊列（ PriorityQueue ），在隊列中，調度程序反復提取隊列中第一個作業并運行，因而實際情況中某些時間較短的任務將等待很長時間才能結束，或者某些不短小，但具有重要性的作業，同樣應當具有優先權。堆即為解決此類問題設計的一種數據結構。

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

4.Graph

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

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

第三步，使用隊列進行寬度優先搜索

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: 5value: 4

實際中，基于Graph需要經常用到的算法：

克隆Graph

5.排序

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

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

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

6.遞歸和迭代

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

問題：

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

步驟1：查找n和n-1之間的關系

為了獲得n，這里有兩種方法：一個是從第一節臺階到n-1或者從2到n-2。如果f(n)種爬法剛好是爬到n節，那么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;
}

遞歸方法的時間復雜度指數為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)

該遞歸可以很簡單地轉換為迭代。

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

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

7.動態規劃

動態規劃主要用來解決如下技術問題：

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

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

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.位操作

位操作符：

從一個給定的數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;

典型的位算法：

9.概率

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

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

結果：

calculateProbability(50) = 0.97

10.組合和排列

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

例1：

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

例2：

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

基于它們的一些常見算法

本文由用戶 jopen 自行上傳分享，僅供網友學習交流。所有權歸原作者，若您的權利被侵害，請聯系管理員。

轉載本站原創文章，請注明出處，并保留原始鏈接、圖片水印。

本站是一個以用戶分享為主的開源技術平臺，歡迎各類分享！

本文地址：http://www.baiduhome.net/lib/view/open1452067314230.html

算法二叉樹