复杂度

字符串

正则表达式

搜索

BM

模式匹配

暴力匹配

KMP

思想：每当一趟匹配过程中出现字符比较不等，不需要回溯i指针，而是利用已经得到的“部分匹配”的结果将模式向右“滑动”尽可能远的一段距离后，继续进行比较。时间复杂度O(n+m)

  1. // 获得字符串t的next函数值
  2. public int[] next(char[] t) {
  3.     int[] next = new int[t.length];
  4.     next[0] = -1;
  5.     int i = 0;
  6.     int j = -1;
  7.     while (i < t.length - 1) {
  8.         if (j == -1 || t[i] == t[j]) {
  9.             i++;
  10.             j++;
  11.             if (t[i] != t[j]) {
  12.                 next[i] = j;
  13.             } else {
  14.                 next[i] = next[j];
  15.             }
  16.         } else {
  17.             j = next[j];
  18.         }
  19.     }
  20.     return next;
  21. }
  23. // s主串，t模式串，若匹配成功，返回下标，否则返回-1
  24. public int kmp(char[] s, char[] t) {
  25.     int[] next = next(t);
  26.     int i = 0;
  27.     int j = 0;
  28.     while (i <= s.length - 1 && j <= t.length - 1) {
  29.         if (j == -1 || s[i] == t[j]) {
  30.             i++;
  31.             j++;
  32.         } else {
  33.             j = next[j];
  34.         }
  35.     }
  36.     if (j < t.length) {
  37.         return -1;
  38.     } else
  39.         return i - t.length; // 返回模式串在主串中的头下标
  40. }

多模式匹配

  • AC自动机

    Trie树★

    又称字典树、前缀树、单词查找树、键树，多叉哈希树 Trie树典型应用是用于快速检索（最长前缀匹配），统计，排序和保存大量的字符串，所以经常被搜索引擎系统用于文本词频统计，搜索提示等场景。它的优点是最大限度地减少无谓的字符串比较，查询效率比较高。

  • 前缀树 ```java public void add(TrieNode root, String word) { TrieNode cur = root; for (int i = 0; i < word.length(); ++i) {

    1.   char ch = word.charAt(i);
    2.   if (cur.child[ch - 'a'] == null) {
    3.       cur.child[ch - 'a'] = new TrieNode();
    4.   }
    5.   cur = cur.child[ch - 'a'];

    } ++cur.frequency; }

public void find(TrieNode cur) { // 常用树的回溯或者DFS进行搜索 }

class TrieNode { int frequency; // 频数统计（可选） TrieNode[] child;

  1. public TrieNode() {
  2.     frequency = 0;
  3.     child = new TrieNode[26];
  4. }

}

  2. - 后缀树
  3. <a name="sgQrE"></a>
  4. ## 线性表
  5. <a name="0R9wV"></a>
  6. ### 数组
  7. <a name="zQq0e"></a>
  8. #### 树状数组
  9. <a name="m5mWc"></a>
  10. #### 矩阵
  11. <a name="xBPMJ"></a>
  12. #### 轮转数组★
  13. <a name="ATnYL"></a>
  14. ### 列表（动态数组）
  15. <a name="rzhA2"></a>
  16. ### 链表★
  17. <a name="4afe0b3f"></a>
  18. #### 单（双）向链表
  19. <a name="yTDqS"></a>
  20. #### 跳舞链
  21. <a name="cYIHW"></a>
  22. #### 快慢指针
  23. <a name="dzF16"></a>
  24. #### 链表反转★
  25. <a name="EY9ra"></a>
  26. #### 链表成环
  27. > 求是否成环、环节点
  29. <a name="cP8tO"></a>
  30. ### 跳表
  31. <a name="kux0m"></a>
  32. ### 队列
  33. <a name="7iXEg"></a>
  34. #### 普通队列
  35. <a name="15ec8cc5"></a>
  36. #### 阻塞队列
  37. <a name="3WfgB"></a>
  38. #### 并发队列
  39. <a name="e91ccb7d"></a>
  40. #### 双端队列
  41. <a name="H3aVG"></a>
  42. #### 优先队列
  43. <a name="sjvvl"></a>
  44. #### 多级反馈队列
  45. <a name="IEIjJ"></a>
  46. ### 栈★
  47. <a name="Zy64J"></a>
  48. #### 单调栈
  49. > MonotonousStack
  51. <a name="09sot"></a>
  52. ##### 思路
  53. 适用于求解第一个大/小于其本身的位置的题目（常用在数组中求大小/最值问题，或者这些问题的隐含问题中）<br />常用技巧：哨兵法（简化代码）
  55. | 求解的问题 | 遍历方向 | 维护单调性（栈底->栈顶） |
  56. | --- | --- | --- |
  57. | 左侧第一个更大 | 从右到左 | 单调递减 |
  58. | 左侧第一个更小 | 从右到左 | 单调递增 |
  59. | 右侧第一个更大 | 从左到右 | 单调递减 |
  60. | 右侧第一个更小 | 从左到右 | 单调递增 |
  62. <a name="hgz9L"></a>
  63. ##### 求解每个位置的模板
  64. ```java
  65. // 问题一：给定一个数组，请你返回每个元素右边第一个大于它的元素,如果不存在则返回-1
  66. public static int[] getFirstRightMax(int[] arr) {
  67.     if(arr == null || arr.length == 0) return null;
  68.     Deque<Integer> stack = new LinkedList<Integer>();
  69.     int[] res = new int[arr.length];
  70.     int i = 0;
  71.     while(i < arr.length) {
  72.         if(stack.isEmpty() || arr[stack.peek()] >= arr[i]) {
  73.             stack.push(i);
  74.             i++;
  75.         } else {
  76.             res[stack.pop()] = arr[i];
  77.         }
  78.     }
  79.     // 遍历走完之后，栈中可能还剩余数组
  80.     while(!stack.isEmpty()){
  81.         res[stack.pop()] = -1;
  82.     }
  83.     return res;
  84. }
  86. // 问题二：给定一个数组，请你返回每个元素左边第一个大于它的元素,如果不存在则返回-1
  87. public static int[] getFirstLeftMax(int[] arr) {
  88.     if(arr == null || arr.length == 0) return null;
  89.     Deque<Integer> stack = new LinkedList<Integer>();
  90.     int[] res = new int[arr.length];
  91.     int i = 0;
  92.     while(i < arr.length) {
  93.         if(stack.isEmpty() || arr[stack.peek()] >= arr[i]) {
  94.             stack.push(i);
  95.             i++;
  96.         } else {
  97.             res[stack.pop()] = stack.isEmpty() ? -1 : arr[stack.peek()];
  98.         }
  99.     }
  100.     while(!stack.isEmpty()){
  101.         res[stack.pop()] = stack.isEmpty() ? -1 : arr[stack.peek()];
  102.     }
  103.     return res;
  104. }

简单维护单调栈模板
  1. int[] nums = {3, 4, 2, 5, 6, 0, 1};
  2. Deque<Integer> stack = new LinkedList<>();
  3. int tmp = -1;
  4. for (int i = 0; i < n; ++i) {
  5.     while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
  6.         tmp = stack.pop(); // 可以记录下次大值的位置
  7.     }
  8.     stack.push(i);
  9. }

练习
    1. 接雨水（困难）
    1. 每日温度（中等）
    1. 下一个更大元素 I（简单）
    1. 去除重复字母（困难）
    1. 股票价格跨度（中等）
    1. 移掉K位数字
    1. 最短无序连续子数组

      并查集★

  • 不用计算连通量

    1. private class UnionFind {
    2.   private int[] parents;
    4.   UnionFind(int n) {
    5.       parents = new int[n];
    6.       for (int i = 0; i < n; ++i) {
    7.           parents[i] = i;
    8.       }
    9.   }
    11.   public int find(int x) {
    12.       return parents[x] == x ? x : parents[x] = find(parents[x]);
    13.   }
    15.   public void union(int a, int b) {
    16.       parents[find(a)] = find(b);
    17.   }
    18. }

  • 计算连通量

    1. private class UnionFind {
    2.   private int[] parents;
    3.   private int count;
    5.   UnionFind(int n) {
    6.       parents = new int[n];
    7.       for (int i = 0; i < n; ++i) {
    8.           parents[i] = i;
    9.       }
    10.       count = n;
    11.   }
    13.   public int find(int x) {
    14.       return parents[x] == x ? x : parents[x] = find(parents[x]);
    15.   }
    17.   public void union(int a, int b) {
    18.       int pa = find(a);
    19.       int pb = find(b);
    20.       if (pa != pb) {
    21.           count--;
    22.       }
    23.       parents[pa] = pb;
    24.   }
    25. }

    散列表/哈希表★

    散列函数

  • 直接定址法

  • 数字分析法
  • 除留余数法
  • 分段叠加法
  • 平方取中法

  • 伪随机数法

    冲突解决

  • 开放寻址法

  • 链地址法
  • 再哈希法

  • 建立公共溢出区

    过滤器

  • 布隆过滤器

  • 布谷鸟过滤器

    位图

    动态扩容

    树

    二叉树、平衡二叉树、红黑树、B树、B+树与B*树

    二叉树

  • 二叉树递归

    1. private static List<Integer> result = new ArrayList<>();
    2. public static List<Integer> DFS(TreeNode root) {
    3.       if (root == null) {
    4.               return null;
    5.       }
    6.       result.add(root.val);
    7.       if (root.left != null) {
    8.               DFS(root.left);
    9.       }
    10.       if (root.right != null) {
    11.                DFS(root.right);
    12.       }
    13.       return result;
    14. }

  • 二叉树非递归 LinkedList

    1. public static List<Integer> DFS(TreeNode root) {
    2.       if (root == null) {
    3.               return null;
    4.       }
    5.       Stack<TreeNode> stack = new Stack<>();
    6.       stack.push(root);
    7.       List<Integer> result = new ArrayList<>();
    8.       while (!stack.isEmpty()) {
    9.               TreeNode treeNode = stack.pop();
    10.               result.add(treeNode.val);
    11.               if (treeNode.right != null) {
    12.                       stack.push(treeNode.right);
    13.               }
    14.               if (treeNode.left != null) {
    15.                       stack.push(treeNode.left);
    16.               }
    17.       }
    18.   return result;
    19. }

    二叉树的最近公共祖先★

    二叉查找树★

    前序遍历
    1.   public static void preOrder(TreeNode root){
    2.       if(root != null){
    3.           System.out.print(root.val + " ");
    4.           preOrder(root.left);
    5.           preOrder(root.right);
    6.       }
    7.   }
  1. public static ArrayList preOrder1(TreeNode root){
  2.     Stack<TreeNode> stack = new Stack<TreeNode>();
  3.     ArrayList alist = new ArrayList();
  4.     TreeNode p = root;
  5.     while(p != null || !stack.empty()){
  6.         while(p != null){
  7.             alist.add(p.val);
  8.             stack.push(p);
  9.             p = p.left;
  10.         }
  11.         if(!stack.empty()){
  12.             TreeNode temp = stack.pop();
  13.             p = temp.right;
  14.         }
  15.     }
  16.     return alist;
  17. }

中序遍历
  1.     public static void inOrder(TreeNode root){
  2.         if(root != null){
  3.             inOrder(root.left);
  4.             System.out.print(root.val + " ");
  5.             inOrder(root.right);
  6.         }
  7.     }
  1. public static ArrayList inOrder1(TreeNode root){
  2.     ArrayList alist = new ArrayList();
  3.     Stack<TreeNode> stack = new Stack<TreeNode>();
  4.     TreeNode p = root;
  5.     while(p != null || !stack.empty()){
  6.         while(p != null){
  7.             stack.push(p);
  8.             p = p.left;
  9.         }
  10.         if(!stack.empty()){
  11.             TreeNode temp = stack.pop();
  12.             alist.add(temp.val);
  13.             p = temp.right;
  14.         }
  15.     }
  16.     return alist;
  17. }

后序遍历
  1.     public static void postOrder(TreeNode root){
  2.         if(root != null){
  3.             postOrder(root.left);
  4.             postOrder(root.right);
  5.             System.out.print(root.val + " ");
  6.         }
  7.     }
  1.     public static ArrayList postOrder1(TreeNode root){
  2.         ArrayList alist = new ArrayList();
  3.         Stack<TreeNode> stack = new Stack<TreeNode>();
  4.         if(root == null)
  5.             return alist;
  6.         TreeNode cur,pre = null;
  7.         stack.push(root);
  8.         while(!stack.empty()){
  9.             cur = stack.peek();
  10.             if((cur.left == null && cur.right == null) || (pre != null && (cur.left == pre || cur.right == pre))){
  11.                 TreeNode temp = stack.pop();
  12.                 alist.add(temp.val);
  13.                 pre = temp;
  14.             }
  15.             else{
  16.                 if(cur.right != null)
  17.                     stack.push(cur.right);
  18.                 if(cur.left != null)
  19.                     stack.push(cur.left);
  20.             }
  21.         }
  22.         return alist;
  23.     }

层序遍历
  1.     private static void levelOrder(TreeNode root) {
  2.         Queue<TreeNode> queue = new LinkedList<TreeNode>();
  3.         if(root == null)
  4.             return;
  5.         queue.offer(root);
  6.         while(!queue.isEmpty()){
  7.             TreeNode temp  = queue.poll();
  8.             System.out.print(temp.val + " ");
  9.             if(temp.left != null)
  10.                 queue.offer(temp.left);
  11.             if(temp.right != null)
  12.                 queue.offer(temp.right);
  13.         }
  14.     }

Morris遍历

完全二叉树

平衡二叉树

平衡二叉查找树

AVL树

红黑树

线段树★

https://www.cnblogs.com/AC-King/p/7789013.html

  • 主席树

    多路查找树

    B-树

    B+树

    B*树

    2-3树/2-3-4树

    哈夫曼树与编码

    堆★

    大（小）顶堆

    二项堆

    优先队列

    斐波那契堆

    可并堆

    最近公共祖先

    图

    存储

    邻接矩阵

    邻接表

    最短路径

    单源最短路

    Dijkstra算法★

    T-O(n^2+e)/S-O(n+e)

Floyd-Warshall算法

T-O(n3)/S-O(n2)

Bellman-Ford算法★

T-O(ne)/S-O(n)

随机游走

最小生成树

  • Kruskal算法

  • Prim算法

    拓扑排序★

    关键路径

    网络流建模

    二分图匹配

  • 配对

  • 匈牙利算法

    其他

  • 中心性算法

  • 社群发现算法

    网络流

    最大流

  • 最短增广路

  • Dinic算法

    最大流最小割

  • 最大收益

  • 方格取数

    最小费用最大流

  • 最小费用路

  • 消图

    数据流★