算法模板

链表

题目链接：826. 单链表

快速排序

quick sort的一道题目，关于字符串排序的，剑指offer上的。剑指 Offer 45. 把数组排成最小的数

public static void quickSort(int[] arr, int l, int r){
    if (l >= r) {
        return;
    }
    
    int pivot = arr[l], i = l - 1, j = r + 1;
    
    while (i < j) {
        do i++; while(arr[i] < pivot);
        do j--; while(arr[j] > pivot);
        // 注意：重点在这里，要i < j的时候才需要swap，否则不需要！！！
        if (i < j) swap(arr, i, j);
    }

    // 注意，这里我们要用j来写下面的递归，不能用i，具体原因y总在第二堂课开头里有讲。主要是边界问题。反之，如果我们前面的pivot用得是arr[r]，那么这里就不能用j，只能用i.
    quickSort(arr, l, j);
    quickSort(arr, j + 1, r);
}

// 这种写法应该更加亲民一点，只是while循环多了一点内容。
public static void quickSort(int[] arr, int l, int r){
    if (l >= r) {
        return;
    }
    int i = l, j = r;
    while (i < j) {
        // 注意，这里一定得是j在前，i在后
        while (i < j && arr[j] >= arr[l]) j--;
        while (i < j && arr[i] <= arr[l]) i++;
        swap(arr, i, j);
    }
    swap(arr, i, l);
    quickSort(arr, l, i - 1);
    quickSort(arr, i + 1, r);
}

归并排序

上面的题目一样可以用mergeSort来做，在submission里面可以看。

public static void mergeSort(int[] arr, int l, int r) {
    if (l >= r) {
        return;
    }

    int mid = l  + r >> 1;
    mergeSort(arr, l, mid);
    mergeSort(arr, mid + 1, r);

    int[] temp = new int[r - l + 1];
    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }

    while (i <= mid) {
        temp[k++] = arr[i++];
    }
    while (j <= r) {
        temp[k++] = arr[j++];
    }

    for (int i = 0; i < temp.length; i++) {
        arr[l + i] = temp[i];
    }
} 

二分法

二分查找的边界问题一直很困扰人额，有两种二分查找，一种是求左边界，另一种是求右边界。最直接的题目就是Leetcode 34。既要求左边界，也要求右边界。

注意，这里左边界和右边界只是一种象征，实际的题目不会这么直白。例如LeetCode 875.

回到正题，网上有很多二分查找的模板，这里只写我自己的模板，以下所有的区间全都都是闭区间，思路参考acwing的yxc。

这里有两种情况

区间被分为[l, mid]和[mid + 1, r]

这种情况的意思就是，当我们做check(mid)的时候，mid是否在我们希望的区间内。换句话说，当mid满足条件时，我们是把它放到左区间还是右区间。比如{1,2,2,2,3,4,5,5}，我们要找到2的左边界，那么当我们找到1个“2”的时候，这个2有可能就是我们要找的值，对吧？那么我们就应该让r = mid，把右边不要的部分去掉，再去遍历左边。反之亦然。

这里的终止条件都是l==r！！！！

// 找左边界
public static void binarySearch1(int l, int r){
    int mid = l + r >> 1;
    if (check(mid)){
        r = mid;
    } else {
        l = mid + 1;
    }
}

区间被分为[l, mid - 1]和[mid, r]

道理和上面类似，只是此时需要mid = (l + r + 1)/2。原因在于除法是向下取整，存在精读缺失，有可能无限死循环。

// 找右边界，注意l=mid的时候，要+1
public void binarySearch2(int l, int r){
    int mid = (l + r + 1)/2;
    if (check(mid)) {
        l = mid;
    } else {
        r = mid - 1;
    }
}

单调栈

首先，从名字上来看，单调栈的意思就是，我们通过某些操作，使得栈里的元素都是单调的。

单调栈解决的问题是“给出一个无序数组，找到每个数字左（右）侧离他最近比它大（小）的数字”。如果一个问题能够抽象成这种类型，那么毫无疑问，马上用单调栈。或者说其他变种，类似于LeetCode 155. Min Stack，blog解析见LeetCode 456. 132 Pattern。

举例：给出一个数组a[]，若要找到 a[7]左侧比它大的数字，假设有a[3]和a[5]，那么我们应该选择a[5]而不是a[3]。那么，换句话说，对于任意两个数a[i]和a[j]，如果”a[i] <= a[j] && i < j，那么a[i]可以被抛弃掉，因为对于j后面的数字，a[j]一定是更优的解。”

这种做法的思想可以理解成保守式单调栈，要哪侧的“第一个最大/最小”，就从哪侧开始遍历，保证遍历到每个数的时候，其结果都能确定。

例题：LeetCode 496. Next Greater Element I，该题目的解析link传送门

这里我们写一个模板，是找到每个数字左侧第一个比它大的数字。

public void montonousStack(int[] nums) {
    Stack<Integer> stack = new Stack();

    for (int num : nums) {
        while (!stack.isEmpty() && stack.peek() <= num) {
            stack.pop();
        }

        if (stack.isEmpty()) {
            // 左侧没有数字比它更大
            System.out.print("-1 ");
        } else {
            System.out.printf("%d ", stack.peek());
        }

        stack.push(num);
    }
}

注意：单调栈并不一定是从左向右，或者从右向左！！！

如上面的左侧第一个更大数字，是从左向右遍历的。那么换种思想，我们从右向左遍历：如果当前数字比栈顶或者等于，则压入；若比栈顶大，则不断弹出，直到栈为空或者小于等于栈顶，然后压栈。最后栈底剩下的元素，是没有左侧更大元素的！

这种做法的思想可以理解成探索式单调栈，对于未知的情况，我们先保留，最后再一起处理。

public void montonousStack(int[] nums) {
    Stack<Integer> stack = new Stack();

    for (int i = nums.length； i >= 0; i--) {
        while (!stack.isEmpty() && stack.peek() < nums[i]) {
            System.out.printf("index %d left greater element is %d\n", stack.pop(), nums[i]);
        }
        stack.push(i);
    }
    while (!stack.isEmpty()) {
        System.out.printf("index %d left greater element is %d\n", stack.pop(), -1);
    }
}

单调队列

从单调队列这个名称来看，就是解决某些问题的时候，我们维护一个队列，使得队列里面的的数字呈现单调的情况。

单调队列解决的问题可以抽象为“求滑动窗口里的最大值和最小值”，最直接的题目就是LeetCode 239. Sliding Window Maximum。

对于这种问题，我们举个例子，[1, 3, -1, -3, 5, 3, 6, 7]，窗口大小为3，输出每个窗口里面的最小值（和239基本一致，只是有小区别）。 第一个窗口为[1, 3, -1]，我们可以发现，当-1只要还在我们的窗口里的时候，在-1左侧的1和3就绝不可能为最小值。也就是说这两个数对于我们找窗口内最小值完全是冗余的！！！因此，我们需要一种数据结构，保证窗口的正常运转，要能够一边进，一边出，因此我们选择Java里的Deque，双端队列，逻辑如下。

    public int[] minSlidingWindow(int[] nums, int k) {
        Deque<Integer> deque = new LinkedList();
        int n = nums.length;
        // 这里用res数组来存储结果
        int[] res = new int[n - k + 1];
        
        for (int i = 0; i < n; i++) {
            // 如果当前队列里面存的数字过多，则将最前面的数字弹出，其实就是边界情况，当window里面数字全部都是升序的时候。注意判断是否为空！
            if (!deque.isEmpty() && i - k + 1 > deque.peekFirst()) {
                deque.pollFirst();
            }
            // 将队尾的所有比当前元素大的全部pop出去，因为它们不可能为解。注意，是队尾！！！不是队首！！！而且要注意有等于的情况！！！
            while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
                deque.pollLast();
            } 

            // 这里pollLast以后，队列里要么为空，要么是一列升序的数字！！！！！！至于这里为什么要存index，是因为前面需要判断长度的时候需要用index判断窗口大小。

            deque.offerLast(i);

            // 此时，队首的数字就是当前队列里的最小值！！！
            if (i >= k - 1) {
                res[i - k + 1] = nums[deque.peekFirst()];
            }
        }
        
        return res;
    }
}

我们还可以使用数组来模拟双端队列。注意写法。

// 这里用数组来模拟双端队列，q就是这个队列，里面存的也是index
int N = 100010, hh = 0, tt = -1;
int[] q = new int[N];

public int[] minSlidingWindow(int[] nums, int k) {
    int[] res = new int[nums.length - k + 1];
    
    for (int i = 0; i < nums.length; i++) {
        // 
        if (hh <= tt && i - k + 1 > q[hh]) hh++;
        while (hh <= tt && nums[q[tt]] >= nums[i]) tt--;
        
        q[++tt] = i;
        
        if (i >= k - 1) {
            res[i - k + 1] = nums[q[hh]];
        }
    }
    
    return res;
}

树

递归的写法没啥好说的，这里强调迭代的写法。

前序遍历

题目链接：前序遍历

这里提供两种遍历思路：

1. 遍历时先压右子树，再压左子树。

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        List<Integer> list = new ArrayList<Integer>();
        TreeNode node = root;
        stack.push(node);

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

        return list;
    }
}

2. 压栈的目的只是为了回溯找右节点，不是压左右子树，而是访问过的节点。

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        List<Integer> list = new ArrayList<Integer>();
        TreeNode node = root;

        while (！stack.isEmpty() || node != null) {
            if (node != null) {
                list.add(node.val);
                stack.push(node);
                node = node.left;
            } else {
                node = stack.pop().right;
            }
        }

        return list;
    }
}

中序遍历

题目链接：中序遍历

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        List<Integer> list = new ArrayList<Integer>();
        TreeNode node = root;

        while (node != null) { // 下面的循环里保证了node在遍历未结束时不为null
            if (node.left != null) {
                stack.push(node);
                node = node.left;
            } else {
                list.add(node.val);
                while (node.right == null && !stack.isEmpty()) {
                    node = stack.pop();
                    list.add(node.val);
                }
                node = node.right;
            }
        }

        return list;
    }
}

2. 判断节点是否为空

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        List<Integer> list = new ArrayList<Integer>();
        TreeNode node = root;

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

        return list;
    }
}

后序遍历

题目链接：后序遍历

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        List<Integer> list = new ArrayList<Integer>();
        TreeNode node = root, lastNode = root;
        stack.push(node);

        while (!stack.isEmpty() && node != null) {
            node = stack.pop();
            if ((node.left == null && node.right == null) || node.left == lastNode || node.right == lastNode) {
                // node为叶子节点或者访问返回到当前节点
                list.add(node.val);
                lastNode = node;
            } else {
                // 栈还没压到叶子节点
                stack.push(node);
                if (node.right != null) {
                    stack.push(node.right);
                }
                if (node.left != null) {
                    stack.push(node.left);
                }
            }
        }

        return list;
    }
}

Morris中序遍历

其核心点在于，利用“左子树最右侧节点”来辅助判断是否已经遍历过左子树了。

public List<Integer> inorderTraversal(TreeNode root) {
    // Morris遍历
    TreeNode cur = root;
    List<Integer> list = new ArrayList<>();
    
    while (cur != null) {
        // 判断其有无左子树，如果有，找到它左子树的最右侧节点
        TreeNode mostRight = cur.left;
        
        if (mostRight != null) {
            while (mostRight.right != null && mostRight.right != cur) {
                mostRight = mostRight.right;
            }
            
            if (mostRight.right == null) {
                mostRight.right = cur;
                cur = cur.left;
                continue;
            } else {
                mostRight.right = null;
                list.add(cur.val);
            }
        } else {
            list.add(cur.val);
        }
        cur = cur.right;
    }
    
    return list;
}

并查集

并查集建议观看花花酱的并查集视频讲解

这里使用size来代替rank，也是可以的，复杂度上没有区别。

class UF {
    int[] parents;
    int[] sizes;
    int count;

    public UF(int n) {
        parents = new int[n];
        sizes = new int[n];
        count = n;

        for (int i = 0; i < n; i++) {
            parents[i] = i;
            sizes[i] = 1;
        }
    }

    public int find(int u) {
        if (u == parents[u]) {
            return u;
        }
        parents[u] = find(parents[u]);
        return parents[u];
    }

    public void union(int u, int v) {
        int pu = find(u), pv = find(v);
        if (pu == pv) {
            return;
        } 

        if (sizes[pu] < sizes[pv]) {
            parents[pu] = pv;
            sizes[pv] += sizes[pu];
        } else {
            parents[pv] = pu;
            sizes[pu] += sizes[pv];
        }
    }
}

Trie

class TrieNode {
    TrieNode[] sons;
    boolean isWord;
    
    TrieNode() {
        sons = new TrieNode[26];
        isWord = false;
    }
    
    public TrieNode get(char c) {
        int idx = c - 'a';
        return sons[idx];
    }
    
    public boolean containsKey(char c) {
        int idx = c - 'a';
        return sons[idx] != null;
    }
    
    public void add(char c) {
        int idx = c - 'a';
        sons[idx] = new TrieNode();
    }
}