数据结构与算法

1. 概述

包括但不限于以下内容：

Basic Data Structure and Algorithms
Design techniques of Algorithms
- Dynamic Programming
- Greedy Algorithms
  - Intervals Problems
  - huffman tree
- Recursive
- Brute Force Search
  - DFS + Backtrack
  - BFS + Branch-and-Bound
- Emumeration Search
  - Permutation
- Linear Programming
- Approximation Algorithms
- Random Algorithms
Databases
- SQL Solutions
- Deep Learning for Databases
Concurrency Algoritms
Analisys of time and space complexity

2. 算法列表

最短路径类型	算法	时间复杂度	算法类型
边权均为正，单源最短路径，稠密图	朴素dijkstra	O(n^2)	贪心
边权均为正，单源最短路径，稀疏图	heap+dijkstra	O(mlogn)	贪心
边权存在负值，单源最短路径，限制最短路径<=k	bellman-ford	O(nm)	离散数学、动态规划
边权存在负值，单源最短路径, 不限制	SPFA	平均情况下为O(m)，最坏O(nm)	BFS优化bellman-ford
多源(起点)汇(终点)最短路径	floyd	O(n^3)	动态规划

最小生成树类型	算法	时间复杂度	算法类型
稠密图	朴素prim	O(n^2)	贪心
稀疏图	heap+prim	O(mlogn)	贪心
稀疏图	kruskal	O(mlogm)	贪心

注意：如果点数n和边数m在同一个数量级为稀疏图，如果m和n^2在一个数量级，则该图为稠密图。

math
Random/Shuffle/Reservior Sampling
Databases
- SQL solutions
  - LeetCode175.sql Combine Two Tables AC
  - find kth elements
  - LeetCode196.sql Delete Duplicate Emails AC
  - LeetCode197.sql Rising Temperature AC
  - LeetCode620.sql AC
  - LeetCode626.sql AC
  - LeetCode595.sql Big Countries AC
  - LeetCode596.sql Classes More Than 5 Students AC
  - LeetCode627.sql Swap Salary AC
  - QS.sql
  - 统计参数，其中均值，最大值，最小值，平均值，计数都有内置的聚集函数
    - Median.sql 中位数
    - ModalNumber.sql 众数
- Deep Learning for Databases
  - Neural Network using Numpy
    - NN_01
    - NN_02
  - Neural Network using Pytorch
    - NN_03
    - NN_04
    - NN_05
  - Linear Model
  - Deep Learning
Concurrency Algorithms

3. 算法设计技术

Dynamic Programming
- 背包型
  - 一定要注意背包问题初始化的含义，何时为0，何时为INF，何时为-INF；其次要注意f[i]到含义是<=i还是=i,这与初始化有关
  - 背包模型参见dd大神的github https://github.com/tianyicui/DP-Book
  - 0-1背包问题
    - 01背包最值型裸题模板
    - 01背包计数型裸题模板
      - NowCoder1042A.cpp 数字组合
  - 完全背包问题
    - 完全背包最值型裸题模板
      - intSplit.cpp 整数划分
    - 完全背包计数型
      - NowCoder1042B.cpp 自然数拆分
  - 多重背包问题
  - 混合背包问题
    - 混合背包裸题模板
  - 分组背包问题
    - 分组背包最值型裸题模板
  - 二维费用的背包问题
    - 二维费用的01背包最值型裸题模板
  - 背包问题求具体方案
  - 有依赖的背包裸题模板
- 线性DP
  - 定义：递推关系存在一个近似的线性关系，我们就称为线性DP，区别于树形DP.其实不需要严格地将DP分型。
  - triangleDP.cpp 数字三角形
    - LeetCode120.cpp Triangle AC
  - LeetCode322.cpp Coin Change AC
  - LeetCode62.cpp Unique Paths AC
    - LeetCode63.cpp Unique Paths II AC
  - NOI1287.cpp 最低通行费 AC
  - LeetCode64.cpp Minimum Path Sum AC
  - P1004_luogu.cpp 方格取数 AC
  - P1006_luogu.cpp 传纸条 AC
  - LeetCode741.cpp Cherry Pickup AC
  - LeetCode152.cpp Maximum Product Subarray AC
  - LeetCode10.cpp Regular Expression Matching AC
  - LeetCode55.cpp Jump Game DP(AC) greedy(AC)
  - LeetCode70.cpp Climbing Stairs AC
  - LeetCode509.cpp Fibonacci Number AC
    - LeetCode1137.cpp N-th Tribonacci Number AC
  - 最长上升子序列(LIS)
    - 求LIS的长度
    - 求一个LIS的解 (同求LIS的长度，只要在其上稍加变形即可)
      - POJ2533.cpp 最长上升子序列
      - LeetCode300.cpp Longest Increasing Subsequence AC
    - 求LIS的个数
      - LeetCode673.cpp Number of Longest Increasing Subsequence AC
    - 求所有LIS的解
  - Edit Distance
    - editDistance.cpp 最短编辑距离
  - 最长公共子序列 (LCS)
    - LCS.cpp 最长公共子序列长度
- 区间DP
  - NowCoder1043A.cpp 石子合并 AC
- 计数型
  - intSplit.cpp 整数划分
- 数位统计型
- 状态压缩型
  - [蒙德里安的梦想状态压缩的经典应用]
- 树形DP
  - 有依赖的背包裸题模板
- 状态机模型
- DP优化方法
  - 单调队列优化DP
  - 斜率优化DP
- 记忆化搜索(DP问题递归写法的学名，属于DP的一种实现方法)
  - snowing.cpp 滑雪记忆化搜索
Greedy Algorithms
Brute Force Search
- DFS + Backtrack
- BFS + Branch-and-Bound

method	extra space	priorities	Data Structure
DFS	O(h)	无	stack
BFS	O(2^h)	shortest path(权重必须为1，否则不能找到最短路径)、topology sort	queue

Recursive
Emumeration Search
- Permutation 本题是一个Generation in lexicographic order，具体见链接 https://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order
  - LeetCode31.cpp Next Permutation AC
  - LeetCode46.cpp Permutations AC 调用了LeetCode31.cpp的Next Permutation函数
  - LeetCode47.cpp Permutations II AC 和LeetCode46.cpp代码完全一样
  - LeetCode60.cpp Permutation Sequence AC LeetCode31.cpp变形题
  - 说明：这四道题目中，采用了三种方法：wiki 方法、C++ STL next_permutation、DFS 搜索方法，其中 DFS 搜索只能用在没有重复元素的情况下，如果存在重复元素 DFS 会生成重复序列，除非想办法进行特殊判断，因此在有重复元素的情况下，只能采用 C++ STL next_permutation 方法和 wiki 方法来做。C++ STL next_permutation 方法库中的实现采用了 wiki 方法，这样的封装使得 permutation 问题变得更加简洁。

4. 时空复杂度分析

4.1 理论

 int cal(int n) {
   int sum = 0;
   int i = 1;
   for (; i <= n; ++i) {
     sum = sum + i;
   }
   return sum;
 }

如上述代码，在上述代码中，只有for循环中的sum+=i被执行了n次，其它代码的执行均与n无关。本例中，我们将算法的时间复杂度表示为O(n)，表示算法的执行时间与n成线性比例。在算法分析中，用大O表示时间复杂度，大O不是算法的真正执行时间，而是表示代码的执行时间随数据规模增长的变化趋势，所有我们也称为渐进时间复杂度。常见的时间复杂度包括：

$O(1) < O(lgn) < O(n) < O(nlogn) < O(n^2) < O(2^n) < O(n!)$ 其中，$O(2^n) < O(n!)$ 被称为$NP$难问题。为使得公式能够真长显示，请在chrome的扩展程序中，打开chrome网上应用店，然后搜索MathJax Plugin for Github，下载该插件，并且启用，就可以让上述公式正常显示。

在时空复杂度分析中，有下面三个法则：

只关注循环执行次数最多的一段代码
加法法则：总复杂度等于量级最大的那段代码的复杂度，该法则适用于多段平行代码段，总的时间复杂度为最大
乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

4.2 最好，最坏、平均、时间复杂度分析

3.1节讲了基本的时间复杂度表示方法，本节将重点讲述最好、最坏、平均、均摊时间复杂度分析，这样便有了完整的时间复杂度分析方法。

// n 表示数组 array 的长度
int find(int[] array, int n, int x) {
  int i = 0;
  int pos = -1;
  for (; i < n; ++i) {
    if (array[i] == x) pos = i;
  }
  return pos;
}

上述代码的时间复杂度为O(n)，代码性能较差，修改为下面部分：

// n 表示数组 array 的长度
int find(int[] array, int n, int x) {
  int i = 0;
  int pos = -1;
  for (; i < n; ++i) {
    if (array[i] == x) {
       pos = i;
       break;
    }
  }
  return pos;
}

如上代码，在**最好情况下：数组的首元素的值与x相等，此时时间复杂度为O(1)，在最坏情况下：遍历整个数组，但是仍然没有找到对应的元素，此时的时间复杂度为O(n)。**至于平均时间复杂度的分析稍微复杂一些，**平均之间复杂度又称为期望时间复杂度或加权时间复杂度。**在本例中，有n个元素，每个元素都有$1/n$的可能性被选中，并且被选中的元素有$1/2$的可能性等于x，因此：

$1 * 1/(2n) + 2 * 1/(2n) + ... + n * 1/(2n) + n * 1/2= (3n+1)/4$

上述值就是每个位置可能出现等于x的情况的加权平均值，也叫做期望值，所以平均时间复杂度的全称应该叫做加权平均时间复杂度或者期望时间复杂度。上述值用大O表示为O(n)。另外一种分析方法是，总共有n+1种情况，n种情况下找到该元素，1种情况下元素不在数组中，如下：

$(1+2+...+n+n)/(n+1) = n(n+3)/(2(n+1))$

这种分析方法没有考虑每种情况出现的概率，不可取。

4.3 均摊时间复杂度分析

上述两节之后我们已经初步掌握了时间复杂度的分析方法，本节介绍均摊时间复杂度，均摊时间复杂度对应于算法中的摊还分析(或者叫平摊分析)。相比最好、最差、平均时间复杂度，均摊时间复杂度的使用场景更加特殊、更加有限。

 // array 表示一个长度为 n 的数组
 // 代码中的 array.length 就等于 n
 int[] array = new int[n];
 int count = 0;

 void insert(int val) {
    if (count == array.length) {
       int sum = 0;
       for (int i = 0; i < array.length; ++i) {
          sum = sum + array[i];
       }
       array[0] = sum;
       count = 1;
    }

    array[count] = val;
    ++count;
 }

这段代码实现了往数组中插入数据的功能。当数组满了之后，也就是代码中 count==array.length时，通过for循环遍历数组求和，并清空数组，将求和之后的sum值放到数组的第一个位置，然后再将心得数据插入。当数组一开始有空闲位置时，则直接将数据插入数组。

最好情况下时间复杂度：O(1)，此时数组未满，并且由于count会自动执行加1操作，因此不用遍历找寻空位。

最坏情况下时间复杂度：O(n)，此时数组装满，首先需要遍历数组的全部元素执行累加操作，接着将累加后的和放入到数组的0位置上，然后count执行加1操作指向下一个位置，后续操作与最好情况下时间复杂度吻戏类似。

平均时间复杂度：假设数组的长度为n，根据插入的位置不同，可以将其分为n中情况，每种情况的时间复杂度都为O(1)，除此之外，还有一种当数组没有空闲位置时的情况，此时的时间复杂度为O(n)，而且这n+1中情况发生的概率一样，都是$1/(n+1)$，所以根据加权平均的计算方法，平均时间复杂度为：

$1 * 1/(n+1) + 1 * 1/(n+1) ... + n * 1/(n+1) = O(1)$

到目前位置，最好情况下时间复杂度、最坏情况下时间复杂度、平均情况下时间复杂度的计算，理解起来都没有任何问题。但是这个例子的平均复杂度分析其实并不需要上述那样复杂，不需要引入概率论的知识。这是为什么呢？其实将本例的insert()和前面的find()进行对比，可以知道，find()函数在极端情况下复杂度才为O(1)，但是insert在大部分情况下，时间复杂度都为O(1)，只有当数组没有空闲位置时，采薇O(n)。其次对于insert()，O(1)时间复杂度的插入和O(n)时间复杂度的插入，出现的频率是非常有规律的，而且有一定的前后时序关系，一般都是一个O(n)插入只有，紧跟着$n-1$个O(1)的插入操作，循环往复。所以针对这种特殊的场景，我们引入了一种更加简单的分析方法：摊还分析法，通过摊还分析得到的时间复杂度，本文给其命名为均摊时间复杂度。那究竟如何使用摊还分析法来分析算法的均摊时间复杂度呢？

我们还是继续看在数组中插入数据的例子。每一次O(n)的插入操作，都会跟着n-1次O(1)的插入操作，所以把时间耗时多的那次操作均摊到接下来的n-1次耗时少的操作上，均摊下来，这一组连续的操作的均摊时间复杂度就是O(1)，这就是均摊分析的大致思路。均摊时间复杂度和弹摊还分析的应用场景比较复杂，所以我们并不会经常用到。为了方便理解和记忆，本文总结了一下它们的应用场景。如果你以后遇到了，知道是怎么回事就行了。

对一个数据结构进行的操作中，大部分情况下时间复杂度都很低，只有个别情况下时间复杂度比较高，而且这些操作之间存在前后连贯的时序关系，这个时候，我们就可以将这一组操作放在一块儿分析，看是否能够将较高时间复杂度的那次操作的耗时平摊到其它时间复杂度较低的操作上。而且，在能够应用平摊时间复杂度的分析场景中，一般均摊时间复杂度就等于最好情况下的时间复杂度。

尽管许多数据结构和算法书籍都花了很大的力气来区分平均时间复杂度和均摊时间复杂度，但是其实我认为，均摊时间复杂度就是一种特殊的平均时间复杂度，我们没必要花太多的精力去区分它们。我们应该花时间去掌握它的分析方法，摊还分析法。至于分析出来的结果叫平均还是均摊，并不重要。

4.4 总结

之所以引入最好时间复杂度、最坏时间复杂度、平均时间复杂度、均摊时间复杂度这些概念，是因为很多算法，在不同的输入情况下，算法的时间复杂度不一样。在引入这些概念以后，我们能够更加全面的表示算法的时间复杂度。

// 全局变量，大小为 10 的数组 array，长度 len，下标 i。
int array[] = new int[10];
int len = 10;
int i = 0;

// 往数组中添加一个元素
void add(int element) {
   if (i >= len) { // 数组空间不够了
     // 重新申请一个 2 倍大小的数组空间
     int new_array[] = new int[len*2];
     // 把原来 array 数组中的数据依次 copy 到 new_array
     for (int j = 0; j < len; ++j) {
       new_array[j] = array[j];
     }
     // new_array 复制给 array，array 现在大小就是 2 倍 len 了
     array = new_array;
     len = 2 * len;
   }
   // 将 element 放到下标为 i 的位置，下标 i 加一
   array[i] = element;
   ++i;
}
/*答案：
最好时间复杂度O(1)，最坏时间复杂度O(n)，平均时间复杂度O(1)，均摊时间复杂度为O(1)
假设数组的长度为n，当数组未满时，每次往数组中添加元素的时间复杂度都为O(1)，当数组满时，需要O(n)的操作进行复制，并且这两个操作具有严格的时序关系，因此可以将复制的操作摊还给前面n-1次操作中，最终得到的时间复杂度仍然为O(1)
平均时间复杂度计算：
1 * 1/(n+1) + 1 * 1/(n+1)  ... + n * 1/(n+1)  = O(1)
*/