> For the complete documentation index, see [llms.txt](https://clloud.gitbook.io/notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://clloud.gitbook.io/notes/shu-ju-jie-gou-yu-suan-fa.md).

# 数据结构与算法

## 排序

### 常见排序算法的比较

[排序算法动画演示](https://www.cnblogs.com/onepixel/articles/7674659.html)

| 排序算法 |  平均时间复杂度 |  最坏时间复杂度 |   空间复杂度  | 稳定性 |
| :--: | :------: | :------: | :------: | :-: |
| 冒泡排序 |   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)   | 不稳定 |

### 快速排序

```java
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个最大元素](https://leetcode-cn.com/problems/kth-largest-element-in-an-array/)

```java
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);
    }
}
```

### 堆排序

```java
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);
        }
    }
}
```

### 归并排序

```java
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. 二叉树的前序遍历](https://leetcode-cn.com/problems/binary-tree-preorder-traversal/)

1. 访问当前节点
2. 右子树入栈
3. 访问左子树

```java
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. 二叉树的后序遍历](https://leetcode-cn.com/problems/binary-tree-postorder-traversal/)

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

1. 访问当前节点
2. 将左子树入栈
3. 访问右子树

最后将结果逆序即可。

```java
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. 二叉树的中序遍历](https://leetcode-cn.com/problems/binary-tree-inorder-traversal/)

1. 将当前节点的最左边一条链压入栈中
2. 取出栈顶元素，如果它有右子树，对右子树执行*操作1*

```java
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. 三角形最小路径和](https://leetcode-cn.com/problems/triangle/) [53. 最大子序和](https://leetcode-cn.com/problems/maximum-subarray/) [152. 乘积最大子数组](https://leetcode-cn.com/problems/maximum-product-subarray/) [72. 编辑距离](https://leetcode-cn.com/problems/edit-distance/)

[121. 买卖股票的最佳时机](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/) [122. 买卖股票的最佳时机 II](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/) [123. 买卖股票的最佳时机 III](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/) [188. 买卖股票的最佳时机 IV](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/) [309. 最佳买卖股票时机含冷冻期](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/) [714. 买卖股票的最佳时机含手续费](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/)

[198. 打家劫舍](https://leetcode-cn.com/problems/house-robber/) [213. 打家劫舍 II](https://leetcode-cn.com/problems/house-robber-ii/)

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

### 背包

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

### 线性

[300. 最长上升子序列](https://leetcode-cn.com/problems/longest-increasing-subsequence/) [673. 最长递增子序列的个数](https://leetcode-cn.com/problems/number-of-longest-increasing-subsequence/) [1143. 最长公共子序列](https://leetcode-cn.com/problems/longest-common-subsequence/)

### 区间

以区间作为状态 [312. 戳气球](https://leetcode-cn.com/problems/burst-balloons/) 最⻓回⽂⼦序列 leetocde516 回⽂⼦序列个数 leetcode730 最优三⻆形剖分 leetcode1039 刷串问题 leetcode664

### 树形

[337. 打家劫舍 III](https://leetcode-cn.com/problems/house-robber-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