编程面试过程中常见的10大算法

1.?字符串

toCharArray() // 获得字符串对应的char数组
Arrays.sort()  // 数组排序
Arrays.toString(char[] a) // 数组转成字符串
charAt(int x) // 获得某个索引处的字符
length() // 字符串长度
length // 数组大小

2.?链表

class Node {
    int val;
    Node next;

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

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）：二叉树中，可能除了最后一个，每一层都被完全填满，且所有节点都必须尽可能想左靠。

4. 图

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,n5};
        n5.neighbors = new GraphNode[]{n1,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);
                }
            }
        }
    }
}

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

• 《视觉直观感受 7 种常用的排序算法》
• 《视频: 6分钟演示15种排序算法》

6.?递归?vs.?迭代

public static int f(int n){
    if(n <= 2) return n;
    int x = f(n-1) + f(n-2);
    return x;
}

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.?动态规划

1. 一个问题可以通过更小子问题的解决方法来解决（译者注：即问题的最优解包含了其子问题的最优解，也就是最优子结构性质）。
2. 有些子问题的解可能需要计算多次（译者注：也就是子问题重叠性质）。
3. 子问题的解存储在一张表格里，这样每个子问题只用计算一次。
4. 需要额外的空间以节省时间。

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

public static boolean getBit(int num,int i){
    int result = num & (1<<i);

    if(result == 0){
        return false;
    }else{
        return true;
    }

9.?概率问题

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;

10.?排列组合