一、复杂度分析

  数据结构是为算法服务的，算法要作用在特定的数据结构之上。

  大O时间复杂度表示法。大O时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以，也叫作渐进时间复杂度，简称时间复杂度。

1.1 时间复杂度分析

• 只关注循环执行次数最多的一段代码
• 加法法则：总复杂度等于量级最大的那段代码的复杂度
• 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积（嵌套循环）

  复杂度量级，可以粗略地分为两类，多项式量级和非多项式量级。其中，非多项式量级只有两个：O(2n) 和 O(n!)。把时间复杂度为非多项式量级的算法问题叫作NP（Non-Deterministic Polynomial，非确定多项式）问题。

O(1) O(logn) O(nlogn) O(m+n) O(m*n) - 代码的复杂度由两个数据的规模来决定

1.2 空间复杂度分析

  空间复杂度全称就是渐进空间复杂度，表示算法的存储空间与数据规模之间的增长关系。
  空间复杂度：指除了原本的数据存储空间外，算法运行还需要额外的存储空间。

O(1) O(n) O(n2 )

image.png

1.3 最好、最坏、平均情况时间复杂度

• 最好情况时间复杂度就是，在最理想的情况下，执行这段代码的时间复杂度
• 最坏情况时间复杂度就是，在最糟糕的情况下，执行这段代码的时间复杂度
• 平均时间复杂度的全称应该叫加权平均时间复杂度或者期望时间复杂度

1.4 均摊时间复杂度

  均摊时间复杂度就是一种特殊的平均时间复杂度。在能够应用均摊时间复杂度分析的场合，一般均摊时间复杂度就等于最好情况时间复杂度。

二、数组

  数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。数组支持随机访问，根据下标随机访问的时间复杂度为 O(1)。

从数组存储的内存模型上来看，“下标”最确切的定义应该是“偏移（offset）”

  线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。其实除了数组，链表、队列、栈等也是线性表结构。

  数组VS容器：

• Autoboxing、Unboxing 则有一定的性能消耗，所以如果特别关注性能，或者希望使用基本类型，就可以选用数组
• 如果数据大小事先已知，并且对数据的操作非常简单，用不到 ArrayList 提供的大部分方法，也可以直接使用数组
• 表示多维数组时，用数组往往会更加直观

三、链表

  链表通过指针将一组零散的内存块串联在一起。其中，我们把内存块称为链表的“结点”。

image.png

  循环链表是一种特殊的单链表。它跟单链表唯一的区别就在尾结点。

image.png

  双向链表可以支持 O(1) 时间复杂度的情况下找到前驱结点。

image.png

  双向循环链表：

image.png

  如何用链表来实现LRU（最近最少使用）缓存淘汰策略：
  维护一个有序单链表，越靠近链表尾部的结点是越早之前访问的。当有一个新的数据被访问时，我们从链表头开始顺序遍历链表。

1. 如果此数据之前已经被缓存在链表中了，我们遍历得到这个数据对应的结点，并将其从原来的位置删除，然后再插入到链表的头部
2. 如果此数据没有在缓存链表中，又可以分为两种情况：如果此时缓存未满，则将此结点直接插入到链表的头部；如果此时缓存已满，则链表尾结点删除，将新的数据结点插入链表的头部
    - 如果此时缓存未满，则将此结点直接插入到链表的头部；
    - 如果此时缓存已满，则链表尾结点删除，将新的数据结点插入链表的头部。

• 理解指针或引用的含义：将某个变量赋值给指针，实际上就是将这个变量的地址赋值给指针，或者反过来说，指针中存储了这个变量的内存地址，指向了这个变量，通过指针就能找到这个变量。
• 警惕指针丢失和内存泄漏：插入结点时，一定要注意操作的顺序；删除链表结点时，也一定要记得手动释放内存空间。
• 利用哨兵简化实现难度：针对链表的插入、删除操作，需要对插入第一个结点和删除最后一个结点的情况进行特殊处理。有哨兵结点的链表叫带头链表。相反，没有哨兵结点的链表就叫作不带头链表。

image.png

• 重点留意边界条件处理：1）链表为空 2）链表只包含一个结点时 3）链表只包含两个结点时 4）在处理头结点和尾结点，是否能正常工作。
• 举例画图，辅助思考
• 多写多练，没有捷径

1）单链表反转 2） 链表中环的检测 3） 两个有序的链表合并 4）删除链表倒数第n个结点 5）求链表的中间结点

四、栈

  后进者先出，先进者后出。从栈的操作特性上来看，栈是一种“操作受限”的线性表，只允许在一端插入和删除数据。

image.png

• 栈在函数调用中的应用
• 栈在表达式求值中的应用：编译器通过两个栈来实现，其中一个保存操作数的栈，另一个是保存运算符的栈。

image.png

• 栈在括号匹配中的应用

五、队列

  先进者先出，队列跟栈一样，也是一种操作受限的线性表数据结构。用数组实现的队列叫作顺序队列，用链表实现的队列叫作链式队列。

image.png

  循环队列：队列为空的判断条件仍然是 head == tail；当队满时，(tail+1)%n=head。当队列满时，图中的 tail 指向的位置实际上是没有存储数据的。所以，循环队列会浪费一个数组的存储空间。

image.png

5.1 阻塞队列和并发队列

  阻塞队列其实就是在队列基础上增加了阻塞操作。简单来说，就是在队列为空的时候，从队头取数据会被阻塞。因为此时还没有数据可取，直到队列中有了数据才能返回；如果队列已经满了，那么插入数据的操作就会被阻塞，直到队列中有空闲位置后再插入数据，然后再返回。

  生产者-消费者模型：

image.png

  线程安全的队列我们叫作并发队列。最简单直接的实现方式是直接在enqueue()、dequeue()方法上加锁，但是锁粒度大并发度会比较低，同一时刻仅允许一个存或者取操作。实际上，基于数组的循环队列，利用CAS原子操作，可以实现非常高效的并发队列。这也是循环队列比链式队列应用更加广泛的原因。

对于大部分资源有限的场景，当没有空闲资源时，基本上都可以通过“队列”这种数据结构来实现请求排队。

六、递归

  递归需要满足的三个条件：

• 一个问题的解可以分解为几个子问题的解，子问题就是数据规模更小的问题
• 这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样
• 存在递归终止条件

找到如何将大问题分解为小问题的规律，并且基于此写出递推公式，然后再推敲终止条件，最后将递推公式和终止条件翻译成代码

编写递归代码的关键是，只要遇到递归，我们就把它抽象成一个递推公式，不用想一层层的调用关系，不要试图用人脑去分解递归的每个步骤

//走台阶
int f(int n) {
  if (n == 1) return 1;
  if (n == 2) return 2;
  return f(n-1) + f(n-2);
}

• 递归代码要警惕堆栈溢出：在代码中限制递归调用的最大深度
• 递归代码要警惕重复计算

  递归本身就是借助栈来实现的，只不过我们使用的栈是系统或者虚拟机本身提供的。

七、排序

image.png

  分析一个排序算法：

• 排序算法的执行效率： 1）最好情况、最坏情况、平均情况时间复杂度 2） 时间复杂度的系数、常数 、低阶 3）比较次数和交换（或移动）次数
• 排序算法的内存消耗：原地排序算法，就是特指空间复杂度是 O(1) 的排序算法
• 排序算法的稳定性：如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变（稳定性）

7.1 冒泡排序（Bubble Sort）

  冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置，重复n次，就完成了n个数据的排序工作。

image.png

// 冒泡排序，a表示数组，n表示数组大小
public void bubbleSort(int[] a, int n) {
  if (n <= 1) return;
 
 for (int i = 0; i < n; ++i) {
    // 提前退出冒泡循环的标志位
    boolean flag = false;
    for (int j = 0; j < n - i - 1; ++j) {
      if (a[j] > a[j+1]) { // 交换
        int tmp = a[j];
        a[j] = a[j+1];
        a[j+1] = tmp;
        flag = true;  // 表示有数据交换      
      }
    }
    if (!flag) break;  // 没有数据交换，提前退出
  }
}

• 冒泡排序是原地排序算法
• 冒泡排序是稳定的排序算法
• 冒泡排序的时间复杂度：最好情况时间复杂度是O(n)，最坏情况时间复杂度为O(n2)，平均情况下的时间复杂度就是O(n2)

7.2 插入排序（Insertion Sort）

  即动态地往有序集合中添加数据，我们可以通过这种方法保持集合中的数据一直有序。插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。

image.png

// 插入排序，a表示数组，n表示数组大小
public void insertionSort(int[] a, int n) {
  if (n <= 1) return;

  for (int i = 1; i < n; ++i) {
    int value = a[i];
    int j = i - 1;
    // 查找插入的位置
    for (; j >= 0; --j) {
      if (a[j] > value) {
        a[j+1] = a[j];  // 数据移动
      } else {
        break;
      }
    }
    a[j+1] = value; // 插入数据
  }
}

• 插入排序是原地排序算法
• 插入排序是稳定的排序算法
• 插入排序的时间复杂度：最好情况时间复杂度是O(n)，最坏情况时间复杂度为O(n2)，平均情况下的时间复杂度就是O(n2)

  冒泡排序的数据交换要比插入排序的数据移动要复杂，冒泡排序需要3个赋值操作，而插入排序只需要1个。

7.3 选择排序（Selection Sort）

  选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。

image.png

• 选择排序是原地排序算法
• 选择排序是一种不稳定的排序算法
• 选择排序的时间复杂度：最好情况时间复杂度是O(n2)，最坏情况时间复杂度为O(n2)，平均情况下的时间复杂度就是O(n2)

7.4 归并排序（Merge Sort）

  如果要排序一个数组，我们先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了。归并排序使用的就是分治思想，分治算法一般都是用递归来实现的。分治是一种解决问题的处理思想，递归是一种编程技巧。

image.png

递推公式：
merge_sort(p…r) = merge(merge_sort(p…q), merge_sort(q+1…r))

终止条件：
p >= r 不用再继续分解

// 归并排序算法, A是数组，n表示数组大小
merge_sort(A, n) {
  merge_sort_c(A, 0, n-1)
}

// 递归调用函数
merge_sort_c(A, p, r) {
  // 递归终止条件
  if p >= r  then return

  // 取p到r之间的中间位置q
  q = (p+r) / 2
  // 分治递归
  merge_sort_c(A, p, q)
  merge_sort_c(A, q+1, r)
  // 将A[p...q]和A[q+1...r]合并为A[p...r]
  merge(A[p...r], A[p...q], A[q+1...r])
}

merge(A[p...r], A[p...q], A[q+1...r]) {
  var i := p，j := q+1，k := 0 // 初始化变量i, j, k
  var tmp := new array[0...r-p] // 申请一个大小跟A[p...r]一样的临时数组
  while i<=q AND j<=r do {
    if A[i] <= A[j] {
      tmp[k++] = A[i++] // i++等于i:=i+1
    } else {
      tmp[k++] = A[j++]
    }
  }
  
  // 判断哪个子数组中有剩余的数据
  var start := i，end := q
  if j<=r then start := j, end:=r
  
  // 将剩余的数据拷贝到临时数组tmp
  while start <= end do {
    tmp[k++] = A[start++]
  }
  
  // 将tmp中的数组拷贝回A[p...r]
  for i:=0 to r-p do {
    A[p+i] = tmp[i]
  }
}

• 归并排序是一个稳定的排序算法
• 归并排序的时间复杂度：最好情况、最坏情况，还是平均情况，时间复杂度都是O(nlogn)
• 归并排序不是原地排序算法，空间复杂度是O(n)

不仅递归求解的问题可以写成递推公式，递归代码的时间复杂度也可以写成递推公式

7.5 快速排序算法（Quicksort）

  如果要排序数组中下标从p到r之间的一组数据，我们选择p到r之间的任意一个数据作为pivot（分区点）。

image.png

递推公式：
quick_sort(p…r) = quick_sort(p…q-1) + quick_sort(q+1… r)

终止条件：
p >= r

// 快速排序，A是数组，n表示数组的大小
quick_sort(A, n) {
  quick_sort_c(A, 0, n-1)
}
// 快速排序递归函数，p,r为下标
quick_sort_c(A, p, r) {
  if p >= r then return
  
  q = partition(A, p, r) // 获取分区点
  quick_sort_c(A, p, q-1)
  quick_sort_c(A, q+1, r)
}

partition(A, p, r) {
  pivot := A[r]
  i := p
  for j := p to r-1 do {
    if A[j] < pivot {
      swap A[i] with A[j]
      i := i+1
    }
  }
  swap A[i] with A[r]
  return i

• 选择排序是原地排序算法
• 快速排序并不是一个稳定的排序算法
• 归并排序的时间复杂度：最好情况O(nlogn)、最坏情况O(n2)，平均情况O(nlogn)

归并排序的处理过程是由下到上的，先处理子问题，然后再合并。而快排正好相反，它的处理过程是由上到下的，先分区，然后再处理子问题

快速排序通过设计巧妙的原地分区函数，可以实现原地排序，解决了归并排序占用太多内存的问题

7.6 桶排序（Bucket sort）

  核心思想是将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。

image.png

• 桶排序的时间复杂度是O(n)
• 桶排序比较适合用在外部排序中。所谓的外部排序就是数据存储在外部磁盘中，数据量比较大，内存有限，无法将数据全部加载到内存中

7.7 计数排序（Counting sort）

  计数排序其实是桶排序的一种特殊情况。当要排序的n个数据，所处的范围并不大的时候，比如最大值是k，我们就可以把数据划分成k个桶。每个桶内的数据值都是相同的，省掉了桶内排序的时间。

• 时间复杂度是O(n)

  计数排序只能用在数据范围不大的场景中，如果数据范围k比要排序的数据n大很多，就不适合用计数排序了。而且，计数排序只能给非负整数排序，如果要排序的数据是其他类型的，要将其在不改变相对大小的情况下，转化为非负整数。

7.8 基数排序（Radix sort）

  基数排序对要排序的数据是有要求的，需要可以分割出独立的“位”来比较，而且位之间有递进的关系，如果a数据的高位比b数据大，那剩下的低位就不用比较了。除此之外，每一位的数据范围不能太大，要可以用线性排序算法来排序，否则，基数排序的时间复杂度就无法做到O(n)了（手机号比较）。

7.9 如何选择合适的排序算法

image.png

  如果对小规模数据进行排序，可以选择时间复杂度是O(n2) 的算法；如果对大规模数据进行排序，时间复杂度是O(nlogn)的算法更加高效。所以，为了兼顾任意规模数据的排序，一般都会首选时间复杂度是O(nlogn)的排序算法来实现排序函数。

  如何优化快速排序：

• 最理想的分区点是：被分区点分开的两个分区中，数据的数量差不多
• 三数取中法
• 随机法

八、二分查找

  二分查找针对的是一个有序的数据集合，查找思想有点类似分治思想。每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为0。

• 时间复杂度是O(logn)

常量级时间复杂度的算法有时候可能还没有O(logn) 的算法执行效率高。指数时间复杂度的算法在大规模数据面前是无效的。

终止条件、区间上下界更新方法、返回值选择

// 二分查找的递归实现
public int bsearch(int[] a, int n, int val) {
  return bsearchInternally(a, 0, n - 1, val);
}

private int bsearchInternally(int[] a, int low, int high, int value) {
  if (low > high) return -1;

  int mid =  low + ((high - low) >> 1);
  if (a[mid] == value) {
    return mid;
  } else if (a[mid] < value) {
    return bsearchInternally(a, mid+1, high, value);
  } else {
    return bsearchInternally(a, low, mid-1, value);
  }
}

8.1 二分查找应用场景的局限性

• 二分查找依赖的是顺序表结构，简单点说就是数组
• 二分查找针对的是有序数据
• 数据量太小不适合二分查找
• 数据量太大也不适合二分查找

8.2 查找第一个值等于给定值的元素

public int bsearch(int[] a, int n, int value) {
  int low = 0;
  int high = n - 1;
  while (low <= high) {
    int mid =  low + ((high - low) >> 1);
    if (a[mid] > value) {
      high = mid - 1;
    } else if (a[mid] < value) {
      low = mid + 1;
    } else {
      if ((mid == 0) || (a[mid - 1] != value)) return mid;
      else high = mid - 1;
    }
  }
  return -1;
}

8.3 查找最后一个值等于给定值的元素

public int bsearch(int[] a, int n, int value) {
  int low = 0;
  int high = n - 1;
  while (low <= high) {
    int mid =  low + ((high - low) >> 1);
    if (a[mid] > value) {
      high = mid - 1;
    } else if (a[mid] < value) {
      low = mid + 1;
    } else {
      if ((mid == n - 1) || (a[mid + 1] != value)) return mid;
      else low = mid + 1;
    }
  }
  return -1;
}

8.4 查找第一个大于等于给定值的元素

public int bsearch(int[] a, int n, int value) {
  int low = 0;
  int high = n - 1;
  while (low <= high) {
    int mid =  low + ((high - low) >> 1);
    if (a[mid] >= value) {
      if ((mid == 0) || (a[mid - 1] < value)) return mid;
      else high = mid - 1;
    } else {
      low = mid + 1;
    }
  }
  return -1;
}

8.5 查找最后一个小于等于给定值的元素

public int bsearch7(int[] a, int n, int value) {
  int low = 0;
  int high = n - 1;
  while (low <= high) {
    int mid =  low + ((high - low) >> 1);
    if (a[mid] > value) {
      high = mid - 1;
    } else {
      if ((mid == n - 1) || (a[mid + 1] > value)) return mid;
      else low = mid + 1;
    }
  }
  return -1;
}

九、跳表

image.png

  链表加多级索引的结构，就是跳表。

• 跳表中查询任意数据的时间复杂度是O(logn)
• 跳表的空间复杂度是O(n)

9.1 高效的动态插入和删除

• 插入、删除操作的时间复杂度也是O(logn)
• 删除操作需要删除原始链表中的结点，还要删除索引中的节点

image.png

9.2 跳表索引动态更新

image.png

• 跳表是通过随机函数来维护前面提到的“平衡性”
• 往跳表中插入数据的时候，我们可以选择同时将这个数据插入到部分索引层中

image.png

十、散列表（Hash Table）

  散列表用的是数组支持按照下标随机访问数据的特性，所以散列表其实就是数组的一种扩展，由数组演化而来。可以说，如果没有数组，就没有散列表。

image.png

  散列表用的就是数组支持按照下标随机访问的时候，时间复杂度是O(1)的特性。我们通过散列函数把元素的键值映射为下标，然后将数据存储在数组中对应下标的位置。当我们按照键值查询元素时，我们用同样的散列函数，将键值转化数组下标，从对应的数组下标的位置取数据。

10.1 散列函数

  如何构造散列函数：

• 散列函数计算得到的散列值是一个非负整数
• 如果 key1 = key2，那 hash(key1) == hash(key2)
• 如果 key1 ≠ key2，那 hash(key1) ≠ hash(key2)

  散列冲突：

• 开放寻址法

image.png

• 链表法

image.png

散列表的装载因子=填入表中的元素个数/散列表的长度。装载因子越大，说明空闲位置越少，冲突越多，散列表的性能会下降。

10.2 如何设计散列函数

• 散列函数的设计不能太复杂
• 散列函数生成的值要尽可能随机并且均匀分布
• 直接寻址法、平方取中法、折叠法、随机数法
• 装载因子过大

  针对散列表的扩容，数据搬移操作要复杂很多。因为散列表的大小变了，数据的存储位置也变了，所以我们需要通过散列函数重新计算每个数据的存储位置。
  装载因子阈值的设置要权衡时间、空间复杂度。如果内存空间不紧张，对执行效率要求很高，可以降低负载因子的阈值；相反，如果内存空间紧张，对执行效率要求又不高，可以增加负载因子的值，甚至可以大于1。

  如何避免低效的扩容：

image.png

10.3 如何选择冲突解决方法

• 开放寻址法：散列表中的数据都存储在数组中，可以有效地利用CPU缓存加快查询速度。而且，这种方法实现的散列表，序列化起来比较简单。当数据量比较小、装载因子小的时候，适合采用开放寻址法。这也是Java中的ThreadLocalMap使用开放寻址法解决散列冲突的原因。
• 链表法：链表法对内存的利用率比开放寻址法要高。链表法比起开放寻址法，对大装载因子的容忍度更高。基于链表的散列冲突处理方法比较适合存储大对象、大数据量的散列表，而且，比起开放寻址法，它更加灵活，支持更多的优化策略，比如用红黑树代替链表。

10.4 设计散列表

  工业级的散列表应该具有哪些特性：

• 支持快速地查询、插入、删除操作
• 内存占用合理，不能浪费过多的内存空间
• 性能稳定，极端情况下，散列表的性能也不会退化到无法接受的情况

  如何实现这样一个散列表：

• 设计一个合适的散列函数
• 定义装载因子阈值，并且设计动态扩容策略
• 选择合适的散列冲突解决方法

10.5 LRU缓存淘汰算法

  借助散列表，我们可以把LRU缓存淘汰算法的时间复杂度降低为O(1)。

image.png

  散列表是通过链表法解决散列冲突的，所以每个结点会在两条链中。一个链是刚刚我们提到的双向链表，另一个链是散列表中的拉链。前驱和后继指针是为了将结点串在双向链表中，hnext指针是为了将结点串在散列表的拉链中。

  Java LinkedHashMap：
  按照访问时间排序的LinkedHashMap本身就是一个支持LRU缓存淘汰策略的缓存系统。LinkedHashMap是通过双向链表和散列表这两种数据结构组合实现的。LinkedHashMap中的“Linked”实际上是指的是双向链表，并非指用链表法解决散列冲突。

十一、哈希算法

  将任意长度的二进制值串映射为固定长度的二进制值串，这个映射的规则就是哈希算法，而通过原始数据映射之后得到的二进制值串就是哈希值。

• 从哈希值不能反向推导出原始数据（所以哈希算法也叫单向哈希算法）
• 对输入数据非常敏感，哪怕原始数据只修改了一个Bit，最后得到的哈希值也大不相同
• 散列冲突的概率要很小，对于不同的原始数据，哈希值相同的概率非常小
• 哈希算法的执行效率要尽量高效，针对较长的文本，也能快速地计算出哈希值

  哈希算法应用：

• 安全加密：最常用于加密的哈希算法是MD5（MD5 Message-Digest Algorithm，MD5消息摘要算法）和SHA（Secure Hash Algorithm，安全散列算法）、DES（Data Encryption Standard，数据加密标准）、AES（Advanced Encryption Standard，高级加密标准）
• 唯一标识
• 数据校验
• 散列函数：散列函数也是哈希算法的一种应用。散列函数对于散列算法计算得到的值，是否能反向解密也并不关心。散列函数中用到的散列算法，更加关注散列后的值是否能平均分布，也就是，一组数据是否能均匀地散列在各个槽中。除此之外，散列函数执行的快慢，也会影响散列表的性能，所以，散列函数用的散列算法一般都比较简单，比较追求效率。
• 负载均衡：通过哈希算法，对客户端IP地址或者会话ID计算哈希值，将取得的哈希值与服务器列表的大小进行取模运算，最终得到的值就是应该被路由到的服务器编号。
• 数据分片
• 分布式存储：一致性哈希算法-假设我们有k个机器，数据的哈希值的范围是[0, MAX]。我们将整个范围划分成m个小区间（m远大于k），每个机器负责m/k个小区间。当有新机器加入的时候，我们就将某几个小区间的数据，从原来的机器中搬移到新的机器中。

一致性哈希算法

十二、二叉树

image.png

  二叉树，顾名思义，每个节点最多有两个“叉”，也就是两个子节点，分别是左子节点和右子节点。叶子节点全都在最底层，除了叶子节点之外，每个节点都有左右两个子节点，这种二叉树就叫做满二叉树。叶子节点都在最底下两层，最后一层的叶子节点都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大，这种二叉树叫做完全二叉树。

image.png

12.1 二叉树的遍历

  前序遍历、中序遍历和后序遍历：二叉树遍历的时间复杂度是O(n)。

image.png

• 前序遍历是指，对于树中的任意节点来说，先打印这个节点，然后再打印它的左子树，最后打印它的右子树。
• 中序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后再打印它本身，最后打印它的右子树。
• 后序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后再打印它的右子树，最后打印这个节点本身。

实际上，二叉树的前、中、后序遍历就是一个递归的过程。比如，前序遍历，其实就是先打印根节点，然后再递归地打印左子树，最后递归地打印右子树。

void preOrder(Node* root) {
  if (root == null) return;
  print root // 此处为伪代码，表示打印root节点
  preOrder(root->left);
  preOrder(root->right);
}

void inOrder(Node* root) {
  if (root == null) return;
  inOrder(root->left);
  print root // 此处为伪代码，表示打印root节点
  inOrder(root->right);
}

void postOrder(Node* root) {
  if (root == null) return;
  postOrder(root->left);
  postOrder(root->right);
  print root // 此处为伪代码，表示打印root节点
}

12.2 二叉查找树（Binary Search Tree）

  二叉查找树最大的特点就是，支持动态数据集合的快速插入、删除、查找操作。
  二叉查找树要求，在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值。

image.png

• 二叉查找树的查找操作：我们先取根节点，如果它等于我们要查找的数据，那就返回。如果要查找的数据比根节点的值小，那就在左子树中递归查找；如果要查找的数据比根节点的值大，那就在右子树中递归查找。

public class BinarySearchTree {
  private Node tree;

  public Node find(int data) {
    Node p = tree;
    while (p != null) {
      if (data < p.data) p = p.left;
      else if (data > p.data) p = p.right;
      else return p;
    }
    return null;
  }

  public static class Node {
    private int data;
    private Node left;
    private Node right;

    public Node(int data) {
      this.data = data;
    }
  }
}

• 二叉查找树的插入操作：从根节点开始，依次比较要插入的数据和节点的大小关系。如果要插入的数据比节点的数据大，并且节点的右子树为空，就将新数据直接插到右子节点的位置；如果不为空，就再递归遍历右子树，查找插入位置。同理，如果要插入的数据比节点数值小，并且节点的左子树为空，就将新数据插入到左子节点的位置；如果不为空，就再递归遍历左子树，查找插入位置。

public void insert(int data) {
  if (tree == null) {
    tree = new Node(data);
    return;
  }

  Node p = tree;
  while (p != null) {
    if (data > p.data) {
      if (p.right == null) {
        p.right = new Node(data);
        return;
      }
      p = p.right;
    } else { // data < p.data
      if (p.left == null) {
        p.left = new Node(data);
        return;
      }
      p = p.left;
    }
  }
}

• 二叉查找树的删除操作

public void delete(int data) {
  Node p = tree; // p指向要删除的节点，初始化指向根节点
  Node pp = null; // pp记录的是p的父节点
  while (p != null && p.data != data) {
    pp = p;
    if (data > p.data) p = p.right;
    else p = p.left;
  }
  if (p == null) return; // 没有找到

  // 要删除的节点有两个子节点
  if (p.left != null && p.right != null) { // 查找右子树中最小节点
    Node minP = p.right;
    Node minPP = p; // minPP表示minP的父节点
    while (minP.left != null) {
      minPP = minP;
      minP = minP.left;
    }
    p.data = minP.data; // 将minP的数据替换到p中
    p = minP; // 下面就变成了删除minP了
    pp = minPP;
  }

  // 删除节点是叶子节点或者仅有一个子节点
  Node child; // p的子节点
  if (p.left != null) child = p.left;
  else if (p.right != null) child = p.right;
  else child = null;

  if (pp == null) tree = child; // 删除的是根节点
  else if (pp.left == p) pp.left = child;
  else pp.right = child;
}

中序遍历二叉查找树，可以输出有序的数据序列，时间复杂度是O(n)，非常高效。因此，二叉查找树也叫作二叉排序树。

十三、红黑树

  平衡二叉树：二叉树中任意一个节点的左右子树的高度相差不能大于1。最先被发明的平衡二叉查找树是AVL树。

image.png

  发明平衡二叉查找树这类数据结构的初衷是，解决普通二叉查找树在频繁的插入、删除等动态更新的情况下，出现时间复杂度退化的问题。
  平衡二叉查找树中“平衡”的意思，其实就是让整棵树左右看起来比较“对称”、比较“平衡”，不要出现左子树很高、右子树很矮的情况。这样就能让整棵树的高度相对来说低一些，相应的插入、删除、查找等操作的效率高一些。

  红黑树的英文是“Red-Black Tree”，简称R-B Tree。它是一种不严格的平衡二叉查找树。红黑树中的节点，一类被标记为黑色，一类被标记为红色。除此之外，一棵红黑树还需要满足这样几个要求：

• 根节点是黑色的
• 每个叶子节点都是黑色的空节点（NIL），也就是说，叶子节点不存储数据
• 任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的
• 每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点

image.png

红黑树的插入、删除、查找各种操作性能都比较稳定。对于工程应用来说，要面对各种异常情况，为了支撑这种工业级的应用，我们更倾向于这种性能稳定的平衡二叉查找树。

13.1 实现红黑树的基本思想

遇到什么样的节点排布，我们就对应怎么去调整

• 左旋（rotate left）、右旋（rotate right）。左旋全称其实是叫围绕某个节点的左旋，右旋全称叫围绕某个节点的右旋。

image.png

• 红黑树规定，插入的节点必须是红色的。而且，二叉查找树中新插入的节点都是放在叶子节点上
• 左右旋转和改变颜色

十四、递归树

  借助递归树来分析递归算法的时间复杂度。

十五、堆

  堆是一种特殊的树：

• 堆是一个完全二叉树：完全二叉树要求，除了最后一层，其他层的节点个数都是满的，最后一层的节点都靠左排列。
• 堆中每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值；堆中每个节点的值都大于等于（或者小于等于）其左右子节点的值。

对于每个节点的值都大于等于子树中每个节点值的堆，我们叫做“大顶堆”。对于每个节点的值都小于等于子树中每个节点值的堆，我们叫做“小顶堆”。

image.png

  第1个和第2个是大顶堆，第3个是小顶堆，第4个不是堆。
  数组存储堆：

image.png

  往堆中插入一个元素后，我们需要继续满足堆的两个特性。进行调整，让其重新满足堆的特性，叫做堆化（heapify）。

• 往堆中插入一个元素
• 删除堆顶元素

  堆排序。堆排序包含两个过程，建堆和排序。堆排序是一种原地的、时间复杂度为O(nlogn) 的排序算法。

  为什么快速排序要比堆排序性能好：

• 堆排序数据访问的方式没有快速排序友好：对于快速排序来说，数据是顺序访问的。而对于堆排序来说，数据是跳着访问的，对CPU缓存不友好。
• 对于同样的数据，在排序过程中，堆排序算法的数据交换次数要多于快速排序。

15.1 堆的应用

• 优先级队列：堆和优先级队列非常相似。一个堆就可以看作一个优先级队列。往优先级队列中插入一个元素，就相当于往堆中插入一个元素；从优先级队列中取出优先级最高的元素，就相当于取出堆顶元素。Java的PriorityQueue。

1. 合并有序小文件 2. 高性能定时器

• 利用堆求Top K
• 利用堆求中位数：利用一个大顶堆和一个小顶堆

十六、图

• 图中的元素我们就叫做顶点（vertex）
• 图中的一个顶点可以与任意其他顶点建立连接关系，这种建立的关系叫做边（edge）
• 跟顶点相连接的边的条数叫做顶点的度（degree）
• 有方向的图叫做“有向图”。以此类推，我们把边没有方向的图就叫做“无向图”
• 在有向图中，度分为入度（In-degree）和出度（Out-degree）
• 顶点的入度，表示有多少条边指向这个顶点；顶点的出度，表示有多少条边是以这个顶点为起点指向其他顶点
• 在带权图中，每条边都有一个权重（weight）

  邻接矩阵存储方法：

image.png

  邻接表存储方法：

image.png

public class Graph { // 无向图
  private int v; // 顶点的个数
  private LinkedList<Integer> adj[]; // 邻接表

  public Graph(int v) {
    this.v = v;
    adj = new LinkedList[v];
    for (int i=0; i<v; ++i) {
      adj[i] = new LinkedList<>();
    }
  }

  public void addEdge(int s, int t) { // 无向图一条边存两次
    adj[s].add(t);
    adj[t].add(s);
  }
}

16.1 广度优先搜索（BFS）

  是一种“地毯式”层层推进的搜索策略，即先查找离起始顶点最近的，然后是次近的，依次往外搜索。

image.png

16.2 深度优先搜索（DFS）

  假设你站在迷宫的某个岔路口，然后想找到出口。你随意选择一个岔路口来走，走着走着发现走不通的时候，你就回退到上一个岔路口，重新选择一条路继续走，直到最终找到出口。这种走法就是一种深度优先搜索策略。

image.png

  广度优先搜索，通俗的理解就是，地毯式层层推进，从起始顶点开始，依次往外遍历。广度优先搜索需要借助队列来实现，遍历得到的路径就是，起始顶点到终止顶点的最短路径。深度优先搜索用的是回溯思想，非常适合用递归实现。换种说法，深度优先搜索是借助栈来实现的。在执行效率方面，深度优先和广度优先搜索的时间复杂度都是O(E)，空间复杂度是O(V)。

十七、字符串匹配

  我们在字符串A中查找字符串B，那字符串A就是主串，字符串B就是模式串。我们把主串的长度记作n，模式串的长度记作m。因为我们是在主串中查找模式串，所以n>m。

BF/PK/BM/KMP算法

17.1 BF算法

  BF算法中的BF是Brute Force的缩写，中文叫作暴力匹配算法，也叫朴素匹配算法。我们在主串中，检查起始位置分别是0、1、2....n-m且长度为m的n-m+1个子串，看有没有跟模式串匹配的。

image.png

17.2 RK算法

  RK算法的全称叫Rabin-Karp算法，BF算法的升级版。我们通过哈希算法对主串中的n-m+1个子串分别求哈希值，然后逐个与模式串的哈希值比较大小。如果某个子串的哈希值与模式串相等，那就说明对应的子串和模式串匹配了。

image.png

17.3 BM算法

image.png

  在模式串与主串匹配的过程中，当模式串和主串某个字符不匹配的时候，能够跳过一些肯定不会匹配的情况，将模式串往后多滑动几位。
  BM算法核心思想是，利用模式串本身的特点，在模式串中某个字符与主串不能匹配的时候，将模式串往后多滑动几位，以此来减少不必要的字符比较，提高匹配的效率。BM算法构建的规则有两类，坏字符规则和好后缀规则。好后缀规则可以独立于坏字符规则使用。因为坏字符规则的实现比较耗内存，为了节省内存，我们可以只用好后缀规则来实现BM算法。

十八、Trie树

  Trie树，也叫“字典树”。顾名思义，它是一个树形结构。它是一种专门处理字符串匹配的数据结构，用来解决在一组字符串集合中快速查找某个字符串的问题。

Trie树的本质，就是利用字符串之间的公共前缀，将重复的前缀合并在一起。

image.png

  根节点不包含任何信息。每个节点表示一个字符串中的字符，从根节点到红色节点的一条路径表示一个字符串（注意：红色节点并不都是叶子节点）。

image.png

  针对在一组字符串中查找字符串的问题，我们在工程中，更倾向于用散列表或者红黑树。因为这两种数据结构，我们都不需要自己去实现，直接利用编程语言中提供的现成类库就行了。Trie树比较适合的是查找前缀匹配的字符串。

  单模式串匹配算法，是在一个模式串和一个主串之间进行匹配，也就是说，在一个主串中查找一个模式串。多模式串匹配算法，就是在多个模式串和一个主串之间做匹配，也就是说，在一个主串中查找多个模式串。

  AC自动机算法，全称是Aho-Corasick算法。AC自动机实际上就是在Trie树之上，加了类似KMP的next数组，只不过此处的next数组是构建在树上罢了。
  AC自动机的构建，包含两个操作：将多个模式串构建成Trie树；在Trie树上构建失败指针（相当于KMP中的失效函数next数组）。

十九、算法思想

19.1 贪心算法

• 第一步，当我们看到这类问题的时候，首先要联想到贪心算法：针对一组数据，我们定义了限制值和期望值，希望从中选出几个数据，在满足限制值的情况下，期望值最大。
• 第二步，我们尝试看下这个问题是否可以用贪心算法解决：每次选择当前情况下，在对限制值同等贡献量的情况下，对期望值贡献最大的数据。
• 第三步，我们举几个例子看下贪心算法产生的结果是否是最优的。

19.2 分治算法

  分治算法（divide and conquer）的核心思想其实就是四个字，分而治之 ，也就是将原问题划分成n个规模较小，并且结构与原问题相似的子问题，递归地解决这些子问题，然后再合并其结果，就得到原问题的解。

  分治算法能解决的问题，一般需要满足下面这几个条件：

• 原问题与分解成的小问题具有相同的模式；
• 原问题分解成的子问题可以独立求解，子问题之间没有相关性，这一点是分治算法跟动态规划的明显区别，等我们讲到动态规划的时候，会详细对比这两种算法；
• 具有分解终止条件，也就是说，当问题足够小时，可以直接求解；
• 可以将子问题合并成原问题，而这个合并操作的复杂度不能太高，否则就起不到减小算法总体复杂度的效果了。

19.3 回溯算法

  回溯的处理思想，有点类似枚举搜索。我们枚举所有的解，找到满足期望的解。为了有规律地枚举所有可能的解，避免遗漏和重复，我们把问题求解的过程分为多个阶段。每个阶段，我们都会面对一个岔路口，我们先随意选一条路走，当发现这条路走不通的时候（不符合期望的解），就回退到上一个岔路口，另选一种走法继续走。

19.4 动态规划

  问题分解为多个阶段，每个阶段对应一个决策。我们记录每一个阶段可达的状态集合（去掉重复的），然后通过当前阶段的状态集合，来推导下一个阶段的状态集合，动态地往前推进。动态规划是一种空间换时间的算法思想。

  一个模型三个特征：

• 多阶段决策最优解模型：解决问题的过程，需要经历多个决策阶段。每个决策阶段都对应着一组状态。然后我们寻找一组决策序列，经过这组决策序列，能够产生最终期望求解的最优值。
• 最优子结构：后面阶段的状态可以通过前面阶段的状态推导出来。
• 无后效性：第一层含义是，在推导后面阶段的状态的时候，我们只关心前面阶段的状态值，不关心这个状态是怎么一步一步推导出来的。第二层含义是，某阶段状态一旦确定，就不受之后阶段的决策影响。
• 重复子问题：不同的决策序列，到达某个相同的阶段时，可能会产生重复的状态。

状态转移表法解题思路大致可以概括为，回溯算法实现 - 定义状态 - 画递归树 - 找重复子问题 - 画状态转移表 - 根据递推关系填表 - 将填表过程翻译成代码。

状态转移方程法的大致思路可以概括为，找最优子结构 - 写状态转移方程 - 将状态转移方程翻译成代码。