常见算法题

1、二分查找
右侧边界为length-1;
while left <= right 跳出条件为区间中没有数据了。
right = mid – 1;
寻找左侧边界，需要检查left大于length，left是否不等于target。
寻找右侧边界，需要检查right小于0，right是否不等于target。

2、快速排序

从数组中取第一个数作为pivot,大于该数的划分到右边，小于的划分到左边。双指针，while循环left < right。
while(left < right && nums [left] <= pivot)
找到左边大于pivot和右边小于pivot的数之后交换

public static int partition(int[] nums, int start, int end){
        int pivot = nums[start];
        int left = start + 1, right = end;
        while(left < right){
            //从左找到第一个比基数大的数
            while(left < right && nums[left] <= pivot)
            {
                left++;
            }
            //从右找到第一个比基数小的数
            while(left < right && nums[right] >= pivot)
            {
                right--;
            }
            //交换位置
            if(left < right){
                exchange(nums, left, right);
                left++;
                right--;
            }
        }
        if(left == right && nums[right] > pivot) right--;
        exchange(nums, start, right);
        return right;
    }
复制代码

3、寻找第K大的数

最大堆实现
PriorityQueue

代码是求最小K个数。

public static int[] smallestK(int[] arr, int k) {
    int[] vec = new int[k];
    if (k == 0) { // 排除 0 的情况
        return vec;
    }
    PriorityQueue<Integer> queue = new PriorityQueue<Integer>(new Comparator<Integer>() {
        public int compare(Integer num1, Integer num2) {
            return num2 - num1;
        }
    });
    for (int i = 0; i < k; ++i) {
        queue.offer(arr[i]);
    }
    for (int i = k; i < arr.length; ++i) {
        if (queue.peek() > arr[i]) {
            queue.poll();
            queue.offer(arr[i]);
        }
    }
    for (int i = 0; i < k; ++i) {
        vec[i] = queue.poll();
    }
    return vec;
}
复制代码

4、前序、中序、后序、层序遍历二叉树

前序

public List<Integer> orderTraversal(TreeNode root) {
  List<Integer> list = new ArrayList<>();
  if(root == null) return list;

  Stack<TreeNode> stack = new Stack<>();
  stack.push(root);

  while(!stack.isEmpty()) {
    TreeNode cur = stack.pop();
    if(cur.right != null) stack.push(cur.right);
    if(cur.left != null) stack.push(cur.left);
    list.add(cur.val);
  }

  return list;
}
复制代码

中序

public List<Integer> inorderTraversal(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    List<Integer> list = new ArrayList<>();
    if(root == null) return list;
    
    TreeNode cur = root;
    while(!stack.isEmpty() || cur != null) {
        while(cur != null) {
          stack.push(cur);
          cur = cur.left;
        }

        cur = stack.pop();
        list.add(cur.val);
        cur = cur.right;
    }

    return list;
}
复制代码

后序

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
//后序遍历：左 右 根 --> 根 右 左
        List<Integer> res = new ArrayList<>();
        if(root == null) return res;

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            res.add(node.val);
            if(node.left != null) stack.push(node.left);
            if(node.right != null) stack.push(node.right);
        }
        Collections.reverse(res);
        return res;
    }
}

复制代码

5、反转链表
迭代法：
pre = null;
while中存一下下个节点next.

递归法：

public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode newHead = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return newHead;
}
复制代码

6、判断链表是否有环

快慢指针，判断是否相遇。

寻找链表形成环的位置

同时从头出发，快慢指针相遇时，快指针从头继续出发，相遇位置即为形成环的位置，数学推导。

7、LRU实现

HashMap + 双向链表

Node
DoubleList: getSize\addLast\remove\removeFirst
LRUCathe: makeRecentLy\addRecentLy\deleteKey\removeLeastRecentLy

class Node {
    private int key, val;
    private Node pre, next;

    public Node(int key, int val) {
        this.key = key;
        this.val = val;
    }
}

class DoubleList {
    Node head, tail;
    private int size;

    public DoubleList() {
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head.next = tail;
        tail.pre = head;
        size = 0;
    }

    public int getSize() {
        return size;
    }

    public void addLast(Node node) {
        node.pre = tail.pre;
        node.next = tail;
        tail.pre.next = node;
        tail.pre = node;
        size++;
    }

    public void remove(Node node) {
        node.pre.next = node.next;
        node.next.pre = node.pre;
        size--;
    }

    public Node removeFirst() {
        if (head.next == tail) {
            return null;
        }
        Node first = head.next;
        remove(first);
        return first;
    }

}

class LRUCache {
    private DoubleList cache;
    private HashMap<Integer, Node> map;
    private int cap;

    public LRUCache(int cap) {
        this.cap = cap;
        map = new HashMap<>();
        cache = new DoubleList();
    }

    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }
        // 将该数据提升为最近使用的
        makeRecently(key);
        return map.get(key).val;
    }

    public void put(int key, int val) {
        if (map.containsKey(key)) {
            // 删除旧的数据
            deleteKey(key);
            // 新插入的数据为最近使用的数据
            addRecently(key, val);
            return;
        }

        if (cap == cache.getSize()) {
            // 删除最久未使用的元素
            removeLeastRecently();
        }
        // 添加为最近使用的元素
        addRecently(key, val);
    }

    /* 将某个 key 提升为最近使用的 */
    private void makeRecently(int key) {
        Node x = map.get(key);
        // 先从链表中删除这个节点
        cache.remove(x);
        // 重新插到队尾
        cache.addLast(x);
    }

    /* 添加最近使用的元素 */
    private void addRecently(int key, int val) {
        Node x = new Node(key, val);
        // 链表尾部就是最近使用的元素
        cache.addLast(x);
        // 别忘了在 map 中添加 key 的映射
        map.put(key, x);
    }

    /* 删除某一个 key */
    private void deleteKey(int key) {
        Node x = map.get(key);
        // 从链表中删除
        cache.remove(x);
        // 从 map 中删除
        map.remove(key);
    }

    /* 删除最久未使用的元素 */
    private void removeLeastRecently() {
        // 链表头部的第一个元素就是最久未使用的
        Node deletedNode = cache.removeFirst();
        // 同时别忘了从 map 中删除它的 key
        int deletedKey = deletedNode.key;
        map.remove(deletedKey);
    }
复制代码

LinkedHashMap

    public class LRUCathe {
        int capacity;
        LinkedHashMap<Integer, Integer> cathe = new LinkedHashMap<>();
        public LRUCathe(int capticy) {
            this.capacity = capticy;
        }
        public int get(int key) {
            if (!cathe.containsKey(key)) {
                return -1;
            }
            makeItRecently(key);
            return cathe.get(key);
        }
        public void put(int key, int val) {
            if (cathe.containsKey(key)) {
                cathe.put(key, val);
                makeItRecently(key);
            }
            if (cathe.size() >= capacity) {
                int oldestKey = cathe.keySet().iterator().next();
                cathe.remove(oldestKey);
            }
            cathe.put(key, val);
        }
        private void makeItRecently(int key) {
            int val = cathe.get(key);
            cathe.remove(key);
            cathe.put(key, val);
        }
    }
复制代码

8、两个栈实现队列

一个inStack
一个outStack
push进inStack
peek就判断outStack是否空，为空就转移inStack，不为空直接返回peek
pop先执行peek操作，然后pop outStack

9、队列实现栈

10、背包问题

11、买卖股票

12、打家劫舍