面试常用手写代码

排序

快速排序

static int[] a = {6, 1, 2, 7, 9, 11, 4, 5, 10, 8};

static void quickSort(int left, int right) {
    int i, j, t, temp;
    if (left > right) {
        return;
    }
    temp = a[left];
    i = left;
    j = right;
    while (i != j) {
        while (a[j] >= temp && i < j) {
            j--;
        }
        while (a[i] <= temp && i < j) {
            i++;
        }
        if (i < j) {
            t = a[i];
            a[i] = a[j];
            a[j] = t;
        }
    }
    a[left] = a[i];
    a[i] = temp;
    quickSort(left, i - 1);
    quickSort(i + 1, right);
}

归并排序

void mergeSort(int[] arr, int start, int end) {
       if (start < end) {
           //折半成两个小集合，分别进行递归
           int mid = (start + end) / 2;
           mergeSort(arr, start, mid);
           mergeSort(arr, mid + 1, end);
           //把有序小集合，归并成大集合
           merge(arr, start, mid, end);
       }
   }

   void merge(int[] arr, int start, int mid, int end) {
       //开辟额外大集合
       int[] temp = new int[end - start + 1];
       int p1 = start, p2 = mid + 1, p = 0;
       //比较两个小集合放入大集合
       while (p1 < mid && p2 < end) {
           if (arr[p1] <= arr[p2]) {
               temp[p++] = arr[p1++];
           } else {
               temp[p++] = arr[p2++];
           }
       }
       //左侧有剩余
       while (p1 < mid) {
           temp[p++] = arr[p1++];
       }
       //右侧有剩余
       while (p2 < end) {
           temp[p++] = arr[p2++];
       }
       //复制回原数组
       for (int i = 0; i < temp.length; i++) {
           arr[i + start] = temp[i];
       }
   }

堆排序

单例

双重校验锁

volatile 的一个语义禁止指令重排优化。在读取变量的时候直接从内存读取，保证所有线程看到的变量值都是相同的，
synchronized关键字锁住类
进入Synchronized 临界区以后，还要再做一次判空。因为当两个线程同时访问的时候，线程A构建完对象，线程B也已经通过了最初的判空验证，不做第二次判空的话，线程B还是会再次构建instance对象。

public class Singleton {
  private volatile static Singleton instance = null;
  private Singleton(){}
  public static Singleton getInstance(){
  //检查实例，如果不存在，就进入同步代码块
      if (instance==null){//  双重检测机制  
          synchronized(Singleton.class){//1  同步锁 类对象加锁
              if(instance == null){//2  双重检测机制
                  instance = new Singleton();//3  
              }
          }
      }
      return instance;
  }
}

静态内部类

public class Singleton {
    private static class LazyHolder{
        private static final Singleton INSTANCE = new Singleton();
    }
    private Singleton(){}
    public static Singleton getInstance(){
      return LazyHolder.INSTANCE;
    }
}

enum

// JVM会组织反射获取枚举类的私有构造方法
public enum Singleton {
    INSTANCE;
    public void whateverMethod() {

    }
}

链表

单链表反转

 Node reverse(Node head) {
    if (head == null) {
        return null;
    }
    Node prev = null;
    Node now = head;
    while (now != null) {
        Node next = now.next;
        now.next = prev;
        prev = now;
        now = next;
    }
    return prev;
}

删除重复值

  Node deleteRepeat(Node head) {
    if (null == head || null == head.next) {
        return head;
    }
    Node pre = head;
    Node cur = head.next;

    while (cur != null) {
        if (cur.val == pre.val) {
            pre.next = cur.next;
        } else {
            pre = cur;
        }
        if (cur.next == null) {
            return head;
        }
        cur = cur.next;
    }
    return cur;
}

判断链表是否有环

Node meetingNode(Node head) {
    if (head == null) {
        return null;
    }
    Node slow = head.next;
    if (slow == null) {
        return null;
    }
    Node fast = slow.next;
    while (slow != null && fast != null) {
        if (slow == fast) {
            return fast;
        }
        slow = slow.next;
        fast = fast.next;
        if (fast != null) {
            fast = fast.next;
        }
    }
    return null;
}

链表中环入口节点

Node nodeOfLoop(Node head) {
    if (head == null) {
        return null;
    }
    //得到相遇节点
    Node meetingNode = meetingNode(head);
    if (meetingNode == null) {
        return null;
    }
    //得到环节点数
    int nodeInLoopNum = 1;
    Node p1 = meetingNode;
    while (p1.next != meetingNode) {
        p1 = p1.next;
        ++nodeInLoopNum;
    }
    p1 = head;
    Node p2 = head;
    //p1先移动环节点数nodeInLoopNum步
    for (int i = 0; i < nodeInLoopNum; i++) {
        p1 = p1.next;
    }
    //然后p1,p2以相同速度移动
    while (p1 != p2) {
        p1 = p1.next;
        p2 = p2.next;
    }
    return p1;
}

判断两个链表是否相交

boolean isIntersert(Node h1, Node h2) {
    if (h1 == null || h2 == null) {
        return false;
    }
    Node tail = h1;
    Node tail2 = h2;
    while (tail.next != null) {
        tail = tail.next;
    }
    while (tail2.next != null) {
        tail2 = tail2.next;
    }
    return tail == tail2;
}

二叉树

非递归遍历二叉树

栈：先入后出

void preOrder(Node head) {
       if(head != null) {
           Stack<Node> stack = new Stack<>();
           stack.push(head);
           while(!stack.isEmpty()) {
               head = stack.pop();
               System.out.print(head.val);
               if (head.right != null)
                   stack.push(head.right);
               if (head.left != null)
                   stack.push(head.left);
           }
       }
   }

二叉树的深度

 int findDeep(BiTree root) {  
    int deep = 0;  
    if(root != null){  
        int lchilddeep = findDeep(root.left);  
        int rchilddeep = findDeep(root.right);  
        deep = lchilddeep > rchilddeep ? lchilddeep + 1 : rchilddeep + 1;  
    }  
    return deep;  
}

层次打印二叉树

void printTree(Tree root) {
    if (root != null) {
        //下一层的节点数
        int nextLevel = 0;
        //当前层还没打印的节点说
        int tobePrint = 1;
        Stack<Tree> stack = new Stack<>();
        stack.push(root);
        while (!stack.empty()) {
            Tree node = stack.pop();
            System.out.println(node.value);
            if (node.left != null) {
                stack.push(node.left);
                nextLevel++;
            }
            if (node.right != null) {
                stack.push(node.right);
                nextLevel++;
            }
            tobePrint--;
            if (tobePrint == 0) {
                System.out.println("\n");
                tobePrint = nextLevel;
                nextLevel = 0;

            }
        }
    }
}

判断tree2是否为tree1子结构

boolean hasSubTree(Tree root1, Tree root2) {
    boolean result = false;
    if (root1.value == root2.value) {
        result = tree1hasTree2(root1, root2);
    }
    if (!result) {
        result = hasSubTree(root1.left, root2);
    }
    if (!result) {
        result = hasSubTree(root1.right, root2);
    }
    return result;
}

boolean tree1hasTree2(Tree root1, Tree root2) {
    if (root2 == null || root1 == null) {
        return true;
    }
    if (root1.value != root2.value) {
        return false;
    }
    return tree1hasTree2(root1.left, root2.left) && tree1hasTree2(root1.right, root2.right);
}

数组

合并两个有序数据，结果任然有序

 int[] merge(int[] a, int[] b) {
    int[] result;
    result = new int[a.length + b.length];
    int i = 0, j = 0, k = 0;
    while (i < a.length && j < b.length) {
        if (a[i] < b[j]) {
            result[k++] = a[i++];
        } else {
            result[k++] = b[j++];
        }
    }
    while (i < a.length) {
        result[k++] = a[i++];
    }
    while (j < b.length) {
        result[k++] = b[j++];
    }
    return result;
}

二分查找

int binarySearch(int[] arr, int key) {
     int low = 0;
     int high = arr.length - 1;

     while (low <= high) {
         int mid = (low + high) / 2;
         if (key == arr[mid]) {
             return mid;
         } else if (key > arr[mid]) {
             low = mid + 1;
         } else {
             high = mid - 1;
         }
     }
     return 0;
 }

矩阵

顺时针打印矩阵

剪绳子求最大乘积

动态规划

• 求问题的最优解
• 整体问题的最优解是依赖各个子问题的最优解
• 把大问题分解成若干小问题，小问题之间还有互相重叠的更小的子问题
• 从上往下分析问题，从下往上解决问题
  为了避免重复求解子问题通常先计算小问题的最优解并存储下来，在以此基础求取大问题最优解。　 　

int maxCuttingSolution(int length) {
     if (length <= 2) {
         return 1;
     }
     if (length == 3) {
         return 2;
     }
     int[] products = new int[length + 1];
     products[0] = 0;
     products[1] = 1;
     products[2] = 2;
     products[3] = 3;
     int max = 0;
     //i是顺序递增的，计算的顺序是自下而上的
     for (int i = 4; i <= length; i++) {
         max = 0;
         for (int j = 1; j <= i / 2; j++) {
             //在求f(i)之前，对于每一个j而言，f(j)都已经求解出来了
             int product = products[j] * products[i - j];
             if (max < product) {
                 max = product;
             }
             products[i] = max;
         }
     }
     return products[length];
 }

贪婪算法

每一步都做最贪婪得选择，基于这个选择，能够得到最优解。

/**
 * 当长度>=5时，尽可能多剪长度为3得绳子，当剩下绳子长度为4时，把绳子剪成长度为2得绳子
 */
 int maxCuttingSolution1(int length) {
    if (length <= 2) {
        return 1;
    }
    if (length == 3) {
        return 2;
    }
    //尽可能剪去长度为3的绳子段
    int cutThree = length / 3;
    if (length - cutThree * 3 == 1) {
        cutThree -= 1;
    }
    int cutTwo = (length - cutThree * 3) / 2;
    // pow(x, y) 返回 x 的 y 次幂。
    return (int) Math.pow(3, cutThree) * (int) Math.pow(2, cutTwo);
}