数据结构与算法

排序

常见排序算法的比较

排序算法动画演示

排序算法	平均时间复杂度	最坏时间复杂度	空间复杂度	稳定性
冒泡排序	O(n2)	O(n2)	O(1)	稳定
选择排序	O(n2)	O(n2)	O(1)	不稳定
插入排序	O(n2)	O(n2)	O(1)	稳定
归并排序	O(nlogn)	O(nlogn)	O(n)	稳定
快速排序	O(nlogn)	O(n2)	O(nlogn)	不稳定
堆排序	O(nlogn)	O(nlogn)	O(1)	不稳定

快速排序

public class QuickSort {
    public void quickSort(int[] arr, int l, int r) {
        if (l < r) {
            int mid = partition(arr, l, r);
            quickSort(arr, l, mid - 1);
            quickSort(arr, mid + 1, r);
        }
    }

    private int partition(int[] arr, int l, int r) {
        // 选择arr[r]作为主元，对子数组arr[l..r]进行划分
        int x = arr[r];
        int i = l - 1;
        // 维持循环不变式a[l..i] < x, a[i+1..j] >= x
        for (int j = l; j <= r - 1; j++) {
            if (arr[j] < x) {
                i++;
                // 交换arr[i]和arr[j]
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        // 交换arr[i+1]与arr[r]
        int temp = arr[i+1];
        arr[i+1] = arr[r];
        arr[r] = temp;

        // 返回主元的下标
        return i + 1;
    }
}

快速选择

215. 数组中的第K个最大元素

class Solution {
    // 在数组nums[l..r]中寻找第k大的数
    private int find(int[] nums, int l, int r, int k) {
        if (l == r) return nums[l];
        int x = nums[r];
        int i = l - 1;
        int t;
        // 在循环中维持nums[l..i] <= x, nums[i+1..j] > x
        for (int j = l; j <= r - 1; j++) {
            if (nums[j] <= x) {
                i++;
                // 交换nums[i]和nums[j]
                t = nums[i];
                nums[i] = nums[j];
                nums[j] = t;
            }
        }
        // 交换nums[i+1]和nums[r]
        t = nums[i+1];
        nums[i+1] = nums[r];
        nums[r] = t;

        if (r - i == k) return nums[i+1];
        else if (r - i > k) return find(nums, i+2, r, k);
        else return find(nums, l, i, k - (r-i));
    }

    public int findKthLargest(int[] nums, int k) {
        return find(nums, 0, nums.length-1, k);
    }
}

堆排序

public class HeapSort {
    public void heapSort(int[] arr) {
        buildMaxHeap(arr);
        for (int i = arr.length - 1; i >= 1; i--) {
            // 交换arr[0]和arr[i]，将堆的最大元素保存到数组末尾
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            // arr[0..i-1]为新的堆，调整堆
            maxHeapify(arr, 0, i);
        }
    }

    // 自底向上建堆，时间复杂度O(n)
    private void buildMaxHeap(int[] arr) {
        for (int i = arr.length / 2; i >= 0; i--) {
            maxHeapify(arr, i, arr.length);
        }
    }

    // 维护最大堆的性质
    private void maxHeapify(int[] arr, int i, int heapSize) {
        // 找出arr[i]、arr[i]的左节点、右节点这三者的最大值
        int l = 2 * i + 1;
        int r = 2 * i + 2;
        int largest = i;
        if (l < heapSize && arr[l] > arr[i])
            largest = l;
        if (r < heapSize && arr[r] > arr[largest])
            largest = r;

        if (largest != i) {
            // 交换arr[i]和arr[largest]
            int temp = arr[i];
            arr[i] = arr[largest];
            arr[largest] = temp;
            // 继续调整节点
            maxHeapify(arr, largest, heapSize);
        }
    }
}

归并排序

public class MergeSort {
    public void mergeSort(int[] arr, int l, int r) {
        if (l < r) {
            int mid = (l + r) / 2;
            mergeSort(arr, l, mid);
            mergeSort(arr, mid+1, r);
            merge(arr, l, mid, r);
        }
    }

    // 合并两个有序数组arr[l..mid] arr[mid+1..r]
    private void merge(int arr[], int l, int mid, int r) {
        // 将arr[]中的左右两个有序子数组拷贝到新的数组中
        int n1 = mid - l + 1;
        int n2 = r - mid;
        int[] L = new int[n1+1];
        int[] R = new int[n2+1];
        for (int i = 0; i < n1; i++)
            L[i] = arr[l+i];
        for (int j = 0; j < n2; j++)
            R[j] = arr[mid+1+j];
        // 在两个数组最后各加上一个哨兵
        L[n1] = Integer.MAX_VALUE;
        R[n2] = Integer.MAX_VALUE;

        // 合并两个有序数组
        int i = 0, j = 0;
        for (int k = l; k <= r; k++) {
            if (L[i] < R[j]) {
                arr[k] = L[i];
                i++;
            }
            else {
                arr[k] = R[j];
                j++;
            }
        }
    }
}

二叉树

采用非递归的方式遍历二叉树

前序遍历

144. 二叉树的前序遍历

1. 访问当前节点

2. 右子树入栈

3. 访问左子树

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        LinkedList<TreeNode> stack = new LinkedList<>();
        TreeNode p = root;
        while (p != null || !stack.isEmpty()) {
            while (p != null) {
                // 访问当前节点
                res.add(p.val);
                // 右子树入栈
                stack.add(p.right);
                // 访问左子树
                p = p.left;
            }
            p = stack.removeLast();
        }
        return res;
    }
}

后序遍历

145. 二叉树的后序遍历

后序遍历（左右根）可以采用与前序遍历类似的思路（根右左）：

1. 访问当前节点

2. 将左子树入栈

3. 访问右子树

最后将结果逆序即可。

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        LinkedList<TreeNode> stack = new LinkedList<>();
        TreeNode p = root;

        while (p != null || !stack.isEmpty()) {
            while (p != null) {
                // 访问当前节点
                res.add(0, p.val);
                // 左子树入栈
                stack.add(p.left);
                // 访问右子树
                p = p.right;
            }
            p = stack.removeLast();
        }

        return res;
    }
}

中序遍历

94. 二叉树的中序遍历

1. 将当前节点的最左边一条链压入栈中

2. 取出栈顶元素，如果它有右子树，对右子树执行操作1

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        LinkedList<TreeNode> stack = new LinkedList<>();
        TreeNode p = root;
        while (p != null || !stack.isEmpty()) {
            // 将当前节点的最左边一条链压入栈中
            while (p != null) {
                stack.add(p);
                p = p.left;
            }
            // 取出栈顶元素
            p = stack.removeLast();
            res.add(p.val);
            // 将当前节点置为右子树
            p = p.right;
        }
        return res;
    }
}

动态规划

经典问题

120. 三角形最小路径和 53. 最大子序和 152. 乘积最大子数组 72. 编辑距离

121. 买卖股票的最佳时机 122. 买卖股票的最佳时机 II 123. 买卖股票的最佳时机 III 188. 买卖股票的最佳时机 IV 309. 最佳买卖股票时机含冷冻期 714. 买卖股票的最佳时机含手续费

198. 打家劫舍 213. 打家劫舍 II

正则表达式匹配 leetcode12 通配符 leetcode44 扔鸡蛋 leetcode887 俄罗斯套娃信封 leetcode354

背包

leetcode 416, 494(01背包) leetcode 518, 322(完全背包) leetcode 474(⼆维费⽤背包)

线性

300. 最长上升子序列 673. 最长递增子序列的个数 1143. 最长公共子序列

区间

以区间作为状态 312. 戳气球 最⻓回⽂⼦序列 leetocde516 回⽂⼦序列个数 leetcode730 最优三⻆形剖分 leetcode1039 刷串问题 leetcode664

树形

337. 打家劫舍 III 最⼤权路径 leetcode124 树的直径 leetcode543,1245 最⼤⼆叉搜索⼦树 leetcode333 树形依赖 leetcode337

状压

以集合的状态做转移 leetcode 526,464,935,1349

数位

以数字位为状态 leetcode902,1015,233

计数型

都可以以组合数学的⽅法写出组合数，然后dp求组合数 leetcode 62, 63 leetcode 22, 96(卡特兰数) leetcode1259(借助卢卡斯定理求⼤组合数模质数的结果)

递推型

所有线性递推关系都可以⽤矩阵快速幂做，O(logN)，最典型是斐波那契数列 leetcode 50, 70,372,509,935,957, 1137

概率型

求数学期望 leetcode 808, 837

博弈型

策梅洛定理，CG定理 翻转游戏(leetcode293,294) Nim游戏(leetcode292) ⽯⼦游戏(leetcode877,1040) 井字游戏(leetcode348,794,1275)

记忆化递归

本质是 dfs + 记忆化，⽤在状态的转移⽅向不确定的情况 矩阵中的最⻓上升路径 leetcode329